- 和人类一样，奶牛们在打饭的时候喜欢和朋友站得很近。
- 约翰的编号为 到 的 只奶牛正打算排队打饭。现在请你来安排她们，让她们在数轴上排好队。奶牛的弹性很好，同一个坐标可以站无限只奶牛，排队的顺序必须和她们编号的顺序一致。有 对奶牛互相爱慕，她们之间的距离不能超过一定的值，有 对奶牛互相敌视，她们的距离不能小于一定的值。
- 那么，首尾奶牛的最大距离是多少呢？
- 和人类一样，奶牛们在打饭的时候喜欢和朋友站得很近。
- 约翰的编号为 到 的 只奶牛正打算排队打饭。现在请你来安排她们，让她们在数轴上排好队。奶牛的弹性很好，同一个坐标可以站无限只奶牛，排队的顺序必须和她们编号的顺序一致。有 对奶牛互相爱慕，她们之间的距离不能超过一定的值，有 对奶牛互相敌视，她们的距离不能小于一定的值。
- 那么，首尾奶牛的最大距离是多少呢？
如果没有合理方案，输出 ，如果首尾两头牛的距离可以无限大，输出 ，否则输出一个整数表示首尾奶牛的最大距离。
样例
样例输入
4 2 1
1 3 10
2 4 20
2 3 3
样例输出
27
题解
- 本题目是差分约束的板子题，如果差分约束有疑问，先复习，，，
- 中间的swap原因是我们要从序号低的点向序号大的点建正边，而后边那个是从高序号到低序号建负边，
- 由于牛必须按顺序站所以必须建相邻边，
- 再建一个超级源点，判断全图是否联通，因为1可能无法连到所有的点。
- 对于建相邻边的情况举一例子，大家手动模拟：
4 1 1
1 4 10
2 3 20
-------
-1
code
#include <bits/stdc++.h>
using namespace std;
const int maxn=5000;
const int INF=0x3f3f3f3f;
struct edge{
int to,dis,next;
}e[maxn<<2];
inline int read(){
int k=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') ch=getchar();
for(;isdigit(ch);ch=getchar()) k=k*10+ch-'0';
return k*f;
}
int head[maxn];
int cnt=0;
inline void add(int x,int y,int z){e[++cnt]=(edge){y,z,head[x]},head[x]=cnt;}
int flag=0;int n;
int d[maxn],tot[maxn],vis[maxn];
void spfa(int s){
queue<int>q;
flag=0;
memset(d,0x3f,sizeof(d));
q.push(s);vis[s]=1;d[s]=0;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to,dis;
if(d[v]>(dis=d[u]+e[i].dis)){
d[v]=dis;
if(!vis[v]) vis[v]=1,q.push(v);
}
}
if(++tot[u]>n) return flag=-1,void();
}
}
int main(){
n=read();int M=read(),K=read();int x,y,z;
for(int i=1;i<=n;i++)add(0,i,0);
for(int i=1;i<n;i++)add(i+1,i,0);
for(int i=1;i<=M;i++){x=read(),y=read(),z=read();if(x>y)swap(x,y);add(x,y,z);}
for(int i=1;i<=K;i++){x=read(),y=read(),z=read();if(x>y)swap(x,y);add(y,x,-z);}
spfa(0);
if(flag==-1) return cout<<-1<<endl,0;
spfa(1);
if (d[n]==INF) return printf("-2
"),0;
else return printf("%d
",d[n]),0;
return 0;
}