JOI2019/2020 本選 D - オリンピックバス (Olympic Bus) 解説

想定解法と異なる面白い解法で解けたので共有します。
atcoder.jp

問題概要

$N(\leq 200)$ 頂点、 $M(\leq 50000)$ 辺の重み付き有向グラフが与えられる。高々1つの辺の向きを反転させて、頂点1→頂点N→頂点1の往復のコストを最小化せよ。ただし反転には、辺ごとに異なるコストがかかる。

解法

それぞれの辺を1つだけ反転させた際の、頂点1→頂点Nの最短距離さえ求めることができれば、頂点N→頂点1について同じ問題を解けば良い。よってこの問題を解くことを考える。
まず簡単に思いつくのは、全ての辺に関して実際に反転させたグラフでダイクストラを行うことである。これはダイクストラ一回当たり $O(N^2)$ 、全体で $O(MN^2)$ となり、間に合わない。*1頂点ごとに処理をすることを考えます。
元のグラフから、頂点 $i$ を始点とした辺を全て除いたグラフを $V$ とします。グラフ $V$ において、 $d_0(x)$ を頂点1から頂点 $x$ までの最短距離、 $d_1(x)$ を頂点 $x$ から頂点Nまでの最短距離とします。*2
ここで、頂点 $i$ と頂点 $j$ を結ぶ辺を反転させたときの最短距離を考えます。頂点 $i$ を通らないとすると $d_0(N)$ が最短となります。よって頂点 $i$ を通る場合の最短距離を求めれば良いです。頂点 $i$ を通るのは1回として良いため、頂点1→頂点 $i$ 及び頂点 $i$ →頂点Nの最短距離を考えて足せば良いです。
まず頂点1→頂点 $i$ を考えます。頂点 $i$ に入ってくる辺は、反転させた辺である場合と、そうでない場合があります。まずそうでない場合は、最短距離は $d_0(i)$ となります。次に入ってくる辺が反転させた辺であるとすると、その辺のコストを $c$ として最短距離は $d_0(j)+c$ となります。よってこの2つのminを取れば良いです。
続いて頂点 $i$ →頂点Nを考えます。頂点 $i$ から出ていく辺は、反転させた辺以外の辺です。それぞれの辺の行先を $j'$ コストを $c'$ とすると、最短距離は $d_1(j')+c'$ となります。これを反転させた辺以外の辺について足せば良いのですが、愚直に実装すると二乗かかってしまいます。なので小さい方から2つ覚えておくことでよしなにできます*3。1つだけ罠があって、 $i=N$ のときだけは、頂点 $i=N$ から辺は出ていかないので、最短距離を0とする必要があります。
以上で解くことができました。計算量は $O(N^3+M)$ となります。

実装

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

struct edge{
    int to,id;
    ll c;
    edge():to(0),c(0),id(0){}
    edge(int to,ll c,int id):to(to),c(c),id(id){}
};

constexpr ll inf=1ll<<59;
ll E[200][200],IE[200][200];

void dkstr(int n,int s,vector<ll>&d,bool iv=false,int be=0,int ban=-1){
    auto v=E;
    if(iv) v=IE;
    d.assign(n,inf);
    vector<bool> vis(n);
    d[s]=0;
    for(int i=0;i<n;++i) {
        ll tmp=inf;
        int k{-1};
        for(int j=0;j<n;++j){
            if(be==1&&j==ban) continue;
            if(!vis[j]&&d[j]<tmp) tmp=d[j],k=j;
        }
        if(k==-1) return;
        vis[k]=true;
        for(int j=0;j<n;++j) if(be!=2||j!=ban) d[j]=min(d[j],tmp+v[k][j]);
    }
}

vector<ll> solve(int n,int m,vector<vector<edge>>&e,vector<vector<edge>>&ie,bool f){
    vector<ll> a(m),d;
    for(int i=0;i<n;++i) if(!e[i].empty()){
        vector<ll> D0,D1;
        dkstr(n,0,D0,f,1,i);
        dkstr(n,n-1,D1,!f,2,i);
        int k=e[i].size();
        ll m1=inf,m2=inf;
        for(auto&ed:e[i]){
            if(D1[ed.to]+ed.c<m1) m2=m1,m1=D1[ed.to]+ed.c;
            else if(D1[ed.to]+ed.c<m2) m2=D1[ed.to]+ed.c;
        }
        for(auto&ed:e[i]) a[ed.id]=min(D0[n-1],min(D0[i],D0[ed.to]+ed.c)+(i==n-1?0:(D1[ed.to]+ed.c==m1?m2:m1)));
    }
    return a;
}

int main(){
    int n,m,u,v;
    ll c;
    cin>>n>>m;
    for(int i=0;i<n;++i) for(int j=0;j<n;++j) E[i][j]=IE[i][j]=inf;
    vector<vector<edge>> e(n),ie(n);
    vector<ll> d(m);
    for(int i=0;i<m;++i){
        cin>>u>>v>>c>>d[i];
        --u,--v;
        e[u].emplace_back(v,c,i);
        ie[v].emplace_back(u,c,i);
        E[u][v]=min(E[u][v],c);
        IE[v][u]=min(IE[v][u],c);
    }
    auto a=solve(n,m,e,ie,false),b=solve(n,m,ie,e,true);
    vector<ll> D0,D1;
    dkstr(n,0,D0);
    dkstr(n,0,D1,true);
    ll ans{inf};
    ans=min(ans,D0[n-1]+D1[n-1]);
    for(int i=0;i<m;++i) ans=min(ans,d[i]+a[i]+b[i]);
    cout<<(ans==inf?-1:ans)<<endl;
}

提出コード
 バチャ中の提出コード

感想

制約からN回ダイクストラと決め打ったら最初に思いついたのがこれでした。模範解答は最短経路に含まれる辺(高々N-1個)だけダイクストラするものでしたが、こっちもそれなりに自然じゃないかなーと思います。コンテスト中は $O((N+M)\log N)$ のダイクストラを書いていて、闇の定数倍高速化ゲームをしていました(カス)。それではー。