題目鏈接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1797
題目描述：求從指定起點(diǎn)到指定終點(diǎn)每條可能路徑上各段邊的最小值
注意事項(xiàng)：有向圖／無向圖
提交情況：3次Runtime Error，是最開始嘗試用Kruskal時(shí)間接排序的數(shù)組r大小只開了MAXN個(gè)；3次WA的主要原因是無向圖按照有向圖做的。用鄰接表存儲(chǔ)圖時(shí)一定要注意有向圖和無向圖的問題，已經(jīng)出錯(cuò)好幾次了。
心得體會(huì)：本道題實(shí)際是按照Prim求最大生成樹的思路，逐條添加邊；在添加的過程中，注意從1點(diǎn)出發(fā)，在遇到n時(shí)，即使最大生成樹仍沒有構(gòu)造完，也可以從函數(shù)中返回了。最開始以為是簡單的生成樹問題，所有用Kruskal來作，遇到起點(diǎn)和終點(diǎn)都訪問過就退出，但此時(shí)，構(gòu)造的生成樹可能根本就沒有連接，而Prim在構(gòu)造的初始就是從一棵樹開始拓展的，不會(huì)出現(xiàn)這個(gè)問題。需要對(duì)每個(gè)具體的算法有更深入的理解。
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 }