题目描述

有 N 头奶牛正在排队，它们的编号为 1 到 N，约翰要给它们安排合适的排队位置，满足以下条 件：

• 首先，所有奶牛要站在一条直线上。由于是排队，所以编号小的奶牛要靠前，不能让编号大的 奶牛插队。但同一个位置可以容纳多头奶牛，这是因为它们非常苗条的缘故

• 奶牛喜欢和朋友靠得近点。朋友关系有 F 对，其中第 Ai 头奶牛和第 Bi 头奶牛是第 i 对朋友， 它们的距离不能超过 Ci

• 奶牛还要和讨厌的同类保持距离。敌对关系有 E 对，其中第 Xi 头奶牛和第 Yi 头奶牛是第 i 对 敌人，它们的距离不能少于 Zi

你能否帮助约翰找到一个合理的站位方法，满足所有奶牛的要求，而且让 1 号奶牛和 N 号奶牛间的 距离尽量大？

输入格式

• 第一行：三个整数 N，F 和 E，2 ≤ N ≤ 1000, 1 ≤ F;E ≤ 10000

• 第二行到第 F + 1 行：第 i + 1 行有三个整数 Ai，Bi 和 Ci，1 ≤ Ai,Bi ≤ N; 1 ≤ Ci ≤ 10^6

• 第 F + 2 行到第 F + E + 1 行：第 i + F + 1 行有三个整数 Xi，Yi 和 Zi，1 ≤ Xi,Yi ≤ N; 1 ≤Zi ≤ 10^6

输出格式

• 单个整数：如果不存在满足所有条件的安排，输出 −1；如果 1 号奶牛和 N 号奶牛的距离可以 任意大，输出 −2；否则输出 1 号奶牛和 N 号奶牛的最大距离

样例输入

4 2 1

1 3 10

2 4 20

2 3 3

样例输出

27

解释

一号奶牛站在坐标 0，二号奶牛站在坐标 7，

三号奶牛站在坐标 10，四号奶牛站在坐标 27

题解

比较明显的差分约束系统吧。

 

根据题目条件很容易得出两个不等式

        min(Ai,Bi)-max(Ai,Bi)>= -Ci

        max(Xi,Yi)-min(Xi,Yi)>= Zi

根据差分约束系统原理，从min(Ai,Bi)向max(Ai,Bi)引一条权值为Ci的有向边，从max(Xi,Yi)向min(Xi,Yi)引一条权值为Zi的有向边，然后SPFA求最短路就可以了。

有时为了防止建成的图不连通，常构造一个节点，从这个节点向每个节点连一条边，本题可以不这样。

dis数组初始化为无穷大，走最短路时，如果有负环，就不存在满足所有条件的安排，输出 −1；如果走完最短路dis[n]还是无穷大，1 号奶牛和 N 号奶牛的距离可以 任意大，输出 −2；不满足以上条件的，直接输出dis[n]。

 

#include 
     
      const int N=2005;struct node{    int id,nex,u,w;}; node g[40005];int fir[1005],num,dis[1005],q[2005],cnt[1005],n;bool vis[1005];int min(int x,int y){    return x<=y?x:y;}int max(int x,int y){    return x>=y?x:y;}void add(int x,int y,int z){    g[++num].u=y;  g[num].w=z;  g[num].nex=fir[x];  fir[x]=num;}void SPFA(){    int t=1,h=0,i,j,k,v;    for (i=2;i<=n;i++)      dis[i]=1e9;    q[1]=1;  vis[1]=true;    while (h!=t)    {        h=(h+1)%N;        for (k=fir[q[h]];k;k=g[k].nex)           if (dis[q[h]]+g[k].w
      
       n)                {                    dis[n]=-1;                    return;                }             }                        }        vis[q[h]]=false;      }      return;}int main(){    int F,E,A,B,C,i,j;    scanf("%d%d%d",&n,&F,&E);    for (i=1;i<=F;i++)         scanf("%d%d%d",&A,&B,&C),      add(min(A,B),max(A,B),C);    for (i=1;i<=E;i++)      scanf("%d%d%d",&A,&B,&C),      add(max(A,B),min(A,B),-C);    /*  for (i=1;i<=n;i++)           add(0,i,0);   */    SPFA();    printf("%d",dis[n]!=1e9?dis[n]:-2);    return 0;  }