POJ-3268.SilverCowParty.(最短路 + 图的转置)

　　本题思路：对原图和原图的逆图分别用一次最短路，找出最大值即可。

一开始是我是对每个顶点spfa搜了一波，结果判题时间巨长，还好这个题的数据量不是很大，所以就用了另一种思路。

　　参考代码：spfa单结点爆搜版

 1 #include <iostream>
 2 #include <cstring>
 3 #include <vector>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 1000 + 5, INF = 0x3f3f3f3f;
 9 struct edge {
10     int to, cost;
11 };
12 int n, m, x, ans, dist[maxn];
13 vector<edge> G[maxn];
14 bool vis[maxn];
15 
16 void addedge(int u, int v, int w) {
17     G[u].push_back({v, w});
18 }
19 
20 int spfa(int source, int aid) {
21     memset(vis, false, sizeof vis);
22     for(int i = 1; i <= n; i ++)
23         dist[i] = (i == source ? 0 : INF);
24     queue <int> Q;
25     Q.push(source);
26     vis[source] = true;
27     while(!Q.empty()) {
28         int now = Q.front();
29         Q.pop();
30         for(int i = 0; i < G[now].size(); i ++) {
31             edge e = G[now][i];
32             if(dist[e.to] > dist[now] + e.cost) {
33                 dist[e.to] = dist[now] + e.cost;
34                 if(!vis[e.to]) Q.push(e.to);
35             }
36         }
37     }
38     return dist[aid];
39 }
40 
41 int main () {
42     ans = 0;
43     int u, v, w;
44     cin >> n >> m >> x;
45     for(int i = 1; i <= m; i ++) {
46         cin >> u >> v >> w;
47         addedge(u, v, w);
48     }
49     for(int i = 1; i <= n; i ++)
50         ans = max(spfa(i, x) + spfa(x, i), ans);
51     cout << ans << endl;
52     return 0;
53 }

View Code

　　对原图和逆图分别进行一次Dijkstra的终极版本

 1 #include <iostream>
 2 #include <cstring>
 3 #include <vector>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 1000 + 5, INF = 0x3f3f3f3f;
 9 struct edge {
10     int to, cost;
11 };
12 int n, m, x, k, ans, dist1[maxn], dist2[maxn], G[maxn][maxn];;
13 bool vis[maxn];
14 
15 void Dijkstra(int lowcost[]) {
16     for(int i = 1; i <= n; i ++)
17         lowcost[i] = INF;
18     lowcost[x] = 0;
19     memset(vis, false, sizeof vis);
20     for(int i = 1; i <= n; i ++) {
21         int minf = INF;
22         for(int j = 1; j <= n; j ++) 
23             if(minf > lowcost[j] && !vis[j]) {
24                 k = j;
25                 minf = lowcost[j];
26             }
27         vis[k] = true;
28         for(int j = 1; j <= n; j ++)
29             if(!vis[j] && lowcost[j] > lowcost[k] + G[k][j])
30                 lowcost[j] = lowcost[k] + G[k][j];
31     }
32 }
33 
34 int main () {
35     ans = 0;
36     int u, v, w;
37     cin >> n >> m >> x;
38     for(int i = 1; i <= n; i ++)    
39         for(int j = 1; j <= n; j ++)
40             if(i == j) G[i][j] = 0;
41             else G[i][j] = INF;
42     for(int i = 1; i <= m; i ++) {
43         cin >> u >> v >> w;
44         G[u][v] = min(G[u][v], w);
45     }
46     Dijkstra(dist1);
47     for(int i = 1; i <= n; i ++)
48         for(int j = 1; j < i; j ++)
49             if(G[i][j]) swap(G[i][j], G[j][i]);
50     Dijkstra(dist2);
51     for(int i = 1; i <= n; i ++)
52         ans = max(ans, dist1[i] + dist2[i]);
53     cout << ans << endl;
54     return 0;
55 }

View Code