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

    
            

            




            







												


        


            


            巢穴
            

            about:blank
            

            



            
	
					
	
            
		
            
			P3259
		
            
		   還是bellman-ford
            

            #include <iostream>
            #include             <vector>
            //#include <fstream>
            using namespace std;

            //ifstream fin("t3259.in");


            struct node
            {
                         int u,v,w;
            }            ;
            vector            <node> edge_vec;
            int f;
            int n,m,w;
            bool bellman()
            {
                             int dist[10000];
                 memset(dist,            0x7f,sizeof(dist));
                 
                 dist[edge_vec.at(            0).u]=0;
                             int flag;
                             for (int i=1;i<=n;i++)
                             {
                  flag            =0;
                              for (int j=0;j<edge_vec.size();j++)
                              {
                      node edge            =edge_vec.at(j);
                                  if (dist[edge.v]>dist[edge.u]+edge.w)
                                     {dist[edge.v]=dist[edge.u]+edge.w;flag=1;}
                  }
                              if (!flag) return false;
                 }
                             for (int i=0;i<edge_vec.size();i++)
                             {
                     node edge            =edge_vec.at(i);
                                 if (dist[edge.v]<dist[edge.u]+edge.w)
                                    return true;
                 }
                             return false;     
            }
            int main()
            {
                cin            >>f;
                            while (f--)
                            {
                 cin            >>n>>m>>w;
                 edge_vec.clear();
                             for (int i=1;i<=m;i++)
                             {
                              int u_,v_,w_;
                  cin            >>u_>>v_>>w_;
                  node edge;
                  edge.u            =u_;
                  edge.v            =v_;
                  edge.w            =w_;
                  edge_vec.push_back(edge);
                  edge.u            =v_;
                  edge.v            =u_;
                  edge.w            =w_;
                  edge_vec.push_back(edge);     
                 }
                             for (int i=1;i<=w;i++)
                             {
                              int u_,v_,w_;
                  cin            >>u_>>v_>>w_;
                  node edge;
                  edge.u            =u_;
                  edge.v            =v_;
                  edge.w            =-w_;
                  edge_vec.push_back(edge);      
                 }
                             if  (bellman()) cout<<"YES"<<endl;
                             else
                     cout            <<"NO"<<endl;
                }
            }
            

		
            
			posted on 2009-10-04 18:45 Vincent 閱讀(121) 評論(0)  編輯 收藏 引用  所屬分類: 數(shù)據(jù)結(jié)構(gòu)與算法 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久人人爽人爽人人爽av|
国产99久久久国产精品小说|
一本一道久久综合狠狠老|
色偷偷88888欧美精品久久久
|
91精品国产91久久久久久|
亚洲精品高清久久|
欧美国产精品久久高清|
新狼窝色AV性久久久久久|
久久精品嫩草影院|
伊人久久精品影院|
欧美一区二区精品久久|
久久一区二区三区99|
久久久久免费看成人影片|
91精品国产91久久久久久青草
|
www亚洲欲色成人久久精品|
久久精品国产WWW456C0M|
人妻丰满AV无码久久不卡|
久久久久99精品成人片三人毛片|
伊人色综合久久天天人手人婷|
91精品国产高清久久久久久91|
午夜天堂av天堂久久久|
久久人人青草97香蕉|
色综合久久中文综合网|
久久人妻少妇嫩草AV无码专区|
久久精品国产亚洲AV不卡|
国产精品无码久久久久久|
亚洲国产精品无码久久98|
伊人色综合九久久天天蜜桃|
AAA级久久久精品无码区|
国内精品久久人妻互换|
国产欧美久久久精品影院|
人妻少妇精品久久|
亚洲AⅤ优女AV综合久久久|
国产福利电影一区二区三区久久老子无码午夜伦不
|
久久国产色av免费看|
国产免费久久精品99re丫y|
久久精品国产72国产精福利|
久久精品一区二区|
日本三级久久网|
久久精品成人免费国产片小草
|
狠狠色丁香婷婷久久综合
|