임의의 그래프가 주어졌을 때, 특정 두 노드 간의 최단 경로를 구하는 문제는 전형적이고 유명한 문제이다.

이를 구하기 위한 대표적인 알고리즘으론 dijkstra가 고안한 최단 경로 알고리즘이 있으며,

그 외에도 다양한 방법으로 최단 경로를 구할 수 있다.

지금 이 최단 경로 문제를 약간 변형한 문제를 풀어보자.

임의의 그래프가 주어지고, 시작점과 도착점이 주어졌을 때,

시작점과 도착점을 거친 다음, 다시 도착점에서 시작점을 거치게 될 때의 최단 경로를 구하는 문제를 풀어보자.

그리고 이 문제에서 제약조건은 다음과 같다.

그래프는 무 방향 그래프가 주어지게 되며, 음수의 가중치는 존재하지 않는다.

그리고 노드를 연결하는 간선은 최대 한번만 거칠 수 있으며, 노드를 여러번 거치는 것은 가능하다.

Tour timer 1s memory 256MB

Tour 1s 256MB