BOJ 10473 인간 대포

사용한 알고리즘

다익스트라 알고리즘

알고리즘 설명

시작점과 대포를 노드로 하는 그래프를 구성한다.
시작점으로 부터 대포까지 걸어가는 시간을 계산하여 시작점과 대포를 연결한다.
각 대포를 이용한 뒤 다른 대포까지 걸어가는 시간을 계산하여 각 대포들을 연결한다.
시작점으로 부터 위 그래프를 이용하여 다익스트라 알고리즘을 적용한다.
도착점까지 가는 최단 거리를 출력한다.

풀이

// baekjoon 10473 yechan
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define SQ(x) ((x)*(x))
typedef pair<double, int> P;

const int MAX_N=101;
const double wSpeed=5;
const double cSpeed=50;

int N;
double sx, sy, ex, ey;
pair<double, double> cannon[MAX_N];
vector<pair<int, double> > adj[MAX_N];

inline double dist(pair<double, double> &A, pair<double, double> &B) {
	return sqrt(SQ(A.first - B.first)+SQ(A.second - B.second));
}

int main() {
	scanf("%lf %lf", &sx, &sy);
	scanf("%lf %lf", &ex, &ey);
	scanf("%d", &N);
	// 시작점 0
	cannon[0] = make_pair(sx, sy);
	// 도착점 N+1
	cannon[N+1] = make_pair(ex, ey);

	// 대포 위치(1~N)
	for (int i=1; i<=N; i++)
		scanf("%lf %lf", &cannon[i].first, &cannon[i].second);

	// 각 대포(i)로 부터 다른 대포 또는 도착점(j) 연결
	for (int i=1; i<=N; i++) { // N+1 도착점으로 제외
		for (int j=1; j<=N+1; j++) {
			if (i == j) continue;
			adj[i].push_back(make_pair(j, 2.f + abs(cSpeed - dist(cannon[i], cannon[j]))/wSpeed));
		}
	}

	// 시작점으로 부터 각 대포와 도착지 까지 걸어가는 거리
	for (int i=1; i<=N+1; i++) {
		adj[0].push_back(make_pair(i, dist(cannon[0], cannon[i])/wSpeed));
	}

	// 다익스트라 알고리즘
	vector<double> dist(N+2, (double)(1LL<<60));
	vector<bool> visited(N+2, false);
	priority_queue<P, vector<P>, greater<P> > PQ;
	
	dist[0] = 0;
	PQ.push(P(0.f, 0));
	while (!PQ.empty()) {
		int curr;
		do {
			curr = PQ.top().second;
			PQ.pop();
		} while (!PQ.empty() && visited[curr]);
		if (visited[curr]) break;

		visited[curr] = true;
		for (int k=0; k<adj[curr].size(); k++) {
			double next = adj[curr][k].first, d = adj[curr][k].second;
			if (dist[next] > dist[curr] + d) {
				dist[next] = dist[curr] + d;
				PQ.push(make_pair(dist[next], next));
			}
		}
	}
	printf("%.6f\n", dist[N+1]);
	return 0;
}