[BOJ]10473번: 인간 대포

 

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

---

suuntree님 풀이를 참고하여 해결하였습니다. (https://suuntree.tistory.com/152)

 

정점의 수가 작으므로 완전 그래프처럼 생각해도 해결할 수 있습니다.

 

출발점을 v[0], 도착점을 v[N]이라 놓고 나머지 중간 지점들을 입력받습니다.

 

특정 정점 N1과 N2의 거리 중 어떤 거리를 취할 지는 아래 두 가지 중 하나를 취하면 됩니다.

 

1. 대포를 사용하던가 

2. 그냥 걸어가던가 

 

두 정점 사이의 거리는 피타고라스 정리를 사용했고, getDistance 라는 함수로 구했습니다.

 

즉, minTime = min(getDistance(n1,n2)/5 , 2 + (getDistance(n1,n2) - 50) / 5 ) 입니다.

 

이런식으로 갱신하는 다익스트라를 구현하면 되겠습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ10473.cc