AtCoder ABC 143 E - Travel by Car (青色, 500 点)

この Floyd--Warshall は天才すぎる！

問題へのリンク

問題概要

頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。

• 各頂点では燃料を補給できて、補給すると満タン (容量 の状態) になる
• 長さが の辺 を移動するときには、頂点 時点での容量は 以上でなければならない

以下の 個のクエリに答えよ:

• 二頂点 が与えられる。頂点 を容量満タンの状態で出発して、頂点 へとたどり着く方法のうち、補給回数の最小値を求めよ。(到達不可能な場合は -1)

制約

• 
• 

自分の解法： Dijkstra 法

の制約が、全頂点間の補給回数を求めさせることがありうることから、実質的に

• 全頂点間について、燃料補給回数の最小値を求めよ

という問題であることがわかる。なにはともあれ、まずは 2 点 を固定したときに、- 間に最小燃料補給回数を考えることにする。考えるべきパラメータが

• から へといたる経路
• 補給タイミング

と 2 つあってややこしい。こういうときはどちらかを固定してみると、考えやすくなることが多い。というわけで、まずは経路を固定して考えて見る。そしてら補給タイミングは実は明快で

• 空になるギリギリまで補給せずに進んで、ギリギリのタイミングで補給する

という Greedy で構わないことがわかる (なぜなら補給しなくても進める辺で先に補給するメリットはないため)。そして、さらに考えると、頂点 から出発して、各頂点についての

• (補給回数, 満タンの状態から使用した燃料量)

のペアについての最短路問題を解けばよいことがわかる。これは DIjkstra 法で自然に解ける。これを全頂点を始点としてやれば、全頂点間についての燃料補給回数の最小値が求まる。計算量は 。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int MAX = 310;
const long long INF = 1LL<<50;

long long G[MAX][MAX];
using pll = pair<long long, long long>;

int main() {
    int N, M; long long L;
    cin >> N >> M >> L;
    
    for (int i = 0; i < MAX; ++i) {
        for (int j = 0; j < MAX; ++j) G[i][j] = INF;
        G[i][i] = 0;
    }
    for (int i = 0; i < M; ++i) {
        int a, b; long long c;
        cin >> a >> b >> c; --a, --b;
        G[a][b] = G[b][a] = c;
    }

    vector<vector<pll> > dist(N, vector<pll>(N, {INF, INF}));
    for (int s = 0; s < N; ++s) {
        dist[s][s] = {0, 0};
        priority_queue<pair<pll, int>,
                       vector<pair<pll, int> >,
                       greater<pair<pll, int> > > que;
        que.push(make_pair(pll(0, 0), s));
        while (!que.empty()) {
            auto p = que.top();
            que.pop();
            
            long long v = p.second;
            long long kaisuu = p.first.first;
            long long used = p.first.second;
            
            if (p.first > dist[s][v]) continue;
            for (int nv = 0; nv < N; ++nv) {
                if (nv == v) continue;
                if (G[v][nv] > L) continue;
                long long nused = used + G[v][nv];
                pll np = {0, 0};
                if (nused > L) np = {kaisuu + 1, G[v][nv]};
                else np = {kaisuu, nused};

                if (chmin(dist[s][nv], np)) que.push(make_pair(np, nv));
            }
        }
    }

    int Q; cin >> Q;
    while (Q--) {
        int a, b; cin >> a >> b; --a, --b;
        
        long long res = dist[a][b].first;
        if (res >= INF) cout << -1 << endl;
        else cout << res << endl;
    }
}

別解： Floyd--Warshall の 2 回

公式 Editorial にある通り。すごく天才！！！