poj3268 Silver Cow Party（两次SPFA || 两次Dijkstra）

题目链接

题意

有向图中有n个结点，编号1~n，输入终点编号x，求其他结点到x结点来回最短路长度的最大值。

思路

最短路问题，有1000个结点，Floyd算法应该会超时，我刚开始使用的Dijkstra算法也超时，原因是因为我使用一个循环遍历结点1~n，每次遍历我都使用两次Dijkstra求i到x和x到i的最短路，时间复杂度太高。降低时间复杂度的方法是先在原矩阵的基础上使用dijkstra求结点x到其余各点的最短路径，然后将矩阵转置，在转置矩阵的基础上使用dijkstra求结点x到其余各点的最短路径，这就相当于在原矩阵上求其余各点到x的最短路径，将两次得到的最短路径的值相加取最大值即可。这题也可以使用SPFA算法解决。

代码

SPFA算法：

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 #include <vector>
 7 using namespace std;
 8 
 9 struct Edge
10 {
11     int s, e, dist;
12 
13     Edge() {}
14     Edge(int s, int e, int d) :s(s), e(e), dist(d) {}
15 };
16 
17 const int INF = 0x3f3f3f;
18 const int N = 1000 + 10;
19 vector<Edge> v[N];
20 int dist[N];
21 int visit[N];
22 int n, m, x;
23 
24 int spfa(int s, int e)    //返回从结点s到结点e的最短路
25 {
26     queue<int> q;
27     memset(visit, 0, sizeof(visit));
28     memset(dist, INF, sizeof(dist));
29     q.push(s);
30     visit[s] = 1;
31     dist[s] = 0;
32 
33     while (!q.empty())
34     {
35         int s = q.front();
36         q.pop();
37         visit[s] = 0;
38         for (int i = 0; i < v[s].size(); i++)
39         {
40             int e = v[s][i].e;
41             if (dist[e] > dist[s] + v[s][i].dist)
42             {
43                 dist[e] = dist[s] + v[s][i].dist;
44                 if (!visit[e])
45                 {
46                     visit[e] = 1;
47                     q.push(e);
48                 }
49             }
50         }
51     }
52     return dist[e];
53 }
54 
55 int main()
56 {
57     //freopen("poj3268.txt", "r", stdin);
58     while (scanf("%d%d%d", &n, &m, &x) == 3)
59     {
60         int a, b, d;
61         for (int i = 0; i < m; i++)
62         {
63             scanf("%d%d%d", &a, &b, &d);
64             v[a].push_back(Edge(a, b, d));
65         }
66         int ans = -1;
67         for (int i = 1; i <= n; i++)
68         {
69             if (i != x)
70             {
71                 int dist1 = spfa(i, x);
72                 int dist2 = spfa(x, i);
73                 ans = max(ans, dist1 + dist2);
74             }
75         }
76         printf("%d
", ans);
77     }
78     return 0;
79 }

Dijkstra算法：

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 const int INF = 0x3f3f3f;
 8 const int N = 1000 + 10;
 9 int map[N][N];
10 int dist[N], reverse_dist[N];    //记录x到其余各点的最短路径，和其余各点到x的最短路径
11 int visit[N];
12 int n, m, x;
13 
14 void dijkstra(int s)
15 {
16     memset(visit, 0, sizeof(visit));
17     for (int i = 1; i <= n; i++)
18         dist[i] = map[s][i];
19     dist[s] = 0;
20     visit[s] = 1;
21 
22     int min_dist, now = s;
23     for (int i = 1;i <= n; i++)
24     {
25         min_dist = INF;
26         for (int j = 1; j <= n; j++)
27         {
28             if (!visit[j] && dist[j] < min_dist)
29             {
30                 min_dist = dist[j];
31                 now = j;
32             }
33         }
34         if (min_dist == INF) break;
35         visit[now] = 1;
36         for (int j = 1; j <= n; j++)
37             dist[j] = min(dist[j], dist[now] + map[now][j]);
38     }
39 }
40 
41 void reverse_map()    //将原矩阵转置
42 {
43     for (int i = 1;i <= n; i++)
44     {
45         for (int j = i + 1; j <= n; j++)
46         {
47             int t = map[i][j];
48             map[i][j] = map[j][i];
49             map[j][i] = t;
50         }
51     }
52 }
53 
54 int main()
55 {
56     //freopen("poj3268.txt", "r", stdin);
57     while (scanf("%d%d%d", &n, &m, &x) == 3)
58     {
59         memset(map, INF, sizeof(map));
60         int a, b, d;
61         for (int i = 0; i < m; i++)
62         {
63             scanf("%d%d%d", &a, &b, &d);
64             map[a][b] = d;
65         }
66         dijkstra(x);
67         for (int i = 1; i <= n; i++)
68             reverse_dist[i] = dist[i];
69         reverse_map();
70         dijkstra(x);
71         int ans = -1;
72         for (int i = 1; i <= n; i++)
73             if (i != x)
74                 ans = max(ans, dist[i] + reverse_dist[i]);
75         printf("%d
", ans);
76     }
77     return 0;
78 }