[文章目录]
Description
奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。即使说，如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数L。另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述，再给出MD条关于两头奶牛间存有反感的描述。（1<=ML,MD<=10000，1<=L,D<=1000000）你的工作是：如果不存在满足要求的方案，输出-1；如果1号奶牛和N号奶牛间的距离可以任意大，输出-2；否则，计算出在满足所有要求的情况下，1号奶牛和N号奶牛间可能的最大距离。
差分约束。
建模，先判断是否有负环，输出-1。再从n跑最长路，如果1的最长路为初始值，说明n可以无限大，输出-2，反之，输出inf-dis[1]
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,ml,md;
int head[1100],to[30000],nxt[30000],f[30000],cnt;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
}
int dis[1100];
bool vis[1100];
int spfa()
{
static int q[4200];
int l=1,r=n,x; dis[n]=inf;
for(int i=n;i;--i) q[n-i+1]=i,vis[i]=1;
while(l<=r)
{
x=q[l++]; vis[x]=0;
for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]<dis[x]+f[i])
{
dis[to[i]]=dis[x]+f[i];
if(!vis[to[i]])
{
q[++r]=to[i],vis[to[i]]=1;
if(r==4000) return -1;
}
}
}
memset(dis,0,sizeof dis); dis[n]=inf;
l=r=1; q[1]=n; vis[n]=1;
while(l<=r)
{
x=q[l++]; vis[x]=0;
for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]<dis[x]+f[i])
{
dis[to[i]]=dis[x]+f[i];
if(!vis[to[i]])
{
q[++r]=to[i];
vis[to[i]]=1;
}
}
}
if(dis[n]-dis[1]==inf) return -2;
return dis[n]-dis[1];
}
int main()
{
scanf("%d%d%d",&n,&ml,&md);
for(int i=1;i<n;++i) add(i,i+1,0);
int x,y,z;
while(ml--)
{
scanf("%d%d%d",&x,&y,&z);
if(x>y) swap(x,y);
add(y,x,-z);
}
while(md--)
{
scanf("%d%d%d",&x,&y,&z);
if(x>y) swap(x,y);
add(x,y,z);
}
printf("%d",spfa());
return 0;
}