coj 1115

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日

分类:最小环,dijkastra

题目分析与算法原型
        这道题目来自地大OJ,相当郁闷,WA了几十次,题目有很多陷阱,比方说,重边,还有自环,其次,重边的时候处理还不能单单记录最小的那条,因为题目是求从1节点出发回到1的最小环,所以极有可能会有这样的情况出现,从1到某个节点x,有多条重边,然后这个时候 从1出发经过某条边到达x,然后又绕着他们之间另外的一条边回到1,这样子也算一个环,这个地方当初一直没考虑到,因此贡献了好几次WA,然后自环的地方也错了好几次,最后,是flag[]数组初始化的错误,导致自己一直找不出来,泪奔.......
       这道题目的大致做法如下:枚举每个和1相邻的点,然后删掉他们之间的这条边,做一次Dijkastra,记录下他们之间的最短路径,将该路径加上删除边的长度就是一个经过1的环的长度,保存下来,然后加回原来的那条边,按此方法继续,直到将所有的与1相邻的点的枚举一遍并且记录下相应的环值大小
      注意:对于自环,只用记录1到1这样的自环(如果有,可能有多个,记录最小的那个的值),其他的点的自环不用考虑,可以直接略掉,因为不影响本题;还有对于重边的处理是,记录两个点之间(如果有多条重边)最小和次小的那两条边的长度,然后将他们的和跟刚才计算的环的值做比较,取小的那个作为该环的最后的值,最后取所有环中最小的那个(如果有1到1的自环,则还有跟该自环的长度做一次比较,取较小的值)输出

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>=&& 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}
 

posted on 2009-07-25 20:53 蜗牛也Coding 阅读(933) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜