解题思路
\(\qquad\)这题也是一个比较裸的差分约束:多了的那个输出\(-2\)的其实就是在差分约束系统中\(1\)号点和\(n\)号点没有约束关系,也就是\(1\)和\(n\)号不连通。由于这里要求最大距离,所以我们在系统中应该跑最短路
从题目中我们可以看出这样几条约束关系
:
\(\qquad\quad\) \(\large x_{i+1}\ge x_i\Rightarrow x_i\le x_{i+1}+0\) :因为后面的牛的位置一定不能比前面的靠前。
\(\qquad\quad\)在\(M_L\)条的关系中 \(\large x_b-x_a\le L\Rightarrow x_b\le x_a+L\):距离不大于\(L\)
\(\qquad\quad\)在\(M_D\)条的关系中 \(\large x_b - x_a\ge D\Rightarrow x_a-x_b\le -D\Rightarrow x_a\le x_b-D\):距离不小于\(D\)
然后又没有一个源点可以遍历所有边
,所以我们还是建立超级源点\(0\)让它和所有点连边权\(0\)的边。
整理关系得到
\(
\Large
\left \{
\begin{array}c
x_i\le x_{i+1}+0,\\
x_b\le x_a+L,\\
x_a\le x_b-D,\\
x_i\le x_0+0.
\end{array}
\right.
\)
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, M = 21010, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N], q[N], st[N];
int hh, tt(1), md, ml, n, ring;
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
void spfa(int S)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
memset(cnt, 0, sizeof cnt);
q[tt ++ ] = S, st[S] = 1, dist[S] = 0;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = 0;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return void (ring = true);
if (!st[j])
{
st[j] = true ;
q[tt ++ ] = j;
if (tt == N) tt = 0;
}
}
}
}
return void (ring = false);
}
int main()
{
scanf("%d%d%d", &n, &ml, &md);
memset(h, -1, sizeof h);
while (ml -- )
{
int a, b, l;
scanf("%d%d%d", &a, &b, &l);
if (a > b) swap(a, b);
add(a, b, l);
}
while (md -- )
{
int a, b, d;
scanf("%d%d%d", &a, &b, &d);
if (a > b) swap(a, b);
add(b, a, -d);
}
for (int i = 1; i < n; i ++ )
add(i + 1, i, 0), add(0, i, 0);
add(0, n, 0);
spfa(0);
if (ring) puts("-1");
else {
spfa(1);
printf("%d\n", dist[n] == INF ? -2 : dist[n]);
}
return 0;
}
标签:USACO05,le,AcWing1170,int,tt,排队,st,add,dist
From: https://www.cnblogs.com/StkOvflow/p/17019911.html