1963 : Tour
- 제한시간
- 1000 ms
- 메모리제한
- 256 MB
- 해결횟수
- 2 회
- 시도횟수
- 16 회
문제
임의의 그래프가 주어졌을 때, 특정 두 노드 간의 최단 경로를 구하는 문제는 전형적이고 유명한 문제이다.
이를 구하기 위한 대표적인 알고리즘으론 dijkstra가 고안한 최단 경로 알고리즘이 있으며,
그 외에도 다양한 방법으로 최단 경로를 구할 수 있다.
지금 이 최단 경로 문제를 약간 변형한 문제를 풀어보자.
임의의 그래프가 주어지고, 시작점과 도착점이 주어졌을 때,
시작점과 도착점을 거친 다음, 다시 도착점에서 시작점을 거치게 될 때의 최단 경로를 구하는 문제를 풀어보자.
그리고 이 문제에서 제약조건은 다음과 같다.
그래프는 무 방향 그래프가 주어지게 되며, 음수의 가중치는 존재하지 않는다.
그리고 노드를 연결하는 간선은 최대 한번만 거칠 수 있으며, 노드를 여러번 거치는 것은 가능하다.
입력형식
첫 번째 줄에는 노드의 개수 N(2≤N≤100)이 주어진다.
그 다음 줄에는 노드를 연결하는 간선의 개수 M(1≤M≤N*N)이 주어진다.
그 다음 줄부터 M개의 줄에는 노드를 연결하는 간선의 정보가 주어지는데,
연결되는 노드의 번호 2개가 주어지고 그 다음에는 해당 간선의 가중치가 주어진다.
노드의 번호는 1이상 N이하로 주어지며, 간선의 경우 가중치는 1이상 10000이하의 정수이다.
두 개의 노드간의 간선은 한 개 보다 많이 존재할 수 없다.
(다시 말해서 두 노드 사이에 여러 개의 간선이 존재 할 수 없다는 것이다.)
출력형식
주어진 그래프에 대한 1번 노드에서 N번 노드를 거치고 다시 1번 노드로 되돌아 올 경우의 최단 경로의 값을 출력한다.
만약 이러한 경우가 존재하지 않을 경우 -1을 출력한다.
입력 예3 3 1 3 10 2 1 20 3 2 50 |
출력 예80 |
입력 예9 12 1 2 10 1 3 10 1 4 10 2 5 10 3 5 10 4 5 10 5 7 10 6 7 10 7 8 10 6 9 10 7 9 10 8 9 10 0 |
출력 예-1 |