백준 10473

10473번: 인간 대포

 

  시작점에서 도착점까지 얼마나 빨리 갈 수 있는가 묻는 문제이다. 가장 빠른 경로를 응용하는 문제이고 음수 간선이 없으니 다익스트라를 이용할 수 있다는 것을 알 수 있다. 정점의 개수도 기껏해야 100개이므로 나올 수 있는 간선이 기껏해야 100^2개이다. 

 

  편리한 계산을 위해 한 정점에서 다른 정점으로 갈 때 걸리는 시간을 미리 구해두자. 가는 방법은 두 가지이다. 걸어가거나 먼저 대포를 탄 뒤 걸어가는 것이다. 시작점과 도착점에서 출발할 땐 반드시 걸어가야 한다. 대포의 경우 대부분은 대포를 타고 가는 것이 빠르겠지만 대포를 타고 날아가는 시간이 2초이므로, 대포 사이의 거리가 10m 미만이면 걸어가는 것이 더 빠르다. 이러한 경우를 다 따져 미리 데이터를 구해놓으면 이제 다른 일반 다익스트라 문제와 별 다를 것이 없다.

 

 

 - Source code link

github.com/Bibidi/Algorithms/blob/master/boj/boj%2010473.cpp