差分约束
注意每头牛排队顺序和编号顺序一致
然后数据有保证 A<B
所以距离只要考虑 B-A 就可以了
要求最大距离
所以要用 ≤ 号来表示牛之间的关系
然后跑最短路
注意搞出来的图可能不连通
所以判断合法方案时要把每个块都跑一遍
最后 dis [ i ] 就表示牛 1 和 牛 i 之间的最大距离
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=5e6+7,M=1e4+7,INF=0x3f3f3f3f; int n,m1,m2; int fir[M],from[N],to[N],val[N],cnt; inline void add(int a,int b,int c) { from[++cnt]=fir[a]; fir[a]=cnt; to[cnt]=b; val[cnt]=c; } int dis[M],tot[M]; bool vis[M],flag; queue <int> q; void SPFA(int sta) { memset(dis,INF,sizeof(dis)); memset(tot,0,sizeof(tot)); q.push(sta); dis[sta]=0; vis[sta]=1; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; if(++tot[u]>=n) { flag=1; break; } for(int i=fir[u];i;i=from[i]) { int &v=to[i]; if(dis[v]>dis[u]+val[i]) { dis[v]=dis[u]+val[i]; if(!vis[v]) q.push(v),vis[v]=1; } } } } int main() { int a,b,c; n=read(); m1=read(); m2=read(); while(m1--) { a=read(); b=read(); c=read(); add(a,b,c); } while(m2--) { a=read(); b=read(); c=read(); add(b,a,-c); } for(int i=1;i<=n;i++) add(0,i,0);//建一个虚节点0来跑每一个块 SPFA(0); if(flag) { cout<<"-1"; return 0; }//判断是否合法 SPFA(1);//求出最大距离 printf("%d",dis[n]==dis[0] ? -2 : dis[n]);//如果可以无穷远就输出-2 return 0; }