BOJ 10473 - 인간대포 (다익스트라)

https://www.acmicpc.net/problem/10473

 

<문제설명>

시작점, 끝점, 대포(최대 100개)의 좌표가 주어진다. 대포를 이용해서 시작점에서 끝점까지 가장 빠르게 이동하는 경우 그 시간을 구해라.

 

<풀이>

정점의 수가 극히 작으므로, 완전그래프라고 생각하고 풀어보자

 

정점 u는 좌표 (xu,yu) 정보를 가지고 있다.

 

u->v일 때 가중치는 대포를 타지 않거나 대포를 타는 경우중 짧은 시간. 즉, min(distance(u,v)/5, 2+(distance(u,v)-50)/5) 이다.

 

단 시작점을 0번, 도착점을 n+1번이라고 할 때, 시작점에선 대포를 탈 수 없음에 유의해야 한다.

 

typedef pair<double, double> P; //정점의 정의
typedef pair<double, int> PQ; //for pq
const int MAX = 1e2 + 5;
const double INF = 1e9;

P vtx[MAX];
inline double pita(int u, int v) {
	return sqrt(pow(vtx[u].first - vtx[v].first, 2) + pow(vtx[u].second - vtx[v].second, 2));
}

int main() {
	FAST;
	double sx, sy, ex, ey, dist[MAX]; cin >> sx >> sy >> ex >> ey;
	int n; cin >> n;
	vtx[0] = { sx,sy };
	for (int i = 1; i <= n; i++) cin >> vtx[i].first >> vtx[i].second;
	vtx[n + 1] = { ex,ey };

	fill(dist, dist + MAX, INF);
	dist[0] = 0;
	priority_queue<PQ, vector<PQ>, greater<PQ>> pq;
	pq.push({ dist[0],0 });
	bool chk[MAX]{ 0 };
	bool flag = true;

	while (!pq.empty()) {
		int u = pq.top().second; pq.pop();
		if (chk[u]) continue;
		chk[u] = true;

		for (int v = 1; v <= n + 1; v++) {
			double t1 = pita(u, v) / 5.0;
			double t2 = 2.0 + abs(pita(u, v) - 50) / 5.0;
			double t = flag ? t1 : min(t1, t2);
			if (dist[v] > dist[u] + t) {
				dist[v] = dist[u] + t;
				pq.push({ dist[v], v });
			}
		}
		flag = false;
	}

	cout << setprecision(10);
	cout << dist[n + 1] << '\n';
}