POJ-3268 Silver Cow Party---正向+反向Dijkstra

时间：2023-12-19 20:39:14

题目链接：

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

题目大意：

有编号为1－N的牛，它们之间存在一些单向的路径。给定一头牛的编号X，其他牛要去拜访它并且拜访完之后要返回自己原来的位置，求所有牛从开始到回家的时间是多少？

思路：

所有牛都回到了家所花费的时间就是这些牛中花费时间的最大者，可以正向的Dijkstra求出从X到每个点的最短时间，然后一个骚操作：将所有边反向（swap(Map[i][j], Map[j][i])），再从x用dijkstra求出X到每个点的最短时间，第二次求出来的时间通过逆向求出来的是每个点到X的最短时间，两个一加，取最大者就是答案。

本题也可以用Bellman来求，不过由于边比较多，必须用队列优化的SPFA来求，但是SPA需要邻接表，不能像邻接矩阵那样直接反向，所以存图的时候存两张图，一张正向，一张反向，跑俩遍出结果。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<map>

 #include<set>

 #include<sstream>

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 const int INF = 1e9 + ;

 int T, n, m, cases;

 int Map[maxn][maxn];

 int d1[maxn], d2[maxn];

 bool v[maxn];

 void flip()

 {

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

     {

         for(int j = i + ; j <= n; j++)swap(Map[i][j], Map[j][i]);

     }

 }

 void dijkstra(int u, int d[])

 {

     memset(v, , sizeof(v));

     for(int i = ; i <= n; i++)d[i] = INF;

     d[u] = ;

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

     {

         int x, m = INF;

         for(int i = ; i <= n; i++)if(!v[i] && d[i] <= m)m = d[x = i];//找距离源点最近的点

         v[x] = ;

         for(int i = ; i <= n; i++)d[i] = min(d[i], d[x] + Map[x][i]);//进行松弛

     }

 }

 int main()

 {

     int u, x, y, z;

     while(cin >> n >> m >> u)

     {

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

             for(int j = ; j <= n; j++)Map[i][j] = (i == j ?  : INF);

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

         {

             scanf("%d%d%d", &x, &y, &z);

             //cout<<"000"<<endl;

             Map[x][y] = z;

         }

         dijkstra(u, d1);

         flip();

         dijkstra(u, d2);

         for(int i = ; i <= n; i++)d1[i] += d2[i];

         sort(d1 + , d1 + n + );

         cout<<d1[n]<<endl;

     }

     return ;

 }

相关文章