ARC 008 C - THE☆たこ焼き祭り2012
問題文 : THE☆たこやき祭り2012
解法 :
基本はdijkstra. たこ焼きを投げる時間は1 秒ずつずれているので, 任意の順番で始点からの最短時間でたこ焼きを投げれる. 問題はどのような順番でたこ焼きを投げるか, ということである.
最も時間がかかる順に届ければ良いということが示せるが, 証明が大変... (writer さんの証明)
コード :
#include <cstdio> #include <cmath> #include <algorithm> #include <queue> using namespace std; double d(int x1, int y1, int x2, int y2) { return (sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))); } int main() { int N; int x[1024], y[1024], t[1024], r[1024]; double dist[1024]; scanf("%d", &N); for (int i = 0; i < N; i++){ scanf("%d %d %d %d", x + i, y + i, t + i, r + i); dist[i] = -1; } priority_queue<pair<double, int> > pq; for (pq.push(make_pair(0, 0)); pq.size(); pq.pop()){ pair<double, int> p = pq.top(); if (!(dist[p.second] < 0)) continue; dist[p.second] = -p.first; for (int i = 0; i < N; i++){ pq.push(make_pair(p.first - d(x[p.second], y[p.second], x[i], y[i]) / min(t[p.second], r[i]), i)); } } sort(dist, dist + N); double ans = 0; for (int i = 1; i < N; i++) ans = max(ans, dist[i] + N - i - 1); printf("%lf\n", ans); return (0); }