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