自动搬运

查看原文

来自洛谷，原作者为

	VainSylphid 美しい音色で世界が鳴った

搬运于2025-08-24 22:32:01，当前版本为作者最后更新于2023-08-05 15:28:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

首先我们考虑，选定了一条 $S$ 到 $T$ 的最短路后， $U$ 到 $V$ 的最短路是什么样的。它有可能不经过 $S$ 到 $T$ 的最短路，也有可能经过。

不难发现，如果 $U$ 到 $V$ 的最短路经过 $S$ 到 $T$ 的最短路，那么一定是一条形如 $U\rightarrow A\rightarrow B\rightarrow V$ 的路径，其中有且仅有 $A\rightarrow B$ 在 $S$ 到 $T$ 的最短路上。

证明很简单，假如有一条形如 $U\rightarrow A\rightarrow B\rightarrow C\rightarrow D\rightarrow V$ 的路径，其中 $A\rightarrow B$、$C\rightarrow D$ 在 $S$ 到 $T$ 的最短路上，$B\rightarrow C$ 不在在 $S$ 到 $T$ 的最短路上，由于原图边权都是正的，将 $B\rightarrow C$ 的路径替换为 $S$ 到 $T$ 的最短路上 $B\rightarrow C$ 的路径一定更优。

换言之，我们可以 $O(n^2)$ 枚举一条 $P\rightarrow Q$ 的路径，如果它位于 $S$ 到 $T$ 的最短路上，即 $dis_{S\rightarrow P}+dis_{P\rightarrow Q}+dis_{Q\rightarrow T}=dis_{S\rightarrow T}$，那么就用 $dis_{U\rightarrow P}+dis_{Q\rightarrow V}$ 和 $dis_{U\rightarrow Q}+dis_{P\rightarrow V}$ 更新最短路。有两种方案的原因是最短路有可能是在 $S$ 到 $T$ 的最短路上反方向行走的。

考虑优化。显然所有在某一条最短路径上的边构成了一个 DAG，那么我们就可以跑一遍 dp 求出 DAG 上能到达节点 $D$ 的所有节点中，到 $U$ 的最小距离 $low_D$，然后用 $low_D+dis_{D\rightarrow V}$ 更新答案即可。还是由于$U$ 到 $V$ 的最短路可能 $S$ 到 $T$ 的最短路上反方向行走的，需要对反图也跑一次。

代码流程如下：

• 跑四次 dijkstra 计算 $S$、$T$、$U$、$V$ 到每一个点的最短路，先用原图中 $U$ 到 $V$ 的最短路。
• 找出在 $S$ 到 $T$ 的最短路上的边，分别用原来的边和反边建一张 DAG。
• 在正图和反图上分别跑一次按拓扑序的 dp 计算 $U$ 到每个最短路上节点的最小距离，然后更新答案。

参考代码

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fLL
using namespace std;
ll n,m,s,t,u,v,x[200005],y[200005],z[200005],c1[100005],c2[100005],c3[100005],c4[100005],ans;
struct graph{
    struct edge{
	    ll v,w,nxt;
    }e[400005];
    ll h[100005],pos,dis[100005],vis[100005],du[100005],mind[100005],f[100005];
    void add(ll u,ll v,ll w)
    {
	    e[++pos] = {v,w,h[u]},h[u] = pos,du[v]++,f[u] = f[v] = 1;
    }
    struct node{
    	ll w,d;
    	bool operator <(const node &b) const
    	{
    		return d > b.d;
    	}
    };
    void dijkstra(ll s)
    {
    	priority_queue<node> q;
    	memset(dis,0x3f,sizeof dis),memset(vis,0,sizeof vis),q.push({s,0}),dis[s] = 0;
    	while(q.size())
    	{
    		node tmp = q.top();
    		q.pop(),vis[tmp.w] = 1;
	    	for(int i = h[tmp.w];i;i = e[i].nxt)
    			if(!vis[e[i].v] && dis[e[i].v] > tmp.d + e[i].w)
    			    q.push({e[i].v,tmp.d + e[i].w}),dis[e[i].v] = tmp.d + e[i].w;
    	}
    }
    void solve()
    {
    	queue<ll> q;
    	for(ll i = 1;i <= n;i++)
    	{
    	    mind[i] = c3[i];
    	    if(!du[i])
    	        q.push(i);
		}
    	while(q.size())
    	{
    		ll tmp = q.front();q.pop();
    		ans = min(ans,mind[tmp] + c4[tmp]);
    		for(ll i = h[tmp];i;i = e[i].nxt)
    		{
    		    du[e[i].v]--,mind[e[i].v] = min(mind[e[i].v],mind[tmp]);
    		    if(du[e[i].v] == 0)
    		        q.push(e[i].v);
			}
		}
	}
}g1,g2,g3;
int main()
{
	scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&s,&t,&u,&v);
	for(ll i = 1;i <= m;i++)
	    scanf("%lld%lld%lld",&x[i],&y[i],&z[i]),g1.add(x[i],y[i],z[i]),g1.add(y[i],x[i],z[i]);
	g1.dijkstra(s);
	for(ll i = 1;i <= n;i++)
	    c1[i] = g1.dis[i];
	g1.dijkstra(t);
	for(ll i = 1;i <= n;i++)
	    c2[i] = g1.dis[i];
	g1.dijkstra(u);
	for(ll i = 1;i <= n;i++)
	    c3[i] = g1.dis[i];
	g1.dijkstra(v);
	for(ll i = 1;i <= n;i++)
	    c4[i] = g1.dis[i];
	ans = c3[v];
	for(ll i = 1;i <= m;i++)
	{
	    if(c1[x[i]] + z[i] + c2[y[i]] == c1[t])
	        g2.add(x[i],y[i],0),g3.add(y[i],x[i],0);
	    else if(c1[y[i]] + z[i] + c2[x[i]] == c1[t])
	        g2.add(y[i],x[i],0),g3.add(x[i],y[i],0);
	}
	g2.solve(),g3.solve();
	printf("%lld",ans);
    return 0;
}