• <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>

            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日

            分類:最小環(huán),dijkastra

            題目分析與算法原型
                    這道題目來自地大OJ,相當郁悶,WA了幾十次,題目有很多陷阱,比方說,重邊,還有自環(huán),其次,重邊的時候處理還不能單單記錄最小的那條,因為題目是求從1節(jié)點出發(fā)回到1的最小環(huán),所以極有可能會有這樣的情況出現,從1到某個節(jié)點x,有多條重邊,然后這個時候 從1出發(fā)經過某條邊到達x,然后又繞著他們之間另外的一條邊回到1,這樣子也算一個環(huán),這個地方當初一直沒考慮到,因此貢獻了好幾次WA,然后自環(huán)的地方也錯了好幾次,最后,是flag[]數組初始化的錯誤,導致自己一直找不出來,淚奔.......
                   這道題目的大致做法如下:枚舉每個和1相鄰的點,然后刪掉他們之間的這條邊,做一次Dijkastra,記錄下他們之間的最短路徑,將該路徑加上刪除邊的長度就是一個經過1的環(huán)的長度,保存下來,然后加回原來的那條邊,按此方法繼續(xù),直到將所有的與1相鄰的點的枚舉一遍并且記錄下相應的環(huán)值大小
                  注意:對于自環(huán),只用記錄1到1這樣的自環(huán)(如果有,可能有多個,記錄最小的那個的值),其他的點的自環(huán)不用考慮,可以直接略掉,因為不影響本題;還有對于重邊的處理是,記錄兩個點之間(如果有多條重邊)最小和次小的那兩條邊的長度,然后將他們的和跟剛才計算的環(huán)的值做比較,取小的那個作為該環(huán)的最后的值,最后取所有環(huán)中最小的那個(如果有1到1的自環(huán),則還有跟該自環(huán)的長度做一次比較,取較小的值)輸出

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

            <2009年8月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            導航

            統(tǒng)計

            常用鏈接

            留言簿(8)

            隨筆檔案(78)

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            評論排行榜

            久久精品国产亚洲Aⅴ香蕉| 久久伊人五月丁香狠狠色| 国产精品久久久久久搜索| 久久最新精品国产| 久久精品国产只有精品66| 中文字幕精品久久| 99国产欧美精品久久久蜜芽| 久久国产视频网| 亚洲AV日韩AV天堂久久| 品成人欧美大片久久国产欧美| 99久久精品国产一区二区蜜芽| 久久精品国产99国产精品| 狠狠色狠狠色综合久久| 久久国产高清字幕中文| 欧美亚洲国产精品久久久久| 国产美女久久久| 新狼窝色AV性久久久久久| 成人精品一区二区久久| 欧美丰满熟妇BBB久久久| 亚洲国产成人精品无码久久久久久综合 | 久久久精品一区二区三区| 一级做a爰片久久毛片毛片| 国产精品欧美久久久久天天影视| 亚洲精品无码久久久久sm| 色综合久久天天综线观看| 99久久亚洲综合精品网站| 99精品国产在热久久无毒不卡| 奇米综合四色77777久久| 国产美女亚洲精品久久久综合| 国产精品一区二区久久精品无码| 99久久精品国产免看国产一区| 久久久久久久波多野结衣高潮| 久久亚洲AV无码精品色午夜麻豆| 国产巨作麻豆欧美亚洲综合久久| 久久天天躁狠狠躁夜夜躁2O2O| 午夜久久久久久禁播电影| 99久久国产亚洲综合精品| 久久午夜福利无码1000合集| 久久免费视频一区| 中文字幕无码久久人妻| 久久综合久久美利坚合众国|