国产精品日韩精品欧美在线,国产精品久久久一本精品,亚洲精品韩国

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 閱讀(127) 評論(0) 編輯收藏引用所屬分類: 數據結構與算法

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: P3368 P2352 dinic P3273 P2104 ctsc2000 丘比特的煩惱 usaco 4.3 lgame P3267 P1276 P1837

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

Link

搜索

最新評論

閱讀排行榜

評論排行榜

P3259