题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1797
题目描述：求从指定起点到指定终点每条可能路径上各段边的最小值
注意事项：有向图／无向图
提交情况：3次Runtime Error，是最开始尝试用Kruskal时间接排序的数组r大小只开了MAXN个；3次WA的主要原因是无向图按照有向图做的。用邻接表存储图时一定要注意有向图和无向图的问题，已经出错好几次了。
心得体会：本道题实际是按照Prim求最大生成树的思路，逐条添加边；在添加的过程中，注意从1点出发，在遇到n时，即使最大生成树仍没有构造完，也可以从函数中返回了。最开始以为是简单的生成树问题，所有用Kruskal来作，遇到起点和终点都访问过就退出，但此时，构造的生成树可能根本就没有连接，而Prim在构造的初始就是从一棵树开始拓展的，不会出现这个问题。需要对每个具体的算法有更深入的理解。
1 #include<queue>
2 #include<stdio.h>
3 #include<string.h>
4 using namespace std;
5
6 #define MAXN 1010
7 #define MAXM 1000010
8
9 struct Edge
10 {
11 int start;
12 int end;
13 int weight;
14
15 bool operator>(const Edge &e) const
16 {
17 return weight<e.weight;
18 }
19 };
20
21 Edge edge[2*MAXM];
22 int visited[MAXN];
23 int first[MAXN];
24 int next[2*MAXM];
25
26 int Prim(int n)
27 {
28 memset(visited,0,sizeof(visited));
29 int result = 10000000;
30 priority_queue<Edge,vector<Edge>,greater<Edge> > pq;
31 for(int e=first[1];e!=-1;e=next[e])
32 {
33 pq.push(edge[e]);
34 }
35 visited[1]=1;
36
37 while(!pq.empty())
38 {
39 int start = pq.top().start;
40 int end = pq.top().end;
41 int weight = pq.top().weight;
42 pq.pop();
43
44 if(visited[end]==1)
45 continue;
46 visited[end] = 1;
47
48 if(weight<result)
49 result = weight;
50 if(end==n)
51 break;
52 for(int e=first[end];e!=-1;e=next[e])
53 {
54 if(visited[edge[e].end]==0)
55 {
56 pq.push(edge[e]);
57 }
58 }
59 }
60 return result;
61 }
62
63 int main()
64 {
65 int snum;
66 scanf("%d",&snum);
67 for(int i=1;i<=snum;i++)
68 {
69 int n,m,start,end,weight;
70 scanf("%d%d",&n,&m);
71
72 memset(first,-1,sizeof(first));
73 for(int j=0;j<2*m;j+=2)
74 {
75 scanf("%d%d%d",&start,&end,&weight);
76
77 edge[j].start = start;
78 edge[j].end = end;
79 edge[j].weight = weight;
80
81 edge[j+1].start = end;
82 edge[j+1].end = start;
83 edge[j+1].weight = weight;
84
85 next[j] = first[start];
86 first[start] = j;
87
88 next[j+1] = first[end];
89 first[end] = j+1;
90
91 }
92
93 int result = Prim(n);
94 printf("Scenario #%d:\n",i);
95 printf("%d\n\n",result);
96 }
97 }