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