久久久久国产一区二区三区,久久精品一区二区三区中文字幕,日韩影院久久

P1860

Bellman-Ford
看題看了半天..

#include <iostream>

#include <vector>

#include <fstream>

using namespace std;

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

struct node

{

int u,v;

double r,c;

};

vector<node> edge_vec;

int n,m,s;

int f;

#define eps 1e-8

double v;

double dist[200];

void relax(int x,int y,double r,double c)

{

if (dist[y]+eps<(dist[x]-c)*r)

{f=1;dist[y]=(dist[x]-c)*r;}

}

bool bellman()

{

for (int i=1;i<=n;i++)

dist[i]=0;

dist[s]=v;

while(dist[s]<=v+eps)

{

f=0;

for (int j=0;j<edge_vec.size();j++)

{

node edge=edge_vec.at(j);

relax(edge.u,edge.v,edge.r,edge.c);

}

if (!f) break;

}

if (dist[s]>v+eps) return true;

else return false;

}

int main()

{

cin>>n>>m>>s>>v;

for (int i=1;i<=m;i++)

{

int x,y;

double rxy,cxy,ryx,cyx;

cin>>x>>y>>rxy>>cxy>>ryx>>cyx;

node edge;

edge.u=x;

edge.v=y;

edge.r=rxy;

edge.c=cxy;

edge_vec.push_back(edge);

edge.u=y;

edge.v=x;

edge.r=ryx;

edge.c=cyx;

edge_vec.push_back(edge);

}

if (bellman()) cout<<"YES"<<endl;

else

cout<<"NO"<<endl;

// system("pause");

return 0;

}

posted on 2009-10-04 17:23 Vincent 閱讀(122) 評論(0) 編輯收藏引用

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



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

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

Link

搜索

最新評論

閱讀排行榜

評論排行榜

P1860