E - 配達ドライバーの巡回 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

ある地域には N 個の町があり、町には 1 から N までの番号が付けられています。いくつかの町の間には道路が整備されており、道路はすべて双方向に通行可能で、全部で M 本あります。i 番目の道路は町 U_i と町 V_i を結んでおり、この道路を通って移動するのにかかる時間は W_i です。なお、すべての町が道路で互いに行き来できるとは限りません。

高橋君は配達ドライバーであり、町 1 にある配送センターから出発して、N 個すべての町に荷物を届けた後、町 1 の配送センターに戻ってこなければなりません。具体的には、町 1 から出発し、道路を通って町から町へ移動することを繰り返して、すべての町を少なくとも 1 回ずつ訪問し、最終的に町 1 に戻る経路をとります。同じ町を複数回訪問したり、同じ道路を複数回通ったりすることは許されます。

このような経路における、通った道路の移動時間の総和の最小値を求めてください。同じ道路を複数回通った場合は、通るたびにその道路の移動時間が加算されます。条件を満たす経路が存在しない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 15
  • 1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i（自己ループはない）
  • i \neq j ならば \{U_i, V_i\} \neq \{U_j, V_j\}（同じ町の組を結ぶ道路は高々 1 本）
  • 1 \leq W_i \leq 10^6
  • 入力はすべて整数である

入力

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 1 行目には、町の数 N と道路の数 M がスペース区切りで与えられる。
  • 続く M 行では、各道路の情報が与えられる。そのうち i 行目では、i 番目の道路が結ぶ 2 つの町の番号 U_i, V_i と、その道路の移動時間 W_i がスペース区切りで与えられる。

出力

高橋君がすべての町を少なくとも 1 回ずつ訪問し、町 1 に戻るために必要な移動時間の総和の最小値を 1 行で出力せよ。条件を満たす経路が存在しない場合は -1 を出力せよ。

入力例 1

4 4
1 2 10
2 3 15
3 4 20
4 1 25

出力例 1

70

入力例 2

4 2
1 2 5
3 4 8

出力例 2

-1

入力例 3

6 7
1 2 3
1 3 10
2 3 4
2 4 7
3 5 2
4 6 5
5 6 6

出力例 3

30

Score : 433 pts

Problem Statement

There are N towns in a region, numbered from 1 to N. Some towns are connected by roads, all of which are bidirectional, and there are M roads in total. The i-th road connects town U_i and town V_i, and the time required to travel along this road is W_i. Note that it is not necessarily the case that all towns are reachable from each other via roads.

Takahashi is a delivery driver. He must depart from the distribution center located in town 1, deliver packages to all N towns, and then return to the distribution center in town 1. Specifically, he starts from town 1, repeatedly moves from town to town via roads, visits every town at least once, and finally returns to town 1. He is allowed to visit the same town multiple times and traverse the same road multiple times.

Find the minimum total travel time of roads traversed along such a route. If the same road is traversed multiple times, its travel time is added each time it is traversed. If no valid route exists, output -1.

Constraints

  • 2 \leq N \leq 15
  • 1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i (no self-loops)
  • If i \neq j, then \{U_i, V_i\} \neq \{U_j, V_j\} (there is at most one road between any pair of towns)
  • 1 \leq W_i \leq 10^6
  • All input values are integers

Input

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • The first line contains the number of towns N and the number of roads M, separated by a space.
  • The following M lines each contain information about a road. The i-th of these lines contains the numbers of the two towns U_i, V_i connected by the i-th road, and the travel time W_i of that road, separated by spaces.

Output

Output in a single line the minimum total travel time required for Takahashi to visit every town at least once and return to town 1. If no valid route exists, output -1.

Sample Input 1

4 4
1 2 10
2 3 15
3 4 20
4 1 25

Sample Output 1

70

Sample Input 2

4 2
1 2 5
3 4 8

Sample Output 2

-1

Sample Input 3

6 7
1 2 3
1 3 10
2 3 4
2 4 7
3 5 2
4 6 5
5 6 6

Sample Output 3

30