• <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>
            隨筆-65  評論-6  文章-0  trackbacks-0
             1 /*
             2 Author:    Leo.W
             3 Descriptipn:    給定圖上的n個點及m條點間連線,試求從S點到W點的最短距離,若不存在,則輸出-1;  
             4 How to Do:    經典的最短路算法的應用,dijkstra算法自編寫
             5   */
             6 #include <iostream>
             7 using namespace std;
             8 int n,m;//點的個數,點間連線的條數
             9 int path[205][1005];
            10 bool node[205];
            11 int Dijkstras(int s,int w){
            12     int i,j;
            13     node[s]=true;
            14     for(i=0;i<n;i++){
            15         int mins=INT_MAX,pos=s;
            16         for(j=0;j<n;j++){//尋找為選入點的最小值
            17             if(!node[j]&&mins>path[s][j]){
            18                 mins=path[s][j]; pos=j;
            19             }
            20         }
            21         if(mins==INT_MAX||j>n)    break;
            22         node[pos]=true;
            23         for(j=0;j<n;j++){
            24             if(!node[j]&&path[pos][j]!=INT_MAX&&path[s][j]>path[s][pos]+path[pos][j]){
            25                 path[s][j]=path[s][pos]+path[pos][j];
            26                 path[j][s]=path[s][j];
            27             }
            28         }
            29     }
            30     return path[s][w];
            31 }
            32 int main(){
            33     //freopen("in.txt","r",stdin);
            34     while(scanf("%d%d",&n,&m)!=EOF){
            35         int i,j;
            36         for(i=0;i<n;i++){
            37             node[i]=false;
            38             for(j=0;j<n;j++){
            39                 if(j==i)    path[i][j]=0;
            40                 else    path[i][j]=INT_MAX;//表示兩點間無通路
            41             }
            42         }
            43         for(i=0;i<m;i++){
            44             int begin,end,len;
            45             scanf("%d%d%d",&begin,&end,&len);
            46             if(len<path[begin][end])//此處是全題關鍵,WA了很久。。。。【審題要細致啊】
            47                 path[begin][end]=path[end][begin]=len;//雙向賦值
            48         }
            49         int s,w;
            50         scanf("%d%d",&s,&w);
            51         if(s>w){
            52             s=s^w;w=s^w;s=s^w;
            53         }
            54         if(s==w)
            55             printf("0\n");
            56         else{
            57             int ans=Dijkstras(s,w);
            58             if(ans==INT_MAX)    printf("-1\n");
            59             else    printf("%d\n",ans);
            60         }
            61     }
            62     return 0;
            63 }
            posted on 2012-03-04 12:30 Leo.W 閱讀(239) 評論(0)  編輯 收藏 引用
            久久久久av无码免费网| 久久久久久综合网天天| 中文字幕精品无码久久久久久3D日动漫| 无码人妻少妇久久中文字幕蜜桃| 欧美色综合久久久久久| 久久久久免费精品国产| 精品一区二区久久久久久久网站| 婷婷久久香蕉五月综合加勒比| 久久无码AV中文出轨人妻| 欧美亚洲国产精品久久高清| 青青久久精品国产免费看| 亚洲国产成人精品久久久国产成人一区二区三区综 | 国产精品久久久久久久久免费| 久久精品九九亚洲精品| 色欲久久久天天天综合网| 伊人久久无码中文字幕| 奇米综合四色77777久久| 久久婷婷成人综合色综合| 精品乱码久久久久久久| 久久美女人爽女人爽| 中文字幕一区二区三区久久网站| 99精品久久久久久久婷婷| 久久精品无码专区免费 | 国产精品成人99久久久久| 秋霞久久国产精品电影院| 久久艹国产| 日本五月天婷久久网站| 精品国产乱码久久久久久郑州公司 | 亚洲婷婷国产精品电影人久久| 天天做夜夜做久久做狠狠| 久久这里的只有是精品23| 国内精品九九久久精品 | 国内精品久久久久伊人av| 久久久久久久尹人综合网亚洲| 久久精品无码一区二区三区免费| 欧美大战日韩91综合一区婷婷久久青草| 欧美亚洲日本久久精品| 麻豆一区二区99久久久久| 99久久国产亚洲高清观看2024| 亚洲精品无码专区久久同性男| 久久亚洲国产成人精品性色|