| ||||||||||
| 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 <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int M=11000;
const int N=110;
double f[N];
struct node{
int x, y;
double f, c;
}data[2*M];
bool cmp(node a, node b){
return a.x<b.x;
}
int main(){
// freopen("poj1860.in", "r", stdin);
// freopen("poj1860.out", "w", stdout);
int n, m, s;
double v;
scanf("%d%d%d%lf", &n, &m, &s, &v);
int x, y;
for(int i=1; i<=m; i++){
scanf("%d%d%lf%lf%lf%lf", &x, &y, &data[i*2-1].f, &data[i*2-1].c, &data[i*2].f, &data[i*2].c);
data[i*2-1].x=x;
data[i*2-1].y=y;
data[i*2].x=y;
data[i*2].y=x;
}
for(int i=1; i<=n; i++)f[i]=0;
f[s]=v;
bool flag;
for(int i=1; i<=n-1; i++){
flag=false;
for(int j=1; j<=2*m; j++){
x=data[j].x;
y=data[j].y;
if((f[x]-data[j].c)*data[j].f>f[y]){
f[y]=(f[x]-data[j].c)*data[j].f;
flag=true;
}
}
if(!flag)break;
}
flag=false;
for(int j=1; j<=2*m; j++){
x=data[j].x;
y=data[j].y;
if((f[x]-data[j].c)*data[j].f>f[y]){
f[y]=(f[x]-data[j].c)*data[j].f;
flag=true;
}
}
if(flag)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