kuangbin专题最短路 D

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iomanip>
 5 #include<cmath>
 6 #include<cstdio>
 7 using namespace std;
 8 #define MAXN 1004
 9 #define INF 0x3f3f3f3f
10 /*
11 18 08
12 18 23
13 超时
14 18 24
15 18 33 
16 超时
17 18 41 AC
18 有向图，所有结点中到终点来回距离的最大值
19 对每个节点求最短路得到to[MAXN],对终点求最短路的back[MAXN]
20 n3!超时！
21 只需将有向图反转一次（有向路径反向）,对终点求两次Dijk即可
22 max(to+back)
23 */
24 bool been[MAXN];
25 int lowcost[MAXN],g[MAXN][MAXN],m,n,x,ans=-1;
26 int to[MAXN],back[MAXN];
27 void Read()
28 {
29     int x,y,d;
30     for(int i=0;i<m;i++)
31     {
32         scanf("%d%d%d",&x,&y,&d);
33         g[x][y] = d;
34     }
35 }
36 void Init()
37 {
38     memset(lowcost,INF,sizeof(lowcost));
39     memset(been,false,sizeof(been));
40 }
41 void Dijkstra(int beg,int tmp[])
42 {
43     Init();
44     lowcost[beg] = 0;
45     for(int j=0;j<n;j++)
46     {
47         int Min = INF,k = -1;
48         for(int i=1;i<=n;i++)
49         {
50             if(!been[i]&&lowcost[i]<Min)
51             {
52                 Min = lowcost[i];
53                 k = i;
54             }
55         }
56         if(k==-1) break;
57         been[k] = true;
58         for(int i=1;i<=n;i++)
59         {
60             if(!been[i]&&lowcost[i]>lowcost[k]+g[k][i])
61             {
62                 lowcost[i] = lowcost[k]+g[k][i];
63             }
64         }
65     }
66     for(int i=1;i<=n;i++)
67     {
68         if(i==beg) continue;
69         tmp[i] = lowcost[i];
70     }
71 }
72 int main()
73 {
74     scanf("%d%d%d",&n,&m,&x);
75     memset(g,INF,sizeof(g));
76     Read();
77     Dijkstra(x,back);
78     for(int i=1;i<=n;i++)
79     {
80         for(int j=i+1;j<=n;j++)
81         {
82             int t = g[i][j];
83             g[i][j] = g[j][i];
84             g[j][i] = t;
85         }
86     }
87     Dijkstra(x,to);
88     for(int i=1;i<=n;i++)
89     {
90         ans = max(ans,back[i]+to[i]);
91     }
92     printf("%d
",ans);
93     return 0;
94 }