| ||||||||||
| 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 | |||||||||
1A随便嘚瑟一下/* ***********************************************
*********************************** */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
struct edge
{
int u,v;
double r,c;
};
vector<edge>e;
int N,M,S;
double V;
double d[2000];
bool bellman_ford(int src)
{
memset(d,0,sizeof(d));
d[src]=V;
for(int i=0;i<N;i++)
{
int flg=0;
for(int j=0;j<e.size();j++)
{
int u=e[j].u,v=e[j].v;
double val=(d[u]-e[j].c)*e[j].r;
if(val>d[v]){
d[v]=val;
//printf("d[%d]=%lf\n",v,d[v]);
flg=1;
}
}
if(!flg) break;
}
for(int j=0;j<e.size();j++)
{
int u=e[j].u,v=e[j].v;
double val=(d[u]-e[j].c)*e[j].r;
if(val>d[v]) return true;
}
return false;
}
int main()
{
// freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d%d%d%lf",&N,&M,&S,&V)==4)
{
e.clear();
for(int i=0;i<M;i++)
{
//printf("i=%d\n",i);
int u,v;
scanf("%d%d",&u,&v); u--;v--;
double rab,cab,rba,cba;
scanf("%lf%lf%lf%lf",&rab,&cab,&rba,&cba);
edge tmp;
tmp.u=u;tmp.v=v;tmp.r=rab;tmp.c=cab;
e.push_back(tmp);
tmp.u=v;tmp.v=u;tmp.r=rba;tmp.c=cba;
e.push_back(tmp);
}
if(bellman_ford(S-1)) puts("YES");
else puts("NO");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator