30 分钟场切但是史山，话说这题有紫吗？

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
const int N=1e5+10;
int a[N],d1[N],d2[N],v[N],v1[N],n,m,st1,ed1,st2,ed2,ans;
vector<PII>G[N];vector<int>pre[N],pre1[N],pre2[N];
void dij(int d[],int st)
{
	memset(v,0,sizeof(v));
	priority_queue<PII,vector<PII>,greater<PII>>q;
	d[st]=0;q.push({0,st});
	while(!q.empty())
	{
		int x=q.top().se;q.pop();
		if(v[x]==1)continue;v[x]=1;
		for(auto i:G[x])
		{
			int y=i.fi,w=i.se;
			if(d[y]>d[x]+w)
			{
				d[y]=d[x]+w;
				q.push({d[y],y});
			}
		}
	}
}
void dij1(int d[],int st)
{
	memset(v,0,sizeof(v));
	priority_queue<PII,vector<PII>,greater<PII>>q;
	d[st]=0;q.push({0,st});
	while(!q.empty())
	{
		int x=q.top().se;q.pop();
		if(v[x]==1)continue;v[x]=1;
		for(auto i:G[x])
		{
			int y=i.fi,w=i.se;
			if(d[y]>d[x]+w)
			{
				d[y]=d[x]+w;
				pre[y].clear();pre[y].push_back(x);
				q.push({d[y],y});
			}
			else if(d[y]==d[x]+w)pre[y].push_back(x);
		}
	}
}
int rd1[N],rd2[N],rd3[N],rd4[N],mx1[N],mx2[N],mx3[N],mx4[N];
void bt()
{
	deque<int>q;q.push_back(ed1);v1[ed1]=1;
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		for(int y:pre[x])
		{
			pre1[y].push_back(x);rd1[x]++;
			pre2[x].push_back(y);rd2[y]++;
			if(!v1[y])v1[y]=1,q.push_back(y);
		}
	}
}
void topo1()
{
	for(int i=1;i<=n;i++)mx1[i]=d1[i];
	deque<int>q;q.push_back(st1);
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		ans=min(ans,mx1[x]+d2[x]);
		for(int y:pre1[x])
		{
			mx1[y]=min(mx1[y],mx1[x]);
			rd1[y]--;if(rd1[y]==0)q.push_back(y);
		}
	}
}
void topo3()
{
	for(int i=1;i<=n;i++)mx3[i]=d2[i];
	deque<int>q;q.push_back(st1);
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		ans=min(ans,mx3[x]+d1[x]);
		for(int y:pre1[x])
		{
			mx3[y]=min(mx3[y],mx3[x]);
			rd3[y]--;if(rd3[y]==0)q.push_back(y);
		}
	}
}
void topo2()
{
	for(int i=1;i<=n;i++)mx2[i]=d2[i];
	deque<int>q;q.push_back(ed1);
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		ans=min(ans,mx2[x]+d1[x]);
		for(int y:pre2[x])
		{
			mx2[y]=min(mx2[y],mx2[x]);
			rd2[y]--;if(rd2[y]==0)q.push_back(y);
		}
	}
}
void topo4()
{
	for(int i=1;i<=n;i++)mx4[i]=d1[i];
	deque<int>q;q.push_back(ed1);
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		ans=min(ans,mx4[x]+d2[x]);
		for(int y:pre2[x])
		{
			mx4[y]=min(mx4[y],mx4[x]);
			rd4[y]--;if(rd4[y]==0)q.push_back(y);
		}
	}
}
signed main()
{
	cin>>n>>m>>st1>>ed1>>st2>>ed2;
	for(int i=1;i<=m;i++)
	{
		int x,y,c;cin>>x>>y>>c;
		G[x].push_back({y,c});
		G[y].push_back({x,c});
	}
	memset(d1,0x3f,sizeof(d1));dij1(d1,st1);
	memset(d1,0x3f,sizeof(d1));dij(d1,st2);
	memset(d2,0x3f,sizeof(d2));dij(d2,ed2);
	bt();ans=d1[ed2];
	memcpy(rd3,rd1,sizeof(rd1));
	memcpy(rd4,rd2,sizeof(rd2));
	topo1();topo2();
	topo3();topo4();
	cout<<ans;
	return 0;
}

思路

首先我们考虑，选定了一条 $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;
}