题解：P14038 [PAIO 2025] Adventure Plan

第一次给官方比赛投题，来写发题解 /se

子任务 \(1,3,4\) 随便乱做就好了，没啥技术含量。

设 \(x_u\) 表示从 \(0\) 到 \(u\) 路径的长度，那么一条有向边 \(u\stackrel{[l,r]}{\to}v\) 等价于一个限制条件 \(l\le x_v-x_u\le r\)。将题目转化为一个差分约束系统，根据三角不等式，只需在差分约束系统建图时连边 \(u\stackrel{r}{\to}v\) 和 \(v\stackrel{-l}{\to}u\) 即可。

容易想到，对于每一次加边操作，可以使用 Bellman-Ford 算法判断负环，没有负环就说明可以加边。最后跑一遍 Bellman-Ford 算法求出所有 \(x_u\)，对于一条边 \(u\to v\)，将其权值设置为 \(x_v-x_u\) 即可。

时间复杂度 \(O(nm+qn(m+q))\)，可以通过子任务 \(2,5\)，结合上面的算法可以获得 \(75\) 分。

每次加边都要重新跑一遍 \(O(nm)\) 的 Bellman-Ford 算法，时间开销过大。有没有其他最短路算法支持判断负环、求带有负权边的图的最短路呢？答案是有的。

初始时使用 Floyd-Warshall 算法求出每对点之间的最短路，每次加边时暴力使用这条边更新每对点，若存在 \(\operatorname{dis}(u,u)<0\) 则说明有负环。

时间复杂度 \(O(m+n^3+qn^2)\)，可以 AC 本题。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define endl '\n'
using namespace std;
typedef long long ll;template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}const ll inf = 0x3f3f3f3f3f3f3f3fll;int _N;
vector<ll> _dis;
vector<tuple<int, int>> _e;vector<bool> add_roads(int N, int M, int Q,vector<int> U, vector<int> V,vector<int> L, vector<int> R,vector<int> U2, vector<int> V2,vector<int> L2, vector<int> R2) {_N = N;_dis.resize(N);vector<vector<ll>> e(N, vector<ll>(N));rep(i, 0, N - 1)rep(j, 0, N - 1)e[i][j] = i == j ? 0LL : +inf;rep(i, 0, M - 1) {int u = U[i], v = V[i];ll l = L[i], r = R[i];_e.emplace_back(u, v);chkmin(e[u][v], +r);chkmin(e[v][u], -l);}rep(k, 0, N - 1)rep(i, 0, N - 1)rep(j, 0, N - 1)if(e[i][k] < +inf && e[k][j] < +inf)chkmin(e[i][j], e[i][k] + e[k][j]);vector<bool> ans(Q);rep(t, 0, Q - 1) {int u = U2[t], v = V2[t];ll l = L2[t], r = R2[t];vector<vector<ll>> f = e;rep(i, 0, N - 1)rep(j, 0, N - 1)if(f[i][u] < +inf && f[v][j] < +inf)chkmin(f[i][j], f[i][u] + r + f[v][j]);rep(i, 0, N - 1)rep(j, 0, N - 1)if(f[i][v] < +inf && f[u][j] < +inf)chkmin(f[i][j], f[i][v] - l + f[u][j]);bool ok = true;rep(i, 0, N - 1) if(f[i][i] < 0) ok = false;if(ok) {_e.emplace_back(u, v);e = f;}ans[t] = ok;}rep(i, 0, N - 1) _dis[i] = e[0][i];return ans;
}vector<int> assign_times() {int M = _e.size();vector<int> ans(M);rep(i, 0, M - 1) {auto [u, v] = _e[i];ans[i] = _dis[v] - _dis[u];}return ans;
}#ifdef LOCALint main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int N, M, Q;cin >> N >> M >> Q;vector<int> U(M), V(M), L(M), R(M);rep(i, 0, M - 1) cin >> U[i];rep(i, 0, M - 1) cin >> V[i];rep(i, 0, M - 1) cin >> L[i];rep(i, 0, M - 1) cin >> R[i];vector<int> U2(Q), V2(Q), L2(Q), R2(Q);rep(i, 0, Q - 1) cin >> U2[i];rep(i, 0, Q - 1) cin >> V2[i];rep(i, 0, Q - 1) cin >> L2[i];rep(i, 0, Q - 1) cin >> R2[i];vector<bool> ans = add_roads(N, M, Q,U, V, L, R, U2, V2, L2, R2);rep(i, 0, Q - 1) cout << ans[i] << " \n"[i == Q - 1];vector<int> dis = assign_times();int sz = dis.size();rep(i, 0, sz - 1) cout << dis[i] << " \n"[i == sz - 1];return 0;
}#endif