1504번: 특정한 최단 경로 www.acmicpc.net 이 문제는 이전의 가중치를 포함한 최단 경로 문제에서 특정 두 정점을 항상 지나야 한다는 조건이 붙은 문제이다. 만약 최단 경로에 조건에 있는 두 정점이 있는 경우에는 아무 문제가 없다. 그냥 정점 1에서 정점 N까지의 최단 경로의 길이를 출력하면 된다. 문제는 그렇지 않은 경우로, 이는 크게 두 가지 경우로 나눌 수 있다. 두 정점을 v1, v2라 할 때 v1을 먼저 갔다가 v2를 가고, 마지막으로 N으로 가는 방법과, v2를 먼저 갔다가 v1을 가고, 마지막으로 N으로 가는 방법이 있다. 물론 각 정점을 경유할 때마다 그 정점들 사이에서는 최단 경로로 움직여야 할 것이고, 따라서 각 정점마다 그 정점을 시작점으로 하는 Dijkstra 알고리즘..
