巢穴

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 阅读(117) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理