Mission

2<=N<=300,2<=M<=N∗(N−1)

Solution

SPFA。

由于只是二元关系，所以条件随便写。

具体来说，如果是u⇒v。

若v的最大领先时间还不是正数，就要使得v的最大领先时间尽量大；

若v的最大领先时间已经是正数，就要使得v的经过道路尽量少；

Code

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #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]
          
           Dis) || val[v]>0 && (dis[v]>Dis || dis[v]==Dis && val[v]
           
            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;}
           
          
         
        
       
      
     

Warning

比赛的时候也想到是这样，但没敢打。T T

其实以前，已经是这样了。