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

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| 久久国产精品久久久| 一区二区在线观看视频| 欧美激情1区| 欧美日韩亚洲在线| 欧美一区三区三区高中清蜜桃 | 亚洲国产精彩中文乱码av在线播放| 久久国产精品电影| 亚洲欧洲另类国产综合| 日韩视频在线观看| 国产精品丝袜白浆摸在线| 久久久7777| 欧美日韩成人综合| 久久精品人人做人人综合| 老牛国产精品一区的观看方式| 亚洲精品日产精品乱码不卡| 亚洲午夜影视影院在线观看| 黄色亚洲网站| 日韩视频中文| 激情欧美亚洲| 在线视频欧美日韩| 亚洲电影成人| 亚洲欧美日韩国产综合在线| 亚洲国产免费| 亚洲欧美日韩在线| 亚洲麻豆视频| 久久久国产一区二区三区| 一本大道久久a久久精二百| 亚洲女与黑人做爰| 日韩天堂av| 久久久久久久久伊人| 一区二区精品国产| 久久夜色精品国产噜噜av| 亚洲欧美日韩中文在线制服| 欧美xxx在线观看| 久久精品人人做人人综合| 欧美日韩国产三级| 欧美第一黄色网| 激情成人综合网| 亚洲一区二区三区乱码aⅴ| 亚洲欧洲视频在线| 久久夜色精品国产欧美乱极品| 亚洲欧美在线aaa| 欧美日韩国产一区精品一区 | 麻豆精品一区二区av白丝在线| 国产精品wwwwww| 亚洲欧洲在线播放| 亚洲第一精品夜夜躁人人躁| 欧美在线视频免费| 亚洲一区二区视频在线观看| 欧美成人综合| 欧美大胆人体视频| 亚洲东热激情| 裸体女人亚洲精品一区| 久久欧美中文字幕| 国产一区二区三区av电影| 一区二区三区欧美成人| 亚洲系列中文字幕| 欧美日韩综合网| 国产精品99久久久久久久vr | 久久久久一区| 国产日韩欧美在线观看| 亚洲免费中文| 久久精品系列| 国内精品免费午夜毛片| 欧美专区亚洲专区| 免费久久99精品国产自| 在线观看亚洲精品视频| 免费看的黄色欧美网站| 欧美成人精品在线观看| 亚洲国产毛片完整版 | 日韩亚洲综合在线| 在线一区亚洲| 国产乱码精品一区二区三区不卡| 亚洲欧美视频在线观看视频| 欧美一区三区三区高中清蜜桃 | 欧美精品久久99久久在免费线| 亚洲激情精品| 亚洲午夜视频| 国产资源精品在线观看| 老司机一区二区三区| 亚洲激情在线| 亚洲欧美激情四射在线日 | 欧美一区二区三区四区在线| 国产一区三区三区| 久久亚洲精品伦理| 亚洲美女视频在线免费观看| 欧美一区二区三区四区在线观看地址 | 欧美日韩国语| 亚洲欧美www| 欧美高清视频在线观看| 夜夜精品视频| 狠狠做深爱婷婷久久综合一区| 美女脱光内衣内裤视频久久网站| 亚洲美女av电影| 久久都是精品| 99re6热在线精品视频播放速度| 国产精品一区二区女厕厕| 久久久久久穴| 亚洲一级特黄| 亚洲激情图片小说视频| 欧美一区二区三区四区视频| 亚洲人www| 国产亚洲观看| 欧美激情成人在线| 久久se精品一区精品二区| 91久久线看在观草草青青| 久久精品二区三区| 中文精品一区二区三区| 永久域名在线精品| 国产精品视频精品视频| 欧美成人有码| 久久综合久久综合九色| 亚洲一区二区三区免费视频 | 亚洲一区综合| 亚洲欧洲日本在线| 精品电影一区| 国产女人精品视频| 欧美特黄视频| 欧美日本中文字幕| 欧美成在线视频| 麻豆成人91精品二区三区| 香蕉成人久久| 亚洲午夜一二三区视频| 91久久国产综合久久蜜月精品| 久久伊人精品天天| 久久久久国产精品午夜一区| 亚洲欧美日韩综合aⅴ视频| 一区二区三区欧美亚洲| 亚洲剧情一区二区| 亚洲激情一区二区三区| 亚洲国产精品va在看黑人| 激情综合五月天| 激情亚洲网站| 伊人久久av导航| 狠狠色狠狠色综合日日五| 国内外成人在线| 黄色成人免费观看| 激情一区二区三区| 一区一区视频| 亚洲电影在线看| 亚洲欧洲在线视频| 亚洲毛片播放| 一区二区三区成人精品| 亚洲无玛一区| 亚洲欧美视频一区| 久久精品国产2020观看福利| 欧美专区中文字幕| 久久久久女教师免费一区| 久久婷婷国产麻豆91天堂| 美女久久一区| 亚洲欧洲精品一区二区三区不卡| 亚洲乱码精品一二三四区日韩在线| 亚洲国产精品视频一区| 亚洲毛片一区| 亚洲一区二区三区777| 欧美一区二视频| 麻豆视频一区二区| 欧美日韩大片一区二区三区| 国产精品色一区二区三区| 国产亚洲女人久久久久毛片| 影音先锋亚洲一区| 亚洲日本视频| 午夜国产欧美理论在线播放| 久久久精品2019中文字幕神马| 免费欧美在线视频| 99re热这里只有精品免费视频| 亚洲影院污污.| 欧美成人一品| 国产欧美综合一区二区三区| 亚洲成人资源| 亚洲欧美怡红院| 欧美激情第一页xxx| 亚洲视频狠狠| 久久综合图片| 国产精品萝li| 亚洲区第一页| 久久成人精品视频| 亚洲欧洲精品一区二区| 久久成人免费电影| 国产精品va在线播放| 又紧又大又爽精品一区二区| 亚洲欧美另类在线| 欧美激情一区二区三区不卡| 亚洲欧美中文另类| 欧美精品www在线观看| 精品成人在线观看| 欧美伊久线香蕉线新在线| 亚洲国产成人av在线| 欧美一区二区三区四区在线| 国产精品xxxxx| 亚洲美女黄色片| 蜜臀a∨国产成人精品| 欧美一区成人|