#3

RT

不知道是什么问题

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define MAXN 2010
#define MAXM 20010
using namespace std;
struct Edge
{
	int to,next,state;
	double dis;
}edge[MAXM];
int head[MAXN],cnt,n,m,count[MAXN],t;
double dis[MAXN],minn=10;
bool vis[MAXN];

void add_edge(int u,int v,double w,int state)
{
	edge[++cnt].to=v;
	edge[cnt].dis=w;
	edge[cnt].state=state;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
bool SPFA(double t)
{
	memset(dis,-0x7f,sizeof(dis));
	memset(count,0,sizeof(count));
	memset(vis,false,sizeof(vis));
	queue <int> q;
	int tmp;
	q.push(n+1);
	dis[n+1]=0;
	while(!q.empty())
	{
		tmp=q.front();
		q.pop();
		vis[tmp]=false;
		for(int i=head[tmp];i;i=edge[i].next)
		{
			double weight=edge[i].dis;
			if(edge[i].state==1)
				weight=log2(weight-t);
			if(edge[i].state==2)
				weight=-log2(weight+t);
			if(dis[edge[i].to]<dis[tmp]+weight)
			{
				dis[edge[i].to]=dis[tmp]+weight;
				if(++count[edge[i].to]==n+2)
					return true;
				if(!vis[edge[i].to])
					vis[edge[i].to]=true,q.push(edge[i].to);
			}
		}
	}
	return false;
}
void binary()
{
	double left=1,right=minn,mid;
	while(right-left>0.000001)
	{
		mid=(left+right)/2.0;
		if(SPFA(mid))
			left=mid;
		else
			right=mid-0.000001;
	}
	printf("%.6lf\n",(left+right)/2.0);
}

int main()
{
	scanf("%d%d%d",&n,&m,&t);
	for(int i=0;i<=n;i++)
		add_edge(n+1,i,0,3);
	for(int i=1;i<=m;i++)
	{
		int u,v,op;
		double w;
		scanf("%d%d%d%lf",&op,&u,&v,&w);
		add_edge(v,u,w,op);
		if(op==1)
			minn=min(minn,w);
	}
	for(int i=1;i<=t;i++)
	{
		int u;
		double w;
		scanf("%d%lf",&u,&w);
		add_edge(0,u,log2(w),3);
		add_edge(u,0,-log2(w),3);
	}
	if(!SPFA(0))
		printf("-1\n");
	else
		binary();
	system("pause");
	return 0;
}