Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1A随便嘚瑟一下

Posted by sprial at 2016-02-26 19:04:24 on Problem 1860
/* ***********************************************
*********************************** */

#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator