# 请问差分约束为什么只能用最长路，而不能用最短路？

@C　C　A  2021-07-22 18:22 回复

$\quad \rm RT$

$\quad$这是最短路的代码，只有 $70\rm pts.$

#include<bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; i++)

const int N = 1e5 + 10;

int n, m, op, u, v, in[N], dis[N], cnt[N];
int last[N], to[N << 2], W[N << 2], Next[N << 2], tot;
queue <int> Q;

void add (int u, int v, int w) {
to[++tot] = v, W[tot] = w, Next[tot] = last[u], last[u] = tot;
}

int main () {

scanf("%d%d", &n, &m);
while (m--) {
scanf("%d%d%d", &op, &u, &v);
else if (op == 2) add(v, u, -1);
else if (op == 3) add(u, v, 0);
else if (op == 4) add(u, v, -1);
else if (op == 5) add(v, u, 0);

}
rep(i, 1, n) to[++tot] = i, Next[tot] = last[0], last[0] = tot;

memset(dis, 0x3f, sizeof dis);
dis[0] = 0, in[0] = true, Q.push(0);
while (!Q.empty()) {
int u = Q.front();
Q.pop(), in[u] = false;
if (++cnt[u] > 1000) puts("-1"), exit(0);
for (int i = last[u]; i; i = Next[i])
if (dis[to[i]] > dis[u] + W[i]) {
dis[to[i]] = dis[u] + W[i];
if (!in[to[i]]) Q.push(to[i]);
}
}

long long ans = 0; int Min = 1e9;
rep(i, 1, n) Min = min(Min, dis[i]);
rep(i, 1, n) ans += dis[i] - Min;
printf("%lld\n", ans + n);

return 0;
}

$\quad$这是最长路的代码，$\rm AC$ 了

#include<bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; i++)

const int N = 1e5 + 10;

int n, m, op, u, v, in[N], dis[N], cnt[N];
int last[N], to[N << 2], W[N << 2], Next[N << 2], tot;
queue <int> Q;

void add (int u, int v, int w) {
to[++tot] = v, W[tot] = w, Next[tot] = last[u], last[u] = tot;
}

int main () {

scanf("%d%d", &n, &m);
while (m--) {
scanf("%d%d%d", &op, &u, &v);
else if (op == 2) add(u, v, 1);
else if (op == 3) add(v, u, 0);
else if (op == 4) add(v, u, 1);
else if (op == 5) add(u, v, 0);

}
for (int i = n; i >= 1; i--) add(0, i, 1);

memset(dis, 128, sizeof dis);
dis[0] = 0, in[0] = true, Q.push(0);
while (!Q.empty()) {
int u = Q.front();
Q.pop(), in[u] = false;
if (++cnt[u] > 3500) puts("-1"), exit(0);
for (int i = last[u]; i; i = Next[i])
if (dis[to[i]] < dis[u] + W[i]) {
dis[to[i]] = dis[u] + W[i];
if (!in[to[i]]) Q.push(to[i]);
}
}

long long ans = 0;
rep(i, 1, n) ans += dis[i];
printf("%lld\n", ans);

return 0;
}
@jia_shengyuan  2021-07-22 18:45 回复 举报

@天命之路 2021-07-22 18:53 回复 举报
if (++cnt[u] > 1000) puts("-1"), exit(0);
 if (++cnt[u] > 3500) puts("-1"), exit(0);

SPFA 可能被卡

@天命之路 2021-07-22 21:36 回复 举报