容易想到二分答案。问题变为判断是否所有条件都被满足,可以发现这是很多变量间的相对关系,取个log之后就是经典的差分约束模型了。特殊的地方在于某些人的分数已被给定,从每个人开始跑一遍最短路判断一下是否能满足关系即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 1010
const double eps=1E-;
double l,r,ans,d[N],a[N];
int n,m,k,p[N],q[N],cnt[N],t;
bool f[N],isget[N];
struct data{int to,nxt;double len;
}edge[N<<];
struct flag{int op,x,y,z;
}Q[N];
void addedge(int x,int y,double z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}
int inc(int &x){x++;if (x>n+) x-=n+;return x;}
bool spfa(int k)
{
memset(f,,sizeof(f));
for (int i=;i<=n;i++) d[i]=;d[k]=;
memset(cnt,,sizeof(cnt));
int head=,tail=;q[]=k;
do
{
int x=q[inc(head)];f[x]=;
for (int i=p[x];i;i=edge[i].nxt)
if (d[x]+edge[i].len<d[edge[i].to])
{
d[edge[i].to]=d[x]+edge[i].len;
if (!f[edge[i].to])
{
q[inc(tail)]=edge[i].to,f[edge[i].to]=;
cnt[edge[i].to]++;if (cnt[edge[i].to]==n) return ;
}
}
}while (head!=tail);
if (isget[k])
for (int i=;i<=n;i++)
if (isget[i]&&d[i]<a[i]-a[k]) return ;
return ;
}
bool check(double T)
{
t=;memset(p,,sizeof(p));
for (int i=;i<=m;i++)
if (Q[i].op==)
{
if (Q[i].z>T) addedge(Q[i].x,Q[i].y,-log(Q[i].z-T));
}
else addedge(Q[i].x,Q[i].y,log(Q[i].z+T));
for (int i=;i<=n;i++)
if (!spfa(i)) return ;
return ;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),m=read(),k=read();
for (int i=;i<=m;i++)
Q[i].op=read(),Q[i].x=read(),Q[i].y=read(),Q[i].z=read();
l=eps,r=-eps;ans=-;
for (int i=;i<=k;i++)
{
int x=read(),y=read();
a[x]=log(y);isget[x]=;
}
while (l<=r)
{
double mid=(l+r)/;
if (check(mid)) ans=mid,l=mid+eps;
else r=mid-eps;
}
if (ans<) cout<<-;
else printf("%.8lf",ans);
return ;
}