poj3268 Silver Cow Party（两次dijkstra）

https://vjudge.net/problem/POJ-3268

一开始floyd超时了。。

对正图定点求最短，对逆图定点求最短，得到任意点到定点的往返最短路。

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<stack>

 #define lson l, m, rt<<1

 #define rson m+1, r, rt<<1|1

 #define INF 0x3f3f3f3f

 typedef unsigned long long ll;

 using namespace std;

 int t[][], rt[][];

 int d[], rd[], vis[];

 int n, m, x, a, b, T;

 void dijkstra(int dist[], int a[][])

 {

     memset(vis, , sizeof(vis));

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

         dist[i] = INF;

     }

     dist[x] = ;

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

         int mini = INF, k = -;

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

             if(!vis[j]&&mini > dist[j]){

                 mini = dist[j];

                 k = j;

             }

         }

         vis[k] = ;

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

             if(!vis[j]&&dist[j] > dist[k]+a[k][j]){

                 dist[j] = dist[k]+a[k][j];

             }

         }

     }

 }

 int main()

 {

     cin >> n >> m >> x;

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

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

             t[i][j] = INF; rt[i][j] = INF;

         }

     }

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

         cin >> a >> b >> T;

         t[a][b] = T;//图

         rt[b][a] = T;//逆图

     }

     dijkstra(d, t);

     dijkstra(rd, rt);

     int maxm = -INF;

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

         if(d[i]!=INF&&rd[i]!=INF&&d[i]+rd[i] > maxm){

             maxm = d[i]+rd[i];

         }

     }

     cout << maxm << endl;

     return ;

 }