[BOJ][1504] 특정한 최단 경로

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

---

최단거리를 구하는 문제이다.

플로이드 알고리즘으로 먼저 모든 정점 간의 최단 거리를 구한다.

1 -> N 까지 이동하는데 반드시 지나야 하는 지점 2개가 a, b라면

나올 수 있는 경로는 

1 -> ... -> a -> ... -> b -> ... -> N

1 -> ... -> b -> ... -> a -> ... -> N

위 경로 2개이다.

따라서 

1 -> a 최단 거리 + a -> b 최단거리 + b -> N 최단거리

1 -> b 최단 거리 + b -> a 최단거리 + a -> N 최단거리

위 2개 중 짧은 거리가 정답이 된다.

만약 구한 짧은 거리가 무한대라면 불가능한 경우이므로 -1을 출력한다.

---

소스코드 : https://gist.github.com/fpdjsns/2537bd9b509dc10e1820232bc84e4741