【JOI2018Final】Commuter Pass（通勤票）

· · 题解

思路

首先我们考虑，选定了一条 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 的最短路上反方向行走的，需要对反图也跑一次。

代码流程如下：

参考代码

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