【JZOJ3640】【COCI2014】utrka

2019-11-06 06:03:59

字体：大中小

来源：转载

供稿：网友

Mission

这里写图片描述 2<=N<=300,2<=M<=N∗(N−1) $2<=N<=300,2<=M<=N*(N-1)$

Solution

SPFA。由于只是二元关系，所以条件随便写。具体来说，如果是u⇒v $u⇒v$ 。若v $v$ 的最大领先时间还不是正数，就要使得v $v$ 的最大领先时间尽量大；若v $v$ 的最大领先时间已经是正数，就要使得v $v$ 的经过道路尽量少；

Code

#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<math.h>#define ll long longusing namespace std;const char* fin="utrka.in";const char* fout="utrka.out";const int inf=0x7fffffff;const int maxn=307,maxm=maxn*maxn;int n,m,i,j,k,l,o,ans1=inf,ans2=0;int fi[maxn],ne[maxm],la[maxm],va[maxm],tot;int head,tail,b[maxm*10],dis[maxn],val[maxn];bool bz[maxn];void add_line(int a,int b,int c){ tot++; ne[tot]=fi[a]; la[tot]=b; va[tot]=c; fi[a]=tot;}void add(int v,int Dis,int Val){ if (val[v]<=0 && (val[v]<Val || val[v]==Val && dis[v]>Dis) || val[v]>0 && (dis[v]>Dis || dis[v]==Dis && val[v]<Val)){ dis[v]=Dis; val[v]=Val; if (!bz[v]){ bz[v]=true; b[++tail]=v; } }}void spfa(int st){ int i,j,k; memset(dis,127,sizeof(dis)); memset(val,128,sizeof(val)); head=tail=0; add(st,0,0); while (head++<tail){ for (k=fi[b[head]];k;k=ne[k]) if (la[k]==st){ if (val[b[head]]+va[k]>0){ if (ans1>dis[b[head]]+1){ ans1=dis[b[head]]+1; ans2=val[b[head]]+va[k]; }else if (ans1==dis[b[head]]+1) ans2=min(ans2,val[b[head]]+va[k]); } }else add(la[k],dis[b[head]]+1,val[b[head]]+va[k]); bz[b[head]]=false; }}int main(){ freopen(fin,"r",stdin); freopen(fout,"w",stdout); scanf("%d%d",&n,&m); for (i=1;i<=m;i++){ scanf("%d%d%d%d",&j,&k,&l,&o); add_line(j,k,o-l); } for (i=1;i<=n;i++) spfa(i); PRintf("%d %d",ans1,ans2); return 0;}