[백준 10473] 인간대포

분류 

다익스트라

요구사항

시작 위치에서 최소한의 시간으로 도착 위치로 도착하기

각 정점의 위치는 주어진다

 

풀이

정점에서 정점으로 이동하는데 최소거리가 되게 이동하기 -> 다익스트라

현재 정점에서 취할 수 있는 행동은 2가지이다

1. 도착 점까지 간다

2. 다른 정점으로 간다

크기가 100이니깐 모든 정점을 구하여 다익스트라를 사용할 수 있도록 한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>

using namespace std;
struct go {
	double x;
	double y;
};
struct go1 {
	int x;
	double y;
};
int n;
go map[110];
vector<go1> v[110];
double dist[110];
double get_dist(go a, go b) {
	double d = sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
	return d;
}
int main() {
	scanf("%lf%lf%lf%lf", &map[0].x, &map[0].y, &map[1].x, &map[1].y);
	scanf("%d", &n);
	for (int i = 2; i < n + 2; i++) {
		scanf("%lf%lf", &map[i].x, &map[i].y);
	}
	for (int i = 0; i < n + 2; i++) dist[i] = 987654321;
	// 0 위치에서는 다른 거리까지 걸어갈수 밖에 없다.
	//i 시작 위치 j 도착 위치
	for (int i = 0; i < n + 2; i++) {
		if (i == 1) continue;
		for (int j = 1; j < n + 2; j++) {
			if (i == j) continue;
			if (i == 0) {
				double nowdist = get_dist(map[i], map[j]) / 5.0;
				//	cout<<nowdist<<endl;
				v[0].push_back({ j,nowdist });
				continue;
			}
			if (i == 1) continue;

			double nowdistwalk = get_dist(map[i], map[j]) / 5.0;
			double nowdistcan = 2.0 + abs(get_dist(map[i], map[j]) - 50) / 5.0;
			double nowmin = min(nowdistcan, nowdistwalk);
			v[i].push_back({ j,nowmin });
			//	cout<<nowmin<<endl;
		}
	}
	priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
	dist[0] = 0;
	q.push({ 0,0 });
	while (!q.empty()) {
		int nownode = q.top().second;
		double nowdist = q.top().first;
		q.pop();
		for (int i = 0; i < v[nownode].size(); i++) {
			int nextnode = v[nownode][i].x;
			double nextdist = v[nownode][i].y;
			if (dist[nextnode] > nowdist + nextdist) {
				dist[nextnode] = nowdist + nextdist;
				q.push({ dist[nextnode],nextnode });
			}
		}
	}
	printf("%.6lf\n", dist[1]);
}