记录编号	96763	评测结果	AAAAAAAAAA
题目名称	[SGU U236]贪心路径	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2014-04-14 21:30:57	内存使用	0.40 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int SIZEN=60;
const double eps=1e-10,INF=1e10;
double C[SIZEN][SIZEN]={0},T[SIZEN][SIZEN]={0};
bool cn[SIZEN][SIZEN]={0};//是否有边
double len[SIZEN][SIZEN]={0};
double dist[SIZEN]={0};
int pre[SIZEN]={0};
int N,M;
int SPFA(int S,double mid,int pre[SIZEN],double f[SIZEN]){
	bool inq[SIZEN]={0};
	queue<int> Q;
	int tim[SIZEN]={0};
	memset(pre,0,sizeof(pre));
	for(int i=1;i<=N;i++) f[i]=INF;
	for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) if(cn[i][j]) len[i][j]=mid*T[i][j]-C[i][j];
	f[S]=0;Q.push(S);inq[S]=true;
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		if(tim[x]>N) return x;
		for(int i=1;i<=N;i++){
			if(!cn[x][i]) continue;
			if(f[i]>f[x]+len[x][i]){
				f[i]=f[x]+len[x][i];
				pre[i]=x;
				if(!inq[i]){
					inq[i]=true;
					Q.push(i);
					tim[i]++;
				}
			}
		}
	}
	return 0;
}
double find(double left,double right){
	if(right-left<=eps) return left;
	double mid=(left+right)/2;
	if(SPFA(1,mid,pre,dist)) return find(mid,right);
	else return find(left,mid);
}
void work(void){
	double ans=find(0,100.0);
	int x=SPFA(1,ans,pre,dist);
	if(!x){//没有负"一点"的负权边
		printf("0\n");
		return;
	}
	printf("%.2lf\n",ans);
	return;
	//下面是输出方案的内容
	int deg[SIZEN]={0};
	int tot=0;
	int path[SIZEN]={0};
	while(deg[x]<=1){
		deg[x]++;
		if(deg[x]==2) path[++tot]=x;
		x=pre[x];
	}
	printf("%d\n",tot);
	for(int i=tot;i>=1;i--) printf("%d ",path[i]);
	printf("\n");
}
void read(void){
	memset(cn,0,sizeof(cn));
	scanf("%d%d",&N,&M);
	int a,b;
	for(int i=1;i<=M;i++){
		scanf("%d%d",&a,&b);
		scanf("%lf%lf",&C[a][b],&T[a][b]);
		cn[a][b]=true;
	}
}
int main(){
	freopen("greedypath.in","r",stdin);
	freopen("greedypath.out","w",stdout);
	read();
	work();
	return 0;
}