[BOJ][Python] 백준 1504번 - 특정한 최단 경로

문제 링크: https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

---

문제 풀이

N이 800개여서 플로이드로 풀려 했다. O($N^{3}$)으로 되는줄 알았는데 시간 초과가 났다. 그래서 그냥 다익스트라로 풀었다.

s → v1 → v2 → e 혹은 s → v2 → v1 → e 중에서 짧은 거리를 출력해주면 된다.

s → v1, s → v2 의 거리를 구할 때 다익스트라 1번,

v1 → v2(= v2 → v1), v1(혹은 v2) → e 의 거리를 구할 때 다익스트라 1번,

위에서 v1 → e 를 구했다면 v2 → e 의 거리를 구할 때 다익스트라 1번으로 총 3번 써야한다.

만약 둘다 INF가 뜬다면 최단거리가 없으므로 -1을 출력해야 한다.

 

코드