Lost City
Time Limit: 1000 MS Memory Limit: 65536 K
Total Submit: 68 Accepted: 14
Description
Bob and Alice are visiting the “lost city”. It’s said that the guys who visit the city will be lost without the help of native. Bob is very interested in the story, and decides to travel alone. Can Bob break his destination?
Of course, Bob is prepared for his travel. No one want to be lost, is it? Bob marks every road he has visited so that he will never visit it a second time.
Hours later, Bob has finally arrived at the position where he started his trip. Bob is so tired now and get back to the hotel to have a sleep immediately without telling Alice the path he has traveled in. Given the map, you are to help Alice calculate at least how far Bob has traveled.
Input
The input contains multiple test cases.
For each test case, it contains n+1 lines.
Line 1: two integers m, n (1<= m <= 50, 1 <= n <= 2000) indicating that there are m cross and n roads in the city.
Line 2~n+1: each contains three integers i, j,d ( 1 <= i, j <= m , 1<= d <=100), indicating that there is a two way road connecting cross i and cross j.
Bob starts from cross 1.
Output
Output the length of the shortest path Bob can travel. If there is no way Bob can finish his trip, just output “-1”
Sample Input
3 4
1 2 3
2 3 2
3 1 4
2 2 4
Sample Output
9
Source
langlang@hust
2009年7月25日
分類：最小環(huán)，dijkastra
題目分析與算法原型
這道題目來(lái)自地大OJ，相當(dāng)郁悶，WA了幾十次，題目有很多陷阱，比方說(shuō)，重邊，還有自環(huán)，其次，重邊的時(shí)候處理還不能單單記錄最小的那條，因?yàn)轭}目是求從1節(jié)點(diǎn)出發(fā)回到1的最小環(huán)，所以極有可能會(huì)有這樣的情況出現(xiàn)，從1到某個(gè)節(jié)點(diǎn)x,有多條重邊，然后這個(gè)時(shí)候 從1出發(fā)經(jīng)過(guò)某條邊到達(dá)x,然后又繞著他們之間另外的一條邊回到1，這樣子也算一個(gè)環(huán)，這個(gè)地方當(dāng)初一直沒(méi)考慮到，因此貢獻(xiàn)了好幾次WA，然后自環(huán)的地方也錯(cuò)了好幾次，最后，是flag[]數(shù)組初始化的錯(cuò)誤，導(dǎo)致自己一直找不出來(lái)，淚奔.......
這道題目的大致做法如下：枚舉每個(gè)和1相鄰的點(diǎn)，然后刪掉他們之間的這條邊，做一次Dijkastra，記錄下他們之間的最短路徑，將該路徑加上刪除邊的長(zhǎng)度就是一個(gè)經(jīng)過(guò)1的環(huán)的長(zhǎng)度，保存下來(lái)，然后加回原來(lái)的那條邊，按此方法繼續(xù)，直到將所有的與1相鄰的點(diǎn)的枚舉一遍并且記錄下相應(yīng)的環(huán)值大小
注意：對(duì)于自環(huán)，只用記錄1到1這樣的自環(huán)（如果有，可能有多個(gè)，記錄最小的那個(gè)的值），其他的點(diǎn)的自環(huán)不用考慮，可以直接略掉，因?yàn)椴挥绊懕绢}；還有對(duì)于重邊的處理是，記錄兩個(gè)點(diǎn)之間（如果有多條重邊）最小和次小的那兩條邊的長(zhǎng)度，然后將他們的和跟剛才計(jì)算的環(huán)的值做比較，取小的那個(gè)作為該環(huán)的最后的值，最后取所有環(huán)中最小的那個(gè)（如果有1到1的自環(huán)，則還有跟該自環(huán)的長(zhǎng)度做一次比較，取較小的值）輸出
Code:
1
#include<stdio.h>
2#include<string.h>
3
4#define max 1000000000
5
6#define len 55
7
8int i, j, map[len][len], dis[len], flag[len],m,n,u,_dis[len],res,pos[len][2];
9bool finish;
10
11void init()
12
{
13
for(i=1;i<=m;i++)
14 for(j=1;j<=m;j++)
15
{
16 if(i==j)map[i][j]=0;
17 else map[i][j]=max;
18
19 pos[j][0]=max;
20 pos[j][1]=max;
21 _dis[j]=max;
22
}
23
}
24
25void dij(int v0)
26{
27 for(i=1;i<=m;i++) dis[i]=map[v0][i];
28 flag[v0]=1;
29
30 for(i=1;i<m;i++)
31 {
32 int min=max;
33 for(j=1;j<=m;j++)
34 if(flag[j]==0&&dis[j]<min)
35 {
36 u=j;
37 min=dis[j];
38 }
39
40 if(min==max)return ;
41 flag[u]=1;
42 for(j=1;j<=m;j++)
43 if(flag[j]==0&&map[u][j]<max&&dis[u]+map[u][j]<dis[j])
44 dis[j]=dis[u]+map[u][j];
45 }
46}
47
48void DIJ()
49{
50 int p;
51 for(p=2;p<=m;p++)
52 {
53 if(map[1][p]<max)
54 {
55 int tt=map[1][p];
56 map[1][p]=max;
57 map[p][1]=max;
58 memset(flag,0,sizeof(flag));
59 dij(1);
60 _dis[p]=dis[p];
61 map[1][p]=tt;
62 map[p][1]=tt;
63 }
64 }
65}
66
67int main()
68{
69 while(scanf("%d%d",&m,&n)!=EOF)
70 {
71 init();
72 finish=false;
73 res = max;
74 for(i=0;i<n;i++)
75 {
76 int a,b,d;
77 scanf("%d%d%d",&a,&b,&d);
78
79 if(a==1&&b==1)
80 {
81 finish=true;
82 if(d < res) res=d;
83 }
84 else if(a!=b)
85 {
86 if(d<map[a][b])
87 {
88 map[a][b]=d;
89 map[b][a]=d;
90 }
91 if(a>b)
92 {
93 int t;
94 t=a,a=b,b=t;
95 }
96 if(a==1)
97 {
98 int t=pos[b][0];
99 if(d<t)
100 {
101 pos[b][0]=d;
102 pos[b][1]=t;
103 }
104 else if(d>=t && d<pos[b][1])pos[b][1]=d;
105 }
106 }
107 }
108
109 DIJ();
110 int _min=max;
111
112 for(i=2;i<=m;i++)
113 {
114 if(map[1][i]<max)
115 {
116 if(_dis[i]<max)
117 if(_dis[i]+map[1][i]<_min)_min=_dis[i]+map[1][i];
118
119 if(pos[i][0]+pos[i][1]<_min)_min=pos[i][0]+pos[i][1];
120 }
121 }
122
123 if(finish)
124 if(res<_min)_min=res;
125
126 if(_min<max) printf("%d\n",_min);
127 else printf("-1\n");
128 }
129
130 return 0;
131}