巢穴

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   知识库   博问   管理