这是在一个叫做九度的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 }
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算法的分析，之后找到的到达终点的路径长度只会比最小路径更长，不会再次相等。