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

            POJ 3259 Wormholes


            Bellman_Ford 算法,

            利用Bellman_Ford算法判斷是否存在負回路。如果存在負回路就一定可以回到(不停的走這個回路,直到賺到的負值夠與回去的值抵消的),如果不存在一定不可以回去。
            用cin500+ms, 用scanf  100+ms

            #include<iostream>
            #include
            <stdio.h>
            using namespace std;
            const int INF=0x0fffffff;
            struct type
            {
                   
            int s,t;
                   
            int len;
            }edge[
            30000];

            int n,m,w,nedge=0;
            int d[505];
            bool Bellman_Ford()
            {
                 
            bool isPossible=false;
                 
            for(int j=1; j<=n; j++)d[j]=INF;
                 d[
            1]=0;
                 
            int u,v;
                 
            bool f;
                 
            for(int j=1; j<=n-1; j++)
                 {
                         f
            =0;
                         
            for(int k=1; k<=nedge; k++)
                         {
                                 u
            =edge[k].s; v=edge[k].t;
                                 
            if(d[v]>d[u]+edge[k].len)
                                             d[v]
            =d[u]+edge[k].len;
                                 f
            =1;            
                         }
                         
            if(f==0)return false;
                 }
              /*前面n-1次循環可以求出無負回路時的最短路徑,再來一次如果可以更新就一定有負回路。/*
                  
            for(int k=1; k<=nedge; k++)
                         {
                                 u
            =edge[k].s; v=edge[k].t;
                                 
            if(d[v]>d[u]+edge[k].len)
                                       {  d[v]
            =d[u]+edge[k].len; return 1;}
                                            
                         }
                 
                
            // system("pause");
                 return 0;
                 
            }

            int main()
            {
                
            int t;
                cin
            >>t;
                
            while(t--)
                {
                          
            int i,j,u,v,value;
                          scanf(
            "%d %d %d",&n,&m,&w);//cin>>n>>m>>w;
                          nedge=0;
                          
            for(int i=1; i<=m; i++)
                          {
                                  scanf(
            "%d %d %d",&u,&v,&value);//cin>>u>>v>>value;
                                  ++nedge;
                                  edge[nedge].s
            =u;
                                  edge[nedge].t
            =v;
                                  edge[nedge].len
            =value;
                                  
            ++nedge;
                                  edge[nedge].s
            =v;
                                  edge[nedge].t
            =u;
                                  edge[nedge].len
            =value;
                          }     
                              
                          
            for(int i=1; i<=w; i++)
                          {
                                  scanf(
            "%d %d %d",&u,&v,&value);//cin>>u>>v>>value;
                                  ++nedge;
                                  edge[nedge].s
            =u;
                                  edge[nedge].t
            =v;
                                  edge[nedge].len
            =-value;
                                  
                                 
            /* ++nedge;
                                  edge[nedge].s=v;
                                  edge[nedge].t=u;
                                  edge[nedge].len=-value;
                                  
            */
                          }
                          
                          
            if(Bellman_Ford())
                                     cout
            <<"YES"<<endl;
                          
            else       cout<<"NO"<<endl;
                 
                }
                system(
            "pause");
                
            return 0;
            }

            posted on 2010-08-09 19:38 田兵 閱讀(723) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            久久99免费视频| 日本欧美国产精品第一页久久| 亚洲va中文字幕无码久久不卡| 久久精品国内一区二区三区| 久久久久综合国产欧美一区二区| 无码人妻久久久一区二区三区| 久久久久久久综合日本| 伊人久久大香线焦综合四虎| 久久国产色av免费看| 久久久久久国产精品无码下载 | 色综合久久久久综合99| 久久久久久久99精品免费观看| 伊人久久大香线蕉综合Av| 久久青青草原精品国产不卡| 999久久久国产精品| segui久久国产精品| 欧美精品一本久久男人的天堂| 精品久久久久久成人AV| 久久亚洲私人国产精品| 久久久精品2019免费观看| 久久久噜噜噜www成人网| 精品久久久中文字幕人妻| 天堂无码久久综合东京热| 亚洲人成无码久久电影网站| 午夜精品久久久久9999高清| 精品久久久久久国产免费了| 久久久久九国产精品| 99久久做夜夜爱天天做精品| 久久精品人人做人人爽电影| 色婷婷综合久久久中文字幕| 久久66热人妻偷产精品9| 日日躁夜夜躁狠狠久久AV| 久久精品国产99国产精偷| 狠狠色综合久久久久尤物| 亚洲国产小视频精品久久久三级 | 久久精品青青草原伊人| 久久久久久综合网天天| 久久99久久99精品免视看动漫| 久久亚洲精品中文字幕三区| 久久久久国产亚洲AV麻豆| 亚洲国产另类久久久精品小说|