青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(1010) 評論(0)  編輯 收藏 引用

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

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美资源在线| 在线成人激情视频| 99亚洲精品| 亚洲激情国产| 欧美精品在线观看| 亚洲欧美日韩成人高清在线一区| 亚洲亚洲精品三区日韩精品在线视频 | 久久精品国产精品亚洲精品| 午夜影视日本亚洲欧洲精品| 精品成人一区二区三区| 91久久久精品| 国产伦精品一区二区三区免费迷| 久久久久久网| 欧美激情在线播放| 欧美在线视频观看| 欧美www在线| 午夜免费日韩视频| 玖玖精品视频| 亚洲欧美国产高清| 蜜臀99久久精品久久久久久软件 | 国产在线视频欧美| 亚洲精品系列| 精久久久久久| 亚洲少妇在线| 亚洲电影免费观看高清完整版在线观看 | 亚洲第一在线视频| 国产精品hd| 欧美高清在线视频观看不卡| 欧美性片在线观看| 欧美肥婆在线| 国产色产综合色产在线视频| 亚洲国产婷婷| 国产一区二区三区电影在线观看| 亚洲精品日韩在线观看| 一区二区三区在线免费视频| 中文一区在线| 一级成人国产| 蜜臀av性久久久久蜜臀aⅴ四虎| 午夜在线不卡| 欧美日韩综合不卡| 亚洲丁香婷深爱综合| 国产综合精品一区| 亚洲中无吗在线| 亚洲少妇自拍| 欧美日韩大片| 亚洲国产视频直播| 亚洲国产精品福利| 久久久久久黄| 久久久青草婷婷精品综合日韩 | 亚洲国产国产亚洲一二三| 午夜精品影院| 欧美一区二区黄色| 国产精品女人网站| 亚洲无线视频| 亚洲欧美日韩第一区 | 欧美在线欧美在线| 欧美影院视频| 国产日韩综合一区二区性色av| 亚洲一区免费在线观看| 亚洲一区在线观看免费观看电影高清| 欧美成人综合| 亚洲欧洲日韩综合二区| 99国产精品久久久久久久| 欧美精品久久久久久久免费观看| 欧美激情中文字幕乱码免费| 亚洲三级色网| 欧美精品一区在线| 一区二区三区欧美在线| 亚洲男人的天堂在线观看 | 欧美18av| 亚洲免费观看高清完整版在线观看熊 | 免费日韩视频| 亚洲精品久久久久中文字幕欢迎你| 亚洲另类春色国产| 欧美日本免费| 午夜电影亚洲| 美女精品在线| 亚洲毛片在线看| 欧美日韩一级片在线观看| 亚洲一区二区3| 久久久人人人| 亚洲最黄网站| 国产日韩欧美综合一区| 久久一区二区三区国产精品| 亚洲国产综合91精品麻豆| 亚洲无线视频| 国内精品久久久久影院色 | 国产日韩欧美日韩大片| 久久久久久久久久码影片| 亚洲高清资源| 性色av一区二区三区在线观看| 国产一区二区三区在线观看网站| 久久综合狠狠综合久久激情| 日韩视频免费观看高清在线视频 | 欧美一级二区| 亚洲国产专区校园欧美| 欧美一级淫片播放口| 亚洲福利av| 国产精品美女久久久| 麻豆九一精品爱看视频在线观看免费| 夜夜嗨av色综合久久久综合网| 久久精品国产91精品亚洲| 99天天综合性| 国产一区三区三区| 欧美视频免费| 美女国产精品| 欧美怡红院视频一区二区三区| 亚洲人成网站777色婷婷| 久久久久女教师免费一区| 一本色道久久88亚洲综合88| 狠狠色2019综合网| 国产精品欧美日韩一区二区| 欧美成人午夜| 久久美女性网| 欧美一区二区三区在线视频 | 91久久在线| 美女福利精品视频| 久久国产精品久久久久久电车| 日韩天堂av| 91久久久久久久久| 黑人巨大精品欧美黑白配亚洲| 国产精品第2页| 欧美日韩中文字幕综合视频| 欧美二区乱c少妇| 久久久中精品2020中文| 欧美在线视频一区| 亚洲欧美日韩在线一区| 亚洲少妇自拍| 亚洲视频一区在线| 一区二区高清视频在线观看| 亚洲精选成人| 日韩系列欧美系列| 亚洲伦理在线| 日韩网站在线观看| 亚洲精品视频一区| 日韩午夜三级在线| 日韩一区二区电影网| 日韩一区二区精品| 国产精品99久久不卡二区| 亚洲精品中文字幕有码专区| 亚洲精品视频在线观看网站| 亚洲另类黄色| 一区二区三区精品国产| 亚洲一本大道在线| 亚洲一区二区三区免费观看| 亚洲欧美日韩精品在线| 欧美一级午夜免费电影| 久久久不卡网国产精品一区| 久久精品国产欧美亚洲人人爽| 久久看片网站| 欧美国产精品劲爆| 欧美午夜片在线观看| 国产欧美亚洲一区| 黑人中文字幕一区二区三区| 亚洲福利视频免费观看| 亚洲精品乱码久久久久| 国产精品99久久不卡二区| 亚洲欧美日韩综合| 久久久九九九九| 欧美韩日一区二区三区| 亚洲靠逼com| 欧美一区午夜精品| 女人天堂亚洲aⅴ在线观看| 欧美日韩国产一区精品一区 | 99一区二区| 欧美尤物巨大精品爽| 欧美va天堂| 亚洲午夜国产成人av电影男同| 欧美一级久久久| 欧美国产精品一区| 国产欧美91| 亚洲毛片av在线| 久久国产色av| 亚洲精品1区| 欧美在线free| 欧美日韩在线三区| 黄色亚洲在线| 一区二区三区日韩在线观看 | 日韩午夜在线观看视频| 久久国产日本精品| 亚洲激情第一页| 久久国产色av| 国产精品国产精品| 亚洲国产美女精品久久久久∴| 亚洲欧美一级二级三级| 欧美激情一区二区三区全黄| 亚洲欧美另类在线观看| 欧美激情精品久久久久| 国内成人在线| 午夜视频在线观看一区二区| 亚洲欧洲综合另类| 久久综合国产精品台湾中文娱乐网| 国产精品久久久久久模特| 亚洲精品乱码久久久久| 噜噜噜久久亚洲精品国产品小说| 一区二区三区四区蜜桃| 欧美黄在线观看| 亚洲福利在线视频| 麻豆成人在线观看| 欧美在线视频观看|