시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 1024 MB | 234 | 27 | 18 | 9.783% |
순례자는 영원히 끝나지 않을 것만 같은 순례를 계속하고 있다. 지상에는 총 $N$ 개의 성지가 있어 $1$에서 $N$사이의 번호가 붙어있다. 또한 총 $M$ 개의 도로가 있어 $i$번 도로는 $x_i$번 성지와 $y_i$번 성지 사이를 $w_i$분에 오갈 수 있게 해준다.
순례자는 $1$번 성지에서 출발해 $N$번 성지에서 끝나는 새로운 순례를 계획 중이다. 이때 종교적인 의미를 담아 $1$번 성지와 $N$번 성지를 포함해 정확히 여덟 개의 서로 다른 성지를 방문하려고 한다. 단, 순례 중 한 성지를 두 번 이상 방문해서는 안 된다.
도로 위에서 이동하는 시간만 고려할 때, 순례에 걸리는 가장 짧은 시간을 구하여라.
첫 번째 줄에, 성지의 개수와 도로의 개수를 나타내는 자연수 $N$과 $M$이 주어진다.
다음 $M$ 개의 줄의 $i$ 번째 줄에, $i$번 도로의 정보 $x_i, y_i, w_i$ ($1 \leq x_i,y_i \leq N$, $x_i \neq y_i$, $1 \leq w_i \leq 10^8$)가 주어진다. 같은 두 성지 쌍을 연결하는 도로가 여러 번 주어지지 않는다.
첫 번째 줄에, 순례에 걸리는 가장 짧은 시간을 분 단위로 출력한다. 단, 조건을 만족하는 순례가 존재하지 않을 경우 -1
을 출력한다.
10 10 1 2 2 2 3 2 3 4 2 4 5 2 5 6 2 6 7 2 7 10 2 3 8 1 8 9 5 9 6 1
14
8 8 1 2 1 2 3 1 3 4 1 4 8 1 1 5 1 5 6 1 6 7 1 7 8 1
-1
Contest > BOJ User Contest > 전시관 > 제1 전시관 3번