题意描述
正如其他物种一样，奶牛们也喜欢在排队打饭时与它们的朋友挨在一起。
FJ 有编号为 $1\dots N$ 的 $N$ 头奶牛 ($2\le N\le 1000$)。开始时，奶牛们按照编号顺序来排队。奶牛们很笨拙，因此可能有多头奶牛在同一位置上。
有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。
给出 $M_L$对好基友的编号，以及它们希望彼此之间的距离小于等于多少；
又给出 $M_D$对情敌的编号，以及它们希望彼此之间的距离大于等于多少
请计算：如果满足上述所有条件，$1$ 号奶牛和$N$ 号奶牛之间的距离最大为多少。
输入格式
第一行：三个整数 $N$, $M_L$, $M_D$，用空格分隔。
第$2\dots M_L+1$ 行：每行三个整数 $A$, $B$, $D$，用空格分隔，表示 $A$ 号奶牛与 $B$ 号奶牛之间的距离须 $\le D≤D$。
第 $M_L+2\dots M_L+M_D+1$行：每行三个整数 $A, B, D$，用空格分隔，表示 $A$ 号奶牛与 $B$ 号奶牛之间的距离须 $\ge D$。
输出格式
一行，一个整数。如果没有合法方案，输出 -1. 如果有合法方案，但 $1$ 号奶牛可以与 $N$ 号奶牛相距无穷远，输出 -2. 否则，输出 $1$ 号奶牛与 $N$ 号奶牛间的最大距离。
Output ‘s eg
数据范围与约定
对于 $100\%$ 的数据，保证 $1\le A<B\le N,1\le D\le 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]
#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);
}
for(int i = 1; i <= md; i ++){
scanf("%d%d%d" , &u , &v , &d);
add_edge(v , 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;
}
|
THE END
