输入的N条边构成邻接矩阵adj[][]，将边反向，建立返回路径邻接矩阵ret[][]，分别对这两个邻接矩阵运用Dijkstra算法，求到X的最短路，对应顶点两条最短路和的最大值即为所求。
1 #include<iostream>
2 #include<limits>
3
4 using namespace std;
5
6 const int maxN = 1001;
7 const int INF = numeric_limits<int>::max();
8
9 int adj[maxN][maxN]; //去时邻接矩阵
10 int ret[maxN][maxN]; //返回时邻接矩阵
11
12 int res[2][maxN];
13
14 void Dijkstra(int n, int s[][maxN], int dist[],int v)
15 {
16 bool flag[maxN];
17 for(int i=1;i<=n;i++)
18 {
19 flag[i] = false;
20 dist[i] = s[v][i];
21 }
22 dist[v] = 0;
23 flag[v] = true;
24
25 for(int i=1;i<n;i++)
26 {
27 int temp = INF;
28 int u = v;
29 for(int j=1;j<=n;j++)
30 {
31 if((!flag[j]) && dist[j] < temp)
32 {
33 temp = dist[j];
34 u = j;
35 }
36 }
37 flag[u] = true;
38
39 for(int j=1;j<=n;j++)
40 {
41 if((!flag[j]) && s[u][j] != INF)
42 {
43 int newDist = dist[u] + s[u][j];
44 if(newDist < dist[j])
45 {
46 dist[j] = newDist;
47 }
48 }
49 }
50 }
51 }
52
53 int main()
54 {
55 int N,M,X;
56 int a,b,t;
57 int maxT;
58
59 int i,j;
60
61 while(cin>>N>>M>>X)
62 {
63 for(i=1;i<=N;i++)
64 {
65 for(j=1;j<=N;j++)
66 {
67 adj[i][j] = INF;
68 ret[i][j] = INF;
69 }
70 }
71
72 for(i=0;i<M;i++)
73 {
74 cin>>a>>b>>t;
75 adj[a][b] = t;
76 ret[b][a] = t;
77 }
78
79 Dijkstra(N,adj,res[0],X);
80 Dijkstra(N,ret,res[1],X);
81
82 maxT = 0;
83
84 for(i=1;i<=N;i++)
85 {
86 if(maxT < (res[0][i] + res[1][i]))
87 {
88 maxT = res[0][i] + res[1][i];
89 }
90 }
91
92 cout<<maxT<<endl;
93 }
94 }