| ||||||||||
| 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 | |||||||||
我的AC代码 真心欢迎各位大牛指正错误!#include<iostream>
using namespace std;
const double MIN=-1<<30;
struct Edge{
int a,b;
double c,r;
};
bool bellman_ford(Edge* e,double* d,int s,double q,int n,int m){
int i,j;
for(i=1;i<=n;i++)
d[i]=MIN;
d[s]=q;
bool flag;
for(i=1;i<=n;i++){
flag=true;
for(j = 1; j <= m; j++)
if(d[e[j].a]>0&&d[e[j].b] <(d[e[j].a] - e[j].c) * e[j].r ){
d[e[j].b] = (d[e[j].a] - e[j].c) * e[j].r;
flag =false;
}
if(flag) return false;
}
return true;
}
int main(){
int n,m,s;
double q;
Edge e[300];
double d[105];
scanf("%d%d%d%lf",&n,&m,&s,&q);
int i;
int a,b;
double r,c;
for(i=1;i<=m;i++){
scanf("%d%d%lf%lf",&a,&b,&r,&c);
e[i].a=a;e[i].b=b;e[i].r=r;e[i].c=c;
scanf("%lf%lf",&r,&c);
e[m+i].a=b;e[m+i].b=a;e[m+i].r=r;e[m+i].c=c;
}
if(bellman_ford(e,d,s,q,n,2*m))
printf("YES\n");
else
printf("NO\n");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator