这是在一个叫做九度的OJ上面的题，这是一个典型的最短路问题。题目很简单，就只有一个要注意的地方，就是路径有可能是重复的，要把这种情况考虑进去。我就是为此WA了好几次，最后只好参考那里的BBS，才知道原来这题是要检测重复路径的。改了以后就立刻AC了！
这题是我第一次用Dij算法做的题，因为以前都只会Floyd算法，用在这里后就TLE了一次，因为这里有1000个点，如果用Floyd的话，O(n^3)在就是最少10^9次运算了。后来想起了Dij的算法，然后根据我印象中对Dij算法的思路，打了我第一个Dij算法的代码。
下面是我的代码，也是像其他题解一样，在旁边有注解的。如果觉得有什么不明白，或者有更好的优化方法，欢迎留言~
View Code 1 #include<stdio.h> 2 #include< string.h> 3 #include<stdlib.h> 4 #define MAX 9999999999999999 // 刚开始不停的WA，我以为是int不够大，所以直接用了long long 5 6 typedef struct arc // 这是用来储存弧信息的结构体的定义 7 { 8 int end; 9 long long dis; 10 long long cost; 11 struct arc *next; 12 }Arc; 13 14 Arc *begin[ 1005]; // 起点相同的弧放在一起，顺序查找 15 long long dis[ 1005]; // 这是从起点到各个点的距离 16 long long cost[ 1005]; // 从起点到各个点的花费 17 int visited[ 1005]; // 点是否确定了 18 19 int findmin( int n) // 找出与起点的距离最小的那一点，返回点的标号 20 { 21 int i; 22 long long min=MAX; 23 int num= 0; 24 25 for(i= 1; i<=n; i++) 26 if(!visited[i]&&min>dis[i])min=dis[i], num=i; // 如果是确定了的点就不要重复返回了 27 return num; 28 } 29 30 int main() 31 { 32 int i; 33 int n, m; 34 int a, b; 35 long long c, d; // cost,distance 36 Arc *p, *tmp; 37 38 while(scanf( " %d%d ", &n, &m)&&(n||m)) 39 { 40 memset(begin, 0, sizeof(begin)); 41 memset(visited, 0, sizeof(visited)); 42 43 for(i= 1; i<= 1003; i++) 44 cost[i]=dis[i]=MAX; 45 while(m--) 46 { 47 scanf( " %d%d%lld%lld ", &a, &b, &d, &c); // 因为这是无向图所以两个方向都要设置 48 tmp=(Arc *)malloc( sizeof(Arc)); 49 tmp->next=begin[a]; 50 tmp->end=b; 51 tmp->dis=d; 52 tmp->cost=c; 53 begin[a]=tmp; 54 tmp=(Arc *)malloc( sizeof(Arc)); 55 tmp->next=begin[b]; 56 tmp->end=a; 57 tmp->dis=d; 58 tmp->cost=c; 59 begin[b]=tmp; 60 } 61 62 scanf( " %d%d ", &a, &b); 63 c=d=MAX; // 额……突然发现这是多余的 64 visited[a]= 1; 65 p=begin[a]; 66 dis[a]=cost[a]= 0; 67 while(p) // 把各点信息放进dis和cost数组，因为可能有重复的路径，所以这里也是要比较大小的 68 { 69 if(dis[p->end]>dis[a]+p->dis) 70 dis[p->end]=dis[a]+p->dis, 71 cost[p->end]=cost[a]+p->cost; 72 else if(dis[p->end]==dis[a]+p->dis&&cost[p->end]>cost[a]+p->cost) 73 cost[p->end]=cost[a]+p->cost; 74 p=p->next; 75 } 76 while(i=findmin(n)) 77 { 78 visited[i]= 1; 79 p=begin[i]; 80 while(p) 81 { 82 if(dis[p->end]>dis[i]+p->dis) 83 dis[p->end]=dis[i]+p->dis, 84 cost[p->end]=cost[i]+p->cost; 85 else if(dis[p->end]==dis[i]+p->dis&&cost[p->end]>cost[i]+p->cost) 86 cost[p->end]=cost[i]+p->cost; 87 p=p->next; 88 } 89 } 90 printf( " %lld %lld\n ", dis[b], cost[b]); 91 } 92 93 return 0; 94 }
Dij算法还是得多点用，否则到真的比赛的时候就会浪费太多时间了！
written by Lyon
beta 1：
可以在上面代码的第77和78行之间加上
if(i==b)break;
这样的目的是找到最小路以后直接跳出，做到剪枝优化的效果。因为根据dij算法的分析，之后找到的到达终点的路径长度只会比最小路径更长，不会再次相等。