[JOI2018]定期券 (Commuter Pass)

\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;
}