1504 특정한 최단 경로

정점의 갯수가 간선의 갯수보다 극히 작으므로, 다익스트라를 사용하는 것이 올바르다. 노드를 2개를 반드시 거쳐야하므로, 나올 수 있는 경우의 수는

1 - n1 - n2 - n

1 - n2 - n1 - n이 나올 수 있게 된다

따라서 각 노드간의 최단거리를 구해서 그 합이 최소가 된다면 답을 구할 수 있게된다

 

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

https://github.com/surinoel/boj/blob/master/1504.cpp