問題
ウサギとカメがレースをする。個の地点があり、地点間は本の道で繋がれている。ウサギの速さがm/s、カメの速さがm/sであると与えられるとき、カメが先に目的地に到着するような目的地、ウサギのスタート地点、カメのスタート地点の選び方の個数を求めよ。
解法
目的地をであると仮定したとき、ダイクストラ法を用いれば各地点への最短距離がわかる。これを、で割ったものを一つの配列に入れてソートすれば時間が到着時間が早いものから見ていくことができ、カメが着く時刻について、それ以降にウサギが到着する数をカウントしていけばよい。
反省
23分19秒(1WA)でAC。まぁ初手はダイクストラを考えるところからで、愚直にやるとになってしまうけどまぁ上手いことやればなんとかなりそうだったので書き始める。書きながら考えたら普通に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; }