第2回ドワンゴからの挑戦状予選 C - メンテナンス明け

問題ページ

経路を一つ固定したとき、寝過ごしたときに最悪となるパターンについて考える。辺 $(u,v)$ で寝過ごした場合、かかる時間は (始点からuまでの時間) + (uから終点までの時間) + (終点からtまでの時間) となる。経路上の各辺で寝過ごした場合の時間のmaxが最悪となるパターンである。この時間が最小となるような経路を求める問題である。

終点からdijkstra

$\text{dist} \lbrack v \rbrack = ($ 頂点 $v$ から $t$ までで最悪な位置で寝た場合の最短時間 $)$ とする。辺 $(u,v)$ について $\text{dist} \lbrack u \rbrack = \max($ 辺重み $+ \text{dist} \lbrack v \rbrack ,$ 辺重み $+$ 路線の終点までの時間 $+$ 路線の終点からTまでの時間 $)$ となる。 $\text{dist} \lbrack t \rbrack =0$ からスタートしてdijkstra法のように最小のものから順に確定させていけばよい。

これが通常の最短距離を求めるdijkstra法と同様に最適解が求められることを確認する。最短経路問題では辺 $(u,v)$ を使用する場合、始点から $u$ までは最短距離で移動するのが最善である(負辺がないなら)。したがって、最短距離が確定した頂点から隣接した頂点に移動するパターンについて更新すればよい。

辺 $(u,v)$ で $v \to u$ に移動するとき、 $t$ から $v$ までは最短の移動時間とするのが最善である。よって、dijkstra法の要領で最短が確定した頂点から順に確定させていくことで最適解を得ることができる。

▶ソースコード(クリックで展開)

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n, m, s, t;  
    cin >> n >> m >> s >> t;  
    struct edge { ll to, cost, ep, cost_ep; };  
    vector<vector<edge>> g(n), rg(n);  
    REP(i, m) {  
        ll l;  
        cin >> l;  
        vector<ll> v(l), w(l-1);  
        REP(i, l) cin >> v[i];       
        REP(i, l-1) cin >> w[i];  
        vector<ll> rui(w);  
        FOR(i, 1, l-1) rui[i] += rui[i-1];  
        FOR(i, 1, l) {  
            // w[i-1…l-2]  
            ll s0 = (l-2<0?0:rui[l-2]) - (i-2<0?0:rui[i-2]);  
            // w[0…i-1]  
            ll s1 = (i-1<0?0:rui[i-1]);  
  
            g[v[i-1]].push_back({v[i], w[i-1], v[l-1], s0});  
            rg[v[i-1]].push_back({v[i], w[i-1], v[0], s1});  
            g[v[i]].push_back({v[i-1], w[i-1], v[0], s1});  
            rg[v[i]].push_back({v[i-1], w[i-1], v[l-1], s0});  
        }  
    }  
  
    vector<ll> dist_t(n, INF);  
    {  
        priority_queue<PII, vector<PII>, greater<PII>> que;  
        que.push({0, t});  
        dist_t[t] = 0;  
        while(que.size()) {  
            ll cost, vtx;  
            tie(cost, vtx) = que.top(); que.pop();  
            if(dist_t[vtx] < cost) continue;  
            for(auto e: g[vtx]) {  
                if(dist_t[e.to] > dist_t[vtx] + e.cost) {  
                    dist_t[e.to] = dist_t[vtx] + e.cost;  
                    que.push({dist_t[e.to], e.to});  
                }  
            }  
        }  
    }  
  
    vector<ll> dist(n, INF);  
    dist[t] = 0;  
    priority_queue<PII, vector<PII>, greater<PII>> que;  
    que.push({0, t});  
    while(que.size()) {  
        ll cost, vtx;  
        tie(cost, vtx) = que.top(); que.pop();  
        if(dist[vtx] < cost) continue;  
        for(auto e: rg[vtx]) {  
            ll nd = max(e.cost + dist[vtx], e.cost_ep + dist_t[e.ep]);  
            if(dist[e.to] > nd) {  
                dist[e.to] = nd;  
                que.push({nd, e.to});  
            }  
        }  
    }  
    cout << dist[s] << endl;  
  
    return 0;  
}

自分の誤答

$\text{dist} \lbrack v \rbrack = ($ 頂点 $s$ から $v$ まで移動する場合に最悪な位置で寝たパターン, $s$ から $v$ の移動時間 $)$ というペアを持つことにする。辺 $(u,v)$ について $\text{chmin}(\text{dist} \lbrack v \rbrack , (\max(\text{dist} \lbrack u \rbrack .\text{first}, \text{dist} \lbrack u \rbrack .\text{second} +$ 寝過ごした場合の分 $), \text{dist} \lbrack u \rbrack .\text{second} +$ 辺重み $)$ のペア $)$ と更新する。

dijkstra法のように行っても、これでは最適解を求めることはできない。辺 $u,v$ を移動する場合、 $\text{dist} \lbrack u \rbrack$ が最小のものが最適とは限らない。…らしいんだけどどういうケースなのか思いつかなかったのでランダム生成した。20頂点10路線で始点が0で終点が19のケースになっている。

▶ランダム生成で試してたら落ちたやつ

20 10 0 19  
9  
3 7 17 15 5 6 19 11 10   
51 94 44 58 9 8 78 11   
9  
6 13 10 5 7 19 11 17 14   
70 73 39 99 28 62 75 84   
18  
19 11 18 1 15 0 7 3 16 12 17 6 2 13 5 14 4 8   
37 44 96 27 98 97 52 57 78 81 10 57 26 23 43 73 57   
8  
4 6 9 1 13 0 7 12   
36 1 89 4 94 38 51   
6  
10 11 3 6 8 9   
7 9 70 35 46   
4  
11 6 1 0   
11 92 14   
8  
16 13 19 15 11 14 4 5   
77 95 39 83 79 71 56   
13  
10 8 11 7 14 6 9 0 17 1 2 4 5   
41 7 20 72 67 36 29 51 22 14 60 49   
17  
1 8 11 13 17 0 15 7 2 9 16 10 12 6 5 3 19   
72 61 86 44 72 35 54 10 35 52 88 23 97 54 23 60   
3  
18 2 1   
94 84

このケースで正しいのは0→7→11→19という経路で0→7で眠る場合の138となる
誤答の方は0→7→3→19という経路の149を出力する
0→7→11 とくる場合のdist[11]は(138,58)であるが、0→1→6→11 とくる場合のdist[11]は(136,117)でこちらの方が小さいため、0→7→11の方の経路は使用されない
ペアの辞書順で最小のものが常に正しいわけではないのでこのアルゴリズムはおかしい

dijkstra法を行うときはちゃんと条件を確認する必要がある

最短が確定した頂点から移動するような経路が必ず最適になるように実行
ちゃんと全順序になっていること

ferinの競プロ帳

競プロについてのメモ

第2回ドワンゴからの挑戦状予選 C - メンテナンス明け

終点からdijkstra

自分の誤答