2009年7月26日
題目鏈接：PKU 3268 Silver Cow Party
分類：一道巧妙的Dijkastra
題目分析與算法
這道題目最容易想的就是Floyd,但是其n3的復雜度顯然會超時，我當時拿到這題的時候，想都沒想，直接以x為源點一次Dijkastra，然后在一遍循環分別以除x外的其他點為起始點做Dijkastra，然后相加，結果自然使TLE了，復雜度太高了，做了太多遍的Dijkastra,后來看了討論，發現原來兩遍Dijkastra就行了，第一次還是以x為開始的點做一遍，記錄從x出發到其他所有點的最短路徑長度，然后將每條有向路徑反過來（即是將矩陣轉置一下）還是以x為起點再做一遍Dijkastra即可了，至于為什么這樣子，我們可以這樣想，第一次Dijkastra我門已經計算出來從x到其他的點的最短路徑了，現在我們要算的就是其他除x外的每個點到x的最短路徑，對于每個點如果其到x的最短路徑為path，那么顯然我們將所有路徑置反后從x開始沿剛的path返回的路徑的長度顯然和path是一樣的，只是方向不同了，那么當我們將所有路徑置反了后再調用一遍以x為起點的Dijkastra，求出的dis[i]，正好就是第i個點到x的最短路徑，再從所有兩次相加的和中取最大的輸出即可。
Code:
1
#include<stdio.h>
2#define len 1005
3#define max 1000000000
4
5int map[len][len],dis[len],cost[len],n,m,x;
6
7void init()
8
{
9
int i,j;
10 for(i=1;i<=n;i++)
11 for(j=1;j<=n;j++)
12
{
13 if(i==j)map[i][j]=0;
14 else map[i][j]=max;
15
}
16
}
17void dij(int v0)
18{
19 int i,j,u,visit[len]={0};
20 for(i=1;i<=n;i++)dis[i]=map[v0][i];
21 visit[v0]=1;
22 for(i=1;i<n;i++)
23 {
24 int min=max;
25 for(j=1;j<=n;j++)
26 if(!visit[j]&&dis[j]<min)
27 {
28 u=j;
29 min=dis[j];
30 }
31 if(min==max)return ;
32 visit[u]=1;
33 for(j=1;j<=n;j++)
34 if(!visit[j]&&map[u][j]<max&&dis[u]+map[u][j]<dis[j])
35 dis[j]=dis[u]+map[u][j];
36 }
37}
38int main()
39{
40 int i,j;
41 while(scanf("%d%d%d",&n,&m,&x)!=EOF)
42 {
43 init();
44 for(i=1;i<=m;i++)
45 {
46 int a,b,t;
47 scanf("%d%d%d",&a,&b,&t);
48 if(t<map[a][b])map[a][b]=t;
49 }
50 dij(x);
51 for(i=1;i<=n;i++)
52 if(i!=x)cost[i]=dis[i];
53
54 for(i=1;i<=n;i++) //將有向路徑取反，也就是矩陣轉置
55 for(j=i+1;j<=n;j++)
56 {
57 int tt=map[i][j];
58 map[i][j]=map[j][i];
59 map[j][i]=tt;
60 }
61 dij(x);
62 for(i=1;i<=n;i++)
63 if(i!=x)cost[i]+=dis[i];
64
65 int res=-1;
66 for(i=1;i<=n;i++)
67 if(i!=x&&cost[i]>res)res=cost[i];
68 printf("%d\n",res);
69 }
70 return 0;
71}
72
73