글 읽기 - 대회 TC도 다 맞는데 시작하자마자 틀렸다고 나옵니다.

kinssang 4년 전 1

다익스트라를 사용해서 시작점으로부터 각 대포까지 도달하는 최단 시간을 구하고,

답은 시작점으로부터 도착점까지 걸어가는 시간으로 초기화를 한 다음,

각 대포에서 도착점에 도달하는 시간 + 시작점으로부터 그 대포까지 도달하는 시간이 답 보다 작으면 그걸 답으로 취하는 방식의 알고리즘을 활용하여 답을 구했습니다.

근데 채점 시작하자마자 틀렸다고 나오네요.

대회 공식 TC는 http://cs.baylor.edu/~hamerly/...

에서 얻었습니다. 채점 시 사용한 소스는

https://gist.github.com/kinssa...

에서 보실 수 있습니다.

#include <stdio.h>
#include <queue>
#include <math.h>
#include <algorithm>

struct point
{
	double x;
	double y;
};

struct element
{
	int index;
	double time;
	element(int index, double time) : index(index), time(time) {}
};

bool operator<(const element &a, const element &b)
{
	return (a.time > b.time);
}

double dist(point a, point b)
{
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

int main()
{
	point st, ed, cannon[100];
	int n;
	double time[100], answer;
	bool visit[100] = {};
	std::priority_queue<element> pq;
	scanf("%lf %lf %lf %lf %d", &st.x, &st.y, &ed.x, &ed.y, &n);
	answer = dist(st, ed) / 5.0;
	for (int i = 0; i < n; i++)
	{
		scanf("%lf %lf", &cannon[i].x, &cannon[i].y);
		time[i] = dist(st, cannon[i]) / 5.0;
		pq.push(element(i, time[i]));
	}
	while (!pq.empty())
	{
		double cur_time = pq.top().time;
		int index = pq.top().index;
		pq.pop();
		if (visit[index]) continue;
		visit[index] = true;
		time[index] = cur_time;
		for (int i = 0; i < n; i++)
		{
			if (i == index || visit[i]) continue;
			double temp_time = cur_time + std::min(2.0 + abs(50.0 - dist(cannon[index], cannon[i])) / 5.0, dist(cannon[index], cannon[i]) / 5.0);
			if (temp_time < time[i])
			{
				time[i] = temp_time;
				pq.push(element(i, time[i]));
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		double temp_time = time[i] + std::min(2.0 + abs(50.0 - dist(cannon[i], ed)) / 5.0, dist(ed, cannon[i]) / 5.0);
		if (temp_time < answer) answer = temp_time;
	}
	printf("%.6lf\n", answer);
	return 0;
}