boj 13141 : Ignition

boj 13141 : Ignition

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

참여했던 대회인 펑션컵에서 출제되었던 문제.

dijkstra알고리즘을 이용하여 각 node까지 타는데 걸리는 최소시간을 구하고,

이를 이용하여 edge가 타는 시간을 구하였다.

일단 node가 탈 때까지 걸리는 시간을 구하고 나면 edge가 타는 시간은 조금만 생각해보면 구할 수 있다.

각각 시작점을 달리하여 dijkstra알고리즘을 돌렸기 때문에 시간복잡도는 NElogE.

다른사람들은 플로이드 알고리즘을 돌린 사람도 있는데, 이렇게해주면 N^3으로 E가 N^2에 가깝지 않으면 좀더 빠른것같다.