/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 475 点
問題文
頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の重み付き単純連結無向グラフと正整数 K が与えられます。
辺 i\ (1\leq i\leq M) は頂点 u _ i と頂点 v _ i を結んでおり、重みは w _ i です。
このグラフの全域木 T に対して、T のコストを T に含まれる辺の重みの総和を K で割ったあまりで定めます。 このグラフの全域木のコストの最小値を求めてください。
制約
- 2\leq N\leq8
- N-1\leq M\leq\dfrac{N(N-1)}2
- 1\leq K\leq10^{15}
- 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M)
- 0\leq w _ i\lt K\ (1\leq i\leq M)
- 与えられるグラフは単純かつ連結
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M K u _ 1 v _ 1 w _ 1 u _ 2 v _ 2 w _ 2 \vdots u _ M v _ M w _ M
出力
答えを出力せよ。
入力例 1
5 6 328 1 2 99 1 3 102 2 3 86 2 4 94 2 5 95 3 4 81
出力例 1
33
与えられるグラフは次のようになります。
辺 1,3,5,6 の 4 本を含む全域木のコストは (99+86+81+95)\bmod{328}=361\bmod{328}=33 となります。 このグラフの全域木のコストはすべて 33 以上であるため、33 を出力してください。
入力例 2
6 5 998244353 1 2 337361568 1 6 450343304 2 3 61477244 2 5 745383438 4 5 727360840
出力例 2
325437688
このグラフのただ一つの全域木のコスト 325437688 を出力してください。
入力例 3
8 28 936294041850197 1 2 473294720906780 1 3 743030800139244 1 4 709363019414774 1 5 383643612490312 1 6 557102781022861 1 7 623179288538138 1 8 739618599410809 2 3 857687812294404 2 4 893923168139714 2 5 581822471860662 2 6 740549363586558 2 7 307226438833222 2 8 447399029952998 3 4 636318083622768 3 5 44548707643622 3 6 307262781240755 3 7 12070267388230 3 8 700247263184082 4 5 560567890325333 4 6 704726113717147 4 7 588263818615687 4 8 549007536393172 5 6 779230871080408 5 7 825982583786498 5 8 713928998174272 6 7 751331074538826 6 8 449873635430228 7 8 11298381761479
出力例 3
11360716373
入力や答えが 32\operatorname{bit} 整数に収まらない場合があることに注意してください。
Score : 475 points
Problem Statement
You are given a weighted simple connected undirected graph with N vertices and M edges, where vertices are numbered 1 to N, and edges are numbered 1 to M. Additionally, a positive integer K is given.
Edge i\ (1\leq i\leq M) connects vertices u_i and v_i and has a weight of w_i.
For a spanning tree T of this graph, the cost of T is defined as the sum, modulo K, of the weights of the edges in T. Find the minimum cost of a spanning tree of this graph.
Constraints
- 2\leq N\leq8
- N-1\leq M\leq\dfrac{N(N-1)}2
- 1\leq K\leq10^{15}
- 1\leq u_i\lt v_i\leq N\ (1\leq i\leq M)
- 0\leq w_i\lt K\ (1\leq i\leq M)
- The given graph is simple and connected.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K u_1 v_1 w_1 u_2 v_2 w_2 \vdots u_M v_M w_M
Output
Print the answer.
Sample Input 1
5 6 328 1 2 99 1 3 102 2 3 86 2 4 94 2 5 95 3 4 81
Sample Output 1
33
The given graph is shown below:
The cost of the spanning tree containing edges 1,3,5,6 is (99+86+81+95)\bmod{328}=361\bmod{328}=33. The cost of every spanning tree of this graph is at least 33, so print 33.
Sample Input 2
6 5 998244353 1 2 337361568 1 6 450343304 2 3 61477244 2 5 745383438 4 5 727360840
Sample Output 2
325437688
Print the cost of the only spanning tree of this graph, which is 325437688.
Sample Input 3
8 28 936294041850197 1 2 473294720906780 1 3 743030800139244 1 4 709363019414774 1 5 383643612490312 1 6 557102781022861 1 7 623179288538138 1 8 739618599410809 2 3 857687812294404 2 4 893923168139714 2 5 581822471860662 2 6 740549363586558 2 7 307226438833222 2 8 447399029952998 3 4 636318083622768 3 5 44548707643622 3 6 307262781240755 3 7 12070267388230 3 8 700247263184082 4 5 560567890325333 4 6 704726113717147 4 7 588263818615687 4 8 549007536393172 5 6 779230871080408 5 7 825982583786498 5 8 713928998174272 6 7 751331074538826 6 8 449873635430228 7 8 11298381761479
Sample Output 3
11360716373
Note that the input and the answer may not fit into a 32\operatorname{bit} integer.