AtCoder Regular Contest 025 C - ウサギとカメ

問題

ウサギとカメがレースをする。N個の地点があり、地点間はM本の道で繋がれている。ウサギの速さがRm/s、カメの速さがTm/sであると与えられるとき、カメが先に目的地に到着するような目的地A、ウサギのスタート地点B、カメのスタート地点Cの選び方の個数を求めよ。

解法

 目的地をiであると仮定したとき、ダイクストラ法を用いれば各地点への最短距離がわかる。これをRTで割ったものを一つの配列に入れてソートすれば時間が到着時間が早いものから見ていくことができ、カメが着く時刻について、それ以降にウサギが到着する数をカウントしていけばよい。

反省

 23分19秒(1WA)でAC。まぁ初手はダイクストラを考えるところからで、愚直にやるとO(N^3)になってしまうけどまぁ上手いことやればなんとかなりそうだったので書き始める。書きながら考えたら普通にvectorに押し込んで前から見るだけで良さそうだと思ったのでそれで書いて通した。カメの方が速い場合に削らなければいけない数を勘違いして1回WAを出してしまった。

 少数を使うことになっているので精度が不安だったり、最悪ケースについて実行時間が1361msだったりと、もうちょっと厳しいテストケースがあったらダメだったかもしれない。二分探索でやるのは思いつくべきだった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M, R, T;
    cin >> N >> M >> R >> T;

    vector<vector<pair<ll, ll>>> connect(N);
    for (ll i = 0; i < M; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        connect[a].push_back({ b, c });
        connect[b].push_back({ a, c });
    }

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        //iが目的地とする
        vector<ll> distance(N, INT_MAX);
        distance[i] = 0;
        struct Element {
            ll cost, curr;
            bool operator<(const Element& rhs) const {
                return cost > rhs.cost;
            }
        };
        priority_queue<Element> pq;
        pq.push({ 0, i });
        while (!pq.empty()) {
            auto t = pq.top();
            pq.pop();

            for (auto e : connect[t.curr]) {
                ll new_cost = t.cost + e.second;
                if (new_cost < distance[e.first]) {
                    distance[e.first] = new_cost;
                    pq.push({ new_cost, e.first });
                }
            }
        }
        
        vector<pair<double, ll>> times;
        times.reserve(2 * N - 2);
        for (ll j = 0; j < N; j++) {
            if (j == i) {
                continue;
            }

            times.push_back({ (double)distance[j] / R, 0 });
            times.push_back({ (double)distance[j] / T, 1 });
        }

        sort(times.begin(), times.end());

        ll rabbit_num = N - 1;
        for (auto p : times) {
            if (p.second == 0) {
                rabbit_num--;
            } else {
                ans += rabbit_num;
            }
        }
    }

    if (R < T) {
        //カメの方が早いとき同じ地点をカウントしてしまう分を引く
        ans -= N * (N - 1);
    }

    cout << ans << endl;
}