从 $S, U, V$ 分别进行 dijkstra。

我们记 $du_x$ 为 $U$ 到 $x$ 的最短路径长度，$dv_x$ 同理。取一条 $S$ 到 $T$ 的最短路，记该路径为 $p$，则答案为 $\min\limits_{x\in p}du_x +\min\limits_{x\in p}dv_x$。

把 $S$ 到 $T$ 所有可能的最短路上的边保留，方向钦定为 dijkstra 转移的反方向。于是形成了一张以 $T$ 为起点的 DAG。

我们在 DAG 上进行 dp。对每个点 $x$ 记录 $pu_x$ 和 $pv_x$，表示 $x$ 到 $T$ 选取某条路径，其中 $du$ 和 $dv$ 的最小值，满足 $pu_x + pv_x$ 尽可能优。

考虑一个转移。最开始令 $pu_x = pv_x = \infin$，若记录能到达 $x$ 点的集合为 $A$，则对于每个点 $y\in A$，若 $\min(pu_y,du_x) +\min(pv_y+du_x)\le\min(pu_x,du_x)+\min(pv_x+dv_x)$，则使 $pu_x \leftarrow pu_y$，$pv_x\leftarrow pv_y$。

所有的 $y\in A$ 都转移完了之后（也就是拓扑排序中 $x$ 点入度为 $0$ 时），我们令 $pu_x \leftarrow \min(pu_x,du_x)$，$pv_x\leftarrow \min(pv_x+dv_x)$，然后再向外转移。

这部分的代码实现：

ll rd[N], pu[N], pv[N]; // rd 为入度
vector <ll> frm[N]; // frm[x] 为 x 的出边对应的点集
void top_sort() {
	for (int i = 1; i <= n; i++) pu[i] = INF, pv[i] = INF;
	pu[t] = du[t], pv[t] = dv[t];
	queue <ll> q; q.push(t); 
	while (!q.empty()) {
		ll y = q.front(); q.pop();
		for (auto x : frm[y]) {
			if (min(pu[x], du[x]) + min(pv[x], dv[x]) >= min(pu[y], du[x]) + min(pv[y], dv[x])) pu[x] = pu[y], pv[x] = pv[y];
			rd[x]--;
			if (rd[x] == 0) {
				pu[x] = min(pu[x], du[x]);
				pv[x] = min(pv[x], dv[x]);
				q.push(x);
			}
		}
	} return;
}

这东西假的离谱（？）。想象中有个样例：

其中黑色字体为 $(du_x, dv_x)$，红色字体为 $\color{red}(pu_x, pv_x)$。我们发现对于 $4$ 号点，选择向 $5$ 走时答案为 $99+1=100$，向 $6$ 号点走时答案为 $2+2=4$，于是选择了 $6$ 号点。

进而，实际选择了标红的这条最短路。但显然正确答案应该是 $S-2-4-5-T$ 这条最短路，能得到 $1+1=2$ 的最小答案。

请大佬构造一组能够卡掉这个做法的数据，或者证明这样的数据构造不出来，万分感谢！！！

提交记录