题解

本题使用多源最短路 + 路径优化求解月票购买的最优方案问题。

算法思路：

1. 问题建模：

   • 需要从 $S$ 到 $T$，同时 $U$ 和 $V$ 两个点需要见面
   • 有两种方案：
     1. $U$ 和 $V$ 直接相遇：$dis_U[V]$
     2. $U$ 在 $S \to T$ 的某条最短路上与 $V$ 相遇

2. 四次Dijkstra：

   • dis_U[i]：从 $U$ 到点 $i$ 的最短距离
   • dis_V[i]：从 $V$ 到点 $i$ 的最短距离
   • dis_S[i]：从 $S$ 到点 $i$ 的最短距离
   • dis_T[i]：从 $T$ 到点 $i$ 的最短距离

3. 维护最小值：

   • min_S[i]：从 $S$ 沿最短路到 $i$ 的路径上，所有点到 $V$ 的最小距离
   • min_T[i]：从 $T$ 沿最短路到 $i$ 的路径上，所有点到 $V$ 的最小距离
   • 在Dijkstra过程中动态维护这些值

4. 转移更新：

   • 当 $dis_S[v] > dis_S[u] + w$，更新最短路时：
     • $min_S[v] = \min(dis_V[v], min_S[u])$
   • 当 $dis_S[v] = dis_S[u] + w$，路径长度相同时：
     • $min_S[v] = \min(min_S[v], min_S[u])$

5. 答案计算：

   • 初始答案：$ans = dis_U[V]$（$U$ 和 $V$ 直接相遇）
   • 枚举 $S \to T$ 最短路上的每个点 $i$（满足 $dis_S[i] + dis_T[i] = dis_S[T]$）：
     • $ans = \min(ans, dis_U[i] + min_T[i])$
     • $ans = \min(ans, dis_U[i] + min_S[i])$

时间复杂度：$O((n + m) \log n)$

这道题的关键在于理解如何在最短路上维护额外的最优信息。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
template <typename T>
T read() {T x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();} while (c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();} return x * f;}
template <typename T>
void write(T x) {if (x < 0) {putchar('-'); x = -x;} if (x > 9) write(x / 10); putchar('0' + x % 10);}
template <typename T>
void writeln(T x) {write(x); putchar('\n');}
template <typename T>
void write(T x, char c) {write(x); putchar(c);}
template <typename T>
T min_(T x, T y) {return x < y ? x : y;}
template <typename T>
T max_(T x, T y) {return x < y ? y : x;}
#define N 100005
#define M 200005
#define ll long long
int n, m, S, T, U, V;
struct node {
	int x; ll y;
	node () {}
	node (int x, ll y): x(x), y(y) {}
	friend bool operator < (node a, node b) {return a.y > b.y;}
};
node vl[M << 1];
int hd[N], nx[M << 1], cnt_edge = 1;
void add_edge(int u, int v, int w) {
	vl[++cnt_edge] = node(v, w);
	nx[cnt_edge] = hd[u];
	hd[u] = cnt_edge;
}
ll dis_S[N], dis_T[N], dis_U[N], dis_V[N];
bool vis[N];
ll min_S[N], min_T[N];
int main() {
	n = read<int>(); m = read<int>();
	S = read<int>(); T = read<int>();
	U = read<int>(); V = read<int>();
	for (int i = 1; i <= m; i++) {
		int x, y, z; x = read<int>(); y = read<int>(); z = read<int>();
		add_edge(x, y, z); add_edge(y, x, z);
	}
	/* Dijkstra U start */
	memset(dis_U, 0x3f, sizeof(dis_U));
	memset(vis, false, sizeof(vis));
	dis_U[U] = 0;
	priority_queue<node> q;
	q.push(node(U, 0));
	while (!q.empty()) {
		node nd = q.top(); q.pop();
		int u = nd.x;
		if (vis[u]) continue;
		vis[u] = true;
		for (int i = hd[u]; i; i = nx[i]) {
			int v = vl[i].x;
			if (dis_U[v] > dis_U[u] + vl[i].y) {
				dis_U[v] = dis_U[u] + vl[i].y;
				q.push(node(v, dis_U[v]));
			}
		}
	}
	/* Dijkstra U end   */
	/* Dijkstra V start */
	memset(dis_V, 0x3f, sizeof(dis_V));
	memset(vis, false, sizeof(vis));
	dis_V[V] = 0;
	q.push(node(V, 0));
	while (!q.empty()) {
		node nd = q.top(); q.pop();
		int u = nd.x;
		if (vis[u]) continue;
		vis[u] = true;
		for (int i = hd[u]; i; i = nx[i]) {
			int v = vl[i].x;
			if (dis_V[v] > dis_V[u] + vl[i].y) {
				dis_V[v] = dis_V[u] + vl[i].y;
				q.push(node(v, dis_V[v]));
			}
		}
	}
	/* Dijkstra V end   */
	/* Dijkstra S start */
	memset(dis_S, 0x3f, sizeof(dis_S));
	memset(vis, false, sizeof(vis));
	dis_S[S] = 0;
	for (int i = 1; i <= n; i++) min_S[i] = dis_V[i];
	q.push(node(S, 0));
	while (!q.empty()) {
		node nd = q.top(); q.pop();
		int u = nd.x;
		if (vis[u]) continue;
		vis[u] = true;
		for (int i = hd[u]; i; i = nx[i]) {
			int v = vl[i].x;
			if (dis_S[v] > dis_S[u] + vl[i].y) {
				dis_S[v] = dis_S[u] + vl[i].y;
				q.push(node(v, dis_S[v]));
				min_S[v] = min_(dis_V[v], min_S[u]);
			} else if (dis_S[v] == dis_S[u] + vl[i].y) {
				min_S[v] = min_(min_S[v], min_S[u]);
			}
		}
	}
	/* Dijkstra S end   */
	/* Dijkstra T start */
	memset(dis_T, 0x3f, sizeof(dis_T));
	memset(vis, false, sizeof(vis));
	dis_T[T] = 0;
	for (int i = 1; i <= n; i++) min_T[i] = dis_V[i];
	q.push(node(T, 0));
	while (!q.empty()) {
		node nd = q.top(); q.pop();
		int u = nd.x;
		if (vis[u]) continue;
		vis[u] = true;
		for (int i = hd[u]; i; i = nx[i]) {
			int v = vl[i].x;
			if (dis_T[v] > dis_T[u] + vl[i].y) {
				dis_T[v] = dis_T[u] + vl[i].y;
				q.push(node(v, dis_T[v]));
				min_T[v] = min_(dis_V[v], min_T[u]);
			} else if (dis_T[v] == dis_T[u] + vl[i].y) {
				min_T[v] = min_(min_T[v], min_T[u]);
			}
		}
	}
	/* Dijkstra T end   */
	ll ans = dis_U[V];
	for (int i = 1; i <= n; i++) if (dis_S[i] + dis_T[i] == dis_S[T]) {
		ans = min_(ans, dis_U[i] + min_T[i]);
		ans = min_(ans, dis_U[i] + min_S[i]);
	}
	writeln(ans);
	return 0;
}