영일랜드

시간 제한1초메모리 제한1024 MB

요약
놀이기구가 최대 9개인 방향 다중 그래프에서 0번 정문에서 출발해 모든 놀이기구를 한 번씩만 들르고 돌아오는 경로의 최장 시간을 구한다.
난이도

보통10점 중 4점

유형
그래프, 완전 탐색, 비트 연산, 동적 계획법
정답자
아직 제출이 없습니다

문제

영일랜드는 하나의 정문과 NN개의 놀이기구로 이루어진 테마파크로 각각 식별 번호가 매겨져 있다. 정문은 00번, 놀이기구는 11번부터 NN번까지의 번호로 구분된다. 정문과 놀이기구 혹은 놀이기구와 놀이기구 사이에는 단방향 간선으로 이어진다. 두 장소를 잇는 간선은 여러 개일 수 있으며 출발 장소와 도착 장소가 같을 수도 있다.

영일랜드에 놀러 간 정민이는 영일랜드의 정문에서 출발해 모든 놀이기구를 한 번씩만 탑승하고 정문으로 돌아오는 경로의 최장 시간이 궁금하다. 영일랜드의 놀이기구는 매혹적이어서 안 타고 지나갈 수 없어 각 놀이기구에는 최대 한 번씩만 도달할 수 있다. 또한, 모든 놀이기구를 탑승할 때까지 정문을 경유할 수 없으며 놀이기구 탑승 시간은 무시한다.

호기심이 많은 정민이를 위해 최장 시간을 알려주자.

입력

첫 번째 줄에는 놀이기구의 개수 NN이 주어진다. (1≤N≤9)(1 \leq N \leq 9)

두 번째 줄에는 간선의 개수 MM이 주어진다. (0≤M≤10,000)(0 \leq M \leq 10\\,000)

다음 MM개의 줄에는 정문 또는 놀이기구의 식별 번호 u_iu\_i에서 v_iv\_i로 향하는 간선의 이동 시간인 정수 d_id\_i가 공백을 사이에 두고 차례로 주어진다. 간선의 이동 시간의 합은 2312^{31}보다 작다. (0≤u_i,v_i≤N;1≤d_i≤231−1)(0 \leq u\_i, v\_i \leq N; 1 \leq d\_i \leq 2^{31}-1)

출력

정민이가 정문에서 출발해 모든 놀이기구를 한 번씩 탑승하고 다시 정문으로 돌아오는 경로의 최장 시간을 출력한다. 만약 불가능하다면 -1을 출력한다.

예제2

  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. 예제 2

    입력
    2
4
0 1 18
0 2 20
1 0 10
1 2 15
    예상 출력
    -1