kuangbin_ShortPath D (POJ 3268)

本来在想 单源多点很好解决但是多源单点怎么解 然后我发现只要倒过来就可以了

把输入存下来然后 处理完dis1 重新init一次 倒着再输入一次 处理dis2 输出max(dis1[i] + dis2[i])

#include <iostream>

#include <string>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <queue>

#include <map>

#include <vector>

#include <set>

#include <algorithm>

#define INF 0x3F3F3F3F

using namespace std;

typedef pair<int, int> pii;

struct cmp{

    bool operator ()(const pii a, const pii b){

        return a.first > b.first;

    }

};

int size, head[], point[], next[], val[];

void init()

{

    size = ;

    memset(head, -, sizeof head);

}

void add(int from, int to, int value)

{

    point[size] = to;

    val[size] = value;

    next[size] = head[from];

    head[from] = size++;

}

void dij(int dis[], int s)

{

    priority_queue <pii, vector<pii>, cmp> q;

    q.push(make_pair(, s));

    dis[s] = ;

    while(!q.empty()){

        pii u = q.top();

        q.pop();

        if(dis[u.second] < u.first) continue;

        for(int i = head[u.second]; ~i; i = next[i]){

            int j = point[i];

            if(dis[j] > val[i] + u.first){

                dis[j] = val[i] + u.first;

                q.push(make_pair(dis[j], j));

            }

        }

    }

}

int main()

{

    int n, m, x;//parameter

    int site1[], site2[], value[];//data

    int dis1[], dis2[], ans;//result

    //work out dis1

       scanf("%d%d%d", &n, &m, &x);

       memset(dis1, 0x3f, sizeof dis1);

       memset(dis2, 0x3f, sizeof dis2);

       init();

       for(int i = ; i < m; i++){

           scanf("%d%d%d", &site1[i], &site2[i], &value[i]);

           add(site1[i], site2[i], value[i]);

       }

       dij(dis1, x);

       //work out dis2

       init();

       for(int i = ; i < m; i++){

           add(site2[i], site1[i], value[i]);

       }

       dij(dis2, x);

       //output

       ans = dis1[] + dis2[];

       for(int i = ; i <= n; i++){

           ans = max(ans, dis1[i] + dis2[i]);

           //printf("dis1[%d] = %d dis2[%d] = %d\n", i, dis1[i], i, dis2[i]);

       }

       printf("%d\n", ans);

    return ;

}