记录编号	96834	评测结果	AAAAAAAAAA
题目名称	[SGU U236]贪心路径	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2014-04-15 13:32:18	内存使用	0.37 MiB

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>

using namespace std;

const int MAXN=50+10;
const int INF=10000*10000;

int N,M;

struct edge{
	int from,to;
	double cost;
};

struct spfa{
	vector<edge> edges;
	vector<int> G[MAXN];
	int s,t;
	double d[MAXN];
	bool inq[MAXN];
	int inq_times[MAXN];
	
	void add_edge(int from,int to,double cost){
		edges.push_back((edge){from,to,cost});
		//edges.push_back((edge){to,from,cost});
		int m=edges.size();
		G[from].push_back(m-1);
		//G[to].push_back(m-1);
	}
	
	int p[MAXN];
	bool find(){
		for(int i=0;i<MAXN;i++)d[i]=-INF;
		memset(inq,0,sizeof(inq));
		memset(inq_times,0,sizeof(inq_times));
		memset(p,0,sizeof(p));
		d[s]=0;
		queue<int> q;
		q.push(s);inq[s]=true;
		while(!q.empty()){
			int u=q.front();q.pop();inq[u]=false;
			for(int i=0;i<G[u].size();i++){
				edge & e=edges[G[u][i]];
				if(d[e.to]<d[u]+e.cost && p[u]!=e.to){
					d[e.to]=d[u]+e.cost;
					p[e.to]=u;
					inq_times[e.to]++;
					if(inq_times[e.to]>=N)return true;
					if(!inq[e.to]){
						inq[e.to]=true;
						q.push(e.to);
					}
				}
			}
		}
		return false;
	}
	
	void init(int s,int t){
		this->s=s; this->t=t;
		edges.clear();
		for(int i=0;i<MAXN;i++)G[i].clear();
	}
}solver;

struct input{
	int a,b,c,t;
}inputs[MAXN*MAXN];

void read(){
	scanf("%d %d",&N,&M);
	for(int i=1;i<=M;i++){
		int a,b,c,t;
		scanf("%d %d %d %d",&a,&b,&c,&t);
		inputs[i]=(input){a,b,c,t};
	}
}

bool test(double r){
	solver.init(1,N);
	for(int i=1;i<=M;i++){
		input & in=inputs[i];
		double cost=double(in.c)-r*double(in.t);
 		solver.add_edge(in.a,in.b,cost);
	}
	return solver.find();
}

void work(){
	double left=0;double right=500000;
	while(right-left>=0.0001){
		double mid=(left+right)/2;
		if(test(mid)){
			left=mid;
		}else{
			right=mid;
		}	
	}
	if(left-0<0.001){
		printf("0\n");
	}else printf("%.2lf\n",left);
}

int main(){
	//freopen("in.txt","r",stdin);
	freopen("greedypath.in","r",stdin);
	freopen("greedypath.out","w",stdout);
	read();
	work();
	return 0;
}