\(\mathtt{TAG}\)：最短路，DP，拓扑排序
题意
给定一个 \(n\) 个点 \(m\) 条边的无向图，边有边权。
给定两对点 \(s_1,t_1\) 和 \(s_2,t_2\)。
你可以选定 \(s_1\) 到 \(t_1\) 的一条最短路径，使得这些边的边权变为 \(0\)，要求操作之后 \(s_2\) 到 \(t_2\) 的最短路长度最小。
First. \(s_2\) 到 \(t_2\) 的最短路性质
我们发现，这条最短路会经过一段连续的选定边。
如何证明？
反证法。
假设选定路径为 \(e_1,e_2,\dots,e_k\)，如果 \(s_2\) 到 \(t_2\) 的最短路为 \(E_1,E_2,\dots, e_x,e_{x + 1}, E_{l},\dots,E_{r},e_{x+3},\dots,E_{len}\)。显然 \(e_{x+2} < \sum_{i=l}^{r} E_i\)，且选用 \(e_{x + 2}\) 能保证路径连续，是合法路径，显然比 \(s_2\) 到 \(t_2\) 的最短路更短，与最短路定义矛盾，所以这条最短路会经过一段连续的选定边。
Second. 求 \(s_2\) 到 \(t_2\) 的最短路
根据上文中的性质，设该连续路径的两个端点为 \(p, q\)，可以将该最短路分成 \(3\) 段：\(dis_{s_2, p} + 0 + dis_{q, t_2}\)。
不妨枚举 \(p\)，找到使得 \(dis_{q, t_2}\) 最小的在最短路中且可达的 \(q\)。
首先先将最短路 DAG 建出来。
这里直接判断一条边 \((u, v, w)\) 是否满足 \(dis_{s_1, u} + w + dis_{v, t_1} = dis_{s_1, t_1}\)，满足就加入图中。
由于是 DAG，所以 \(q\) 可以 DP 求解：
\[dp_u = \mathop {\max}_{v\in g_u} dp_v \]注意这里可以是 \(p \to q\) 也可以是 \(q \to p\)，所以同时再反过来维护一下使得 \(dis_{q, s_2}\) 最小的在最短路中且可达的 \(q\)。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int N = 2e5 + 10;
typedef pair<int, int> pi;
vector<pi> g[N];
vector<int> g2[N];
ll dis[4][N];
bool vis[N];
int n, m, s, t, s2, t2;
void dij (int s, ll dis[]) {
for (int i = 1; i <= n; i ++) dis[i] = 1e20;
memset(vis, 0, sizeof vis);
dis[s] = 0;
priority_queue<pi, vector<pi>, greater<pi> > q;
q.push({0, s});
while(!q.empty()) {
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for (auto e : g[u]) {
int v = e.first, w = e.second;
if(dis[u] + w < dis[v]) {
q.push({dis[v] = dis[u] + w, v});
}
}
}
}
ll dp[N], f[N], ans = 1e20;
int in[N];
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> s >> t >> s2 >> t2;
for (int i = 1; i <= m; i ++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w}), g[v].push_back({u, w});
}
dij(s, dis[0]), dij(t, dis[1]);
dij(s2, dis[2]), dij(t2, dis[3]);
for (int i = 1; i <= n; i ++) {
for (auto e : g[i]) {
int u = e.first, w = e.second;
if(dis[0][i] + dis[1][u] + w == dis[0][t]) {
g2[i].push_back(u);
// cout << i << ' ' << u << endl;
in[u] ++;
}
}
}
for (int i = 1; i <= n; i ++) {
dp[i] = dis[2][i];
f[i] = dis[3][i];
}
queue<int> q;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
for (auto v : g2[u]) {
dp[v] = min(dp[v], dp[u]);
f[v] = min(f[v], f[u]);
if(!(-- in[v])) q.push(v);
}
}
for (int i = 1; i <= n ;i ++) ans = min(ans, dp[i] + dis[3][i]), ans = min(ans, f[i] + dis[2][i]);
cout << ans << endl;
return 0;
}