세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 가 문제 내용입니다.

주어진 두 정점을 반드시 거치면서 한번 이동했던 간선도 다시 이동할 수 있다면  아래와 같은 그래프가 있을 때 1번-2번-1번-3번-1번-4번 순으로 방문하게 되므로 총 비용은 3 + 3 + 2 + 2 + 4가 되고

아래와 같은 그래프가 있을 때 1번-2번-3번-2번-1번-4번 순으로 방문하게 되므로 총 비용은 2 + 3 + 3 + 2 + 4 인게 맞나요? 궁금해서 질문 남깁니다.