ARC025 C - ウサギとカメ

問題文

http://arc025.contest.atcoder.jp/tasks/arc025_3

解法

制約をみて，なんとなく全頂点を始点としてダイクストラできるなーと検討はつく．
とりあえず，目的地を決め打ちしてしまって，目的地を始点にダイクストラする．
その後，得られた距離 d[i] をソートしておく．
次に，カメのスタート地点を決め打ちして，中継地点からの距離を D とする．
すると，ウサギは D / T < d[i] / R を満たすような d，つまり D * R / T < d[i] を満たすような中継点からスタートすれば良いことがわかる．
このような i の個数は，ソートしておいた距離の候補上で二分探索すれば求めることができる．
ただし，ウサギがカメより遅い場合は，同じスタート地点からスタートしないように -1 しておく必要がある．

計算量は O((N+M)NlogN)．

ソースコード

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

using ll = long long;
using weight = double;

constexpr weight INF = 1e9;

struct edge {
    int from, to;
    weight cost;

    bool operator<(edge const& rhs) const {
        return cost > rhs.cost;
    }
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

void add_edge(graph& g, int from, int to, weight cost) {
    g[from].push_back(edge{from, to, cost});
}

std::vector<weight> dijkstra(graph& g, int s) {
    using P = std::pair<weight, int>;
    std::vector<weight> d(g.size(), INF);
    std::priority_queue<P, std::vector<P>, std::greater<P>> que;
    fill(d.begin(), d.end(), INF);
    d[s] = 0;
    que.push(P{0, s});

    while(!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if(d[v] < p.first) {
            continue;
        }
        for(int i=0; i<g[v].size(); ++i) {
            edge e = g[v][i];
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P{d[e.to], e.to});
            }
        }
    }
    return d;
}


int main() {
    int N, M;
    double R, T;
    cin >> N >> M >> R >> T;
    graph g(N);
    for(int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        add_edge(g, a, b, c);
        add_edge(g, b, a, c);
    }

    ll res = 0;
    for(int i = 0; i < N; ++i) {
        auto d = dijkstra(g, i);
        sort(d.begin(), d.end());
        for(int j = 1; j < N; ++j) {
            auto t = upper_bound(d.begin(), d.end(), d[j] * R / T) - d.begin();
            res += N - t - (t <= j);
        }
    }
    cout << res << endl;
}

感想

ウサギよりカメが早いケース，WA生やさずに気づけたけど完全に罠．
まあカメって走ると意外と早いからね．