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

각 정점간의 최단 경로는 플로이드로 찾을 수 있습니다. O(N^3)인데 그럭저럭 넉넉합니다. 거쳐야하는 점을 v1, v2라고 하면 dist[1][v1]+dist[v1][v2]+dist[v2][N], dist[1][v2]+dist[v2][v1]+dist[v1][N]중 작은 값을 출력하면 됩니다. 단, 아예 도달할 수 없는 곳임을 확인하기 위한 과정은 포함이 되어있어야 합니다. 저는 연결된 두 점의 거리가 아무리 길어봐야 N*1000(<=800000) 임을 활용해서 도달할 수 있는 곳인지 아닌지를 체크했습니다.

https://github.com/encrypted-def/BOJ/blob/master/1504.cpp