#P4774. [模板题][斯坦纳树]修路

    ID: 3892 传统题 1000ms 256MiB 尝试: 903 已通过: 286 难度: 8 上传者: 标签>CF2400提高+/省选-状压 DP子集 DP子掩码递推 (s-1)&maskDijkstra斯坦纳树

[模板题][斯坦纳树]修路

题目描述

村子间的小路年久失修,为了保障村子之间的往来,法珞决定带领大家修路。对于边带权的无向图 G=(V,E)G = (V, E),请选择一些边,使得 1≤i≤d1\le i \le d,ii 号节点和 n−i+1n - i + 1 号节点可以通过选中的边连通,最小化选中的所有边的权值和。

输入格式

第一行两个整数 n,mn, m,表示图的点数和边数。接下来的 mm 行,每行三个整数 ui,vi,wiu_i, v_i, w_i,表示有一条 uiu_i 与 viv_i 之间,权值为 wiw_i 的无向边。

输出格式

一行一个整数,表示答案,如果无解输出 -1

10 20 1
6 5 1
6 9 4
9 4 2
9 4 10
6 1 2
2 3 6
7 6 10
5 7 1
9 7 2
5 9 10
1 6 8
4 7 4
5 7 1
2 6 9
10 10 6
8 7 2
10 9 10
1 2 4
10 1 8
9 9 7
8

数据规模与约定

对于 100%100\% 的数据,1≤d≤41 \le d \le 4,2d≤n≤1042d \le n \le 10^4,0≤m≤1040 \le m \le 10^4,1≤ui,vi≤n1 \le u_i, v_i \le n,1≤wi≤1031 \le w_i \le 10^3 。