Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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);
}