题意描述

正如其他物种一样，奶牛们也喜欢在排队打饭时与它们的朋友挨在一起。

FJ 有编号为 $1 \dots N$ 的 $N$ 头奶牛 ( $2 \leq N \leq 1000$ )。开始时，奶牛们按照编号顺序来排队。奶牛们很笨拙，因此可能有多头奶牛在同一位置上。

有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。

给出 $M_{L}$ 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；

又给出 $M_{D}$ 对情敌的编号，以及它们希望彼此之间的距离大于等于多少

请计算：如果满足上述所有条件， $1$ 号奶牛和 $N$ 号奶牛之间的距离最大为多少。

输入格式

第一行：三个整数 $N$ , $M_{L}$ , $M_{D}$ ，用空格分隔。

第 $2 \dots M_{L} + 1$ 行：每行三个整数 $A$ , $B$ , $D$ ，用空格分隔，表示 $A$ 号奶牛与 $B$ 号奶牛之间的距离须 $\leq D \leq D$ 。

第 $M_{L} + 2 \dots M_{L} + M_{D} + 1$ 行：每行三个整数 $A, B, D$ ，用空格分隔，表示 $A$ 号奶牛与 $B$ 号奶牛之间的距离须 $\geq D$ 。

输出格式

一行，一个整数。如果没有合法方案，输出 -1. 如果有合法方案，但 $1$ 号奶牛可以与 $N$ 号奶牛相距无穷远，输出 -2. 否则，输出 $1$ 号奶牛与 $N$ 号奶牛间的最大距离。

Input & Output ‘s examples

Input ‘s eg

markdown

Output ‘s eg

markdown

数据范围与约定

对于 $100 %$ 的数据，保证 $1 \leq A < B \leq N, 1 \leq D \leq 10^{6}$

分析

差分约束系统的经典题目。

题目可以转换为对于一对基友，他们的距离需要满足 $x_{v} - x_{u} \leq d$ 。

而对于一对情敌，他们之间的距离需要满足 $x_{v} - x_{u} \geq d$ 。

既然这样，我们就得到了一对二元一次不等式组，即 $x_{v} - x_{u} \leq d$ 且 $x_{v} - x_{u} \geq d$

转变一下，也就成了 $x_{v} - x_{u} \leq d$ 且 $x_{u} - x_{v} \leq - d$

转变成有向图跑最短路即可。

还有就是

跑最短路时请使用 SPFA，因为有负边权。

剩下的见代码注释。

Code[Accepted]

cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 150001

using namespace std;

int n , ml , md;

struct Edge{
    int to;
    int last;
    ll dis;
}edge[N << 1];

int edge_num;
int head[N << 1];

I void add_edge(int from , int to , ll dis){
    edge[++ edge_num] = (Edge){to , head[from] , dis};
    head[from] = edge_num;
}

ll dis[N] , cnt[N];
bool vis[N] , flag = false;

int SPFA(int s){
	queue<int > Q;
    for(int i = 1;i <= n;i ++){
        dis[i] = 0x3f3f3f3f;
    }
    dis[s] = 0;
    Q.push(s);
    vis[s] = true;
    int first;
    while(!Q.empty()){
        first = Q.front();
        Q.pop();
        vis[first] = false;
        for(int i = head[first]; i ; i = edge[i].last){
            if(dis[edge[i].to] > dis[first] + edge[i].dis){
            	dis[edge[i].to] = dis[first] + edge[i].dis;
                if (++ cnt[edge[i].to] >= n){   //如果形成负权回路，证明不存在可行路径。
                    return -1;
                }
                if(vis[edge[i].to] == false){
                    vis[edge[i].to] = true;
                    Q.push(edge[i].to);
                }
            }
        }
    }
    if(dis[n] == 0x3f3f3f3f){
        return - 2;
    }
    else{
        return dis[n];
    }
}

int main(){
    int u , v , d;
    scanf("%d%d%d" , &n , &ml , &md);
    for(int i = 1; i <= ml; i ++){ 
        scanf("%d%d%d" , &u , &v , &d);
        add_edge(u , v , d);   //dis[u] <= dis[v] + d
    }
    for(int i = 1; i <= md; i ++){
        scanf("%d%d%d" , &u , &v , &d);
        add_edge(v , u , -d);   //dis[v] <= dis[u] - d
    }
    for(int i = 1; i <= n; i ++){
        add_edge(0 , i , 0);    //建立超级原点，判断图的联通性
    }
    int sb = SPFA(0);
    if(sb <= -1){   
        cout << sb << "\n";
    }
    else{
        cout << SPFA(1) << "\n";
    }
   return 0;
}