| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
请大牛看看我的代码哪里错了?WA好多次了,始终找不到错误,谢谢#include <iostream>
using namespace std;
#define eps 1e-8
int n,m,s;
double curr;
typedef struct edge
{
int u;
int v;
double r;
double c;
} edge;
edge e[200];
double opt[100];
void Initialize()
{
int i,j;
cin>>n>>m>>s>>curr;
int t1,t2;
j=0;
for(i=0;i<m;i++)
{
cin>>t1>>t2;
e[j].u=t1-1;
e[j].v=t2-1;
cin>>e[j].r>>e[j].c;
j++;
e[j].u=t2-1;
e[j].v=t1-1;
cin>>e[j].r>>e[j].c;
j++;
}
for(i=0;i<n;i++)
opt[i]=0;
opt[s-1]=curr;
}
bool bellmanford()
{
int i,j;
double t;
for(i=0;i<n-1;i++)
{
bool flag=false;
for(j=0;j<2*m;j++)
{
t=(opt[e[j].u]-e[j].c)*e[j].r;
if(t>opt[e[j].v]+eps)
{
opt[e[j].v]=t;
flag=true;
}
}
if(!flag)
return opt[s-1]>curr+eps;
}
for(i=0;i<2*m;i++)
{
t=(opt[e[i].u]-e[i].c)*e[i].r;
if(t>opt[e[i].v]+eps)
return true;
}
return false;
}
int main()
{
Initialize();
if(bellmanford())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator