| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 511 | 241 | 193 | 44.266% |
영일랜드는 하나의 정문과 $N$개의 놀이기구로 이루어진 테마파크로 각각 식별 번호가 매겨져 있다. 정문은 0ドル$번, 놀이기구는 1ドル$번부터 $N$번까지의 번호로 구분된다. 정문과 놀이기구 혹은 놀이기구와 놀이기구 사이에는 단방향 간선으로 이어진다. 두 장소를 잇는 간선은 여러 개일 수 있으며 출발 장소와 도착 장소가 같을 수도 있다.
영일랜드에 놀러 간 정민이는 영일랜드의 정문에서 출발해 모든 놀이기구를 한 번씩만 탑승하고 정문으로 돌아오는 경로의 최장 시간이 궁금하다. 영일랜드의 놀이기구는 매혹적이어서 안 타고 지나갈 수 없어 각 놀이기구에는 최대 한 번씩만 도달할 수 있다. 또한, 모든 놀이기구를 탑승할 때까지 정문을 경유할 수 없으며 놀이기구 탑승 시간은 무시한다.
호기심이 많은 정민이를 위해 최장 시간을 알려주자.
첫 번째 줄에는 놀이기구의 개수 $N$이 주어진다. $(1 \leq N \leq 9)$
두 번째 줄에는 간선의 개수 $M$이 주어진다. $(0 \leq M \leq 10,000円)$
다음 $M$개의 줄에는 정문 또는 놀이기구의 식별 번호 $u_i$에서 $v_i$로 향하는 간선의 이동 시간인 정수 $d_i$가 공백을 사이에 두고 차례로 주어진다. 간선의 이동 시간의 합은 2ドル^{31}$보다 작다. $(0 \leq u_i, v_i \leq N; 1 \leq d_i \leq 2^{31}-1)$
정민이가 정문에서 출발해 모든 놀이기구를 한 번씩 탑승하고 다시 정문으로 돌아오는 경로의 최장 시간을 출력한다. 만약 불가능하다면 -1을 출력한다.
2 8 0 1 18 0 2 20 0 2 15 1 0 10 1 2 15 2 0 13 2 2 10 2 1 5
46
2 4 0 1 18 0 2 20 1 0 10 1 2 15
-1