F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:替用户ir1d发布如下信息,希望大家能够积极支持。 OI Wiki 致力于成为一个开放自由的 OI 知识整合站点,欢迎感兴趣的同学参与贡献 https://oi-wiki.org
Problem 4774. -- 修路

4774: 修路

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 633  Solved: 294
[Submit][Status][Discuss]

Description

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

Input

第一行三个整数 n, m,d,表示图的点数和边数。接下来的 m行,每行三个整数 ui, vi, wi,表示有一条 ui 与 vi 
之间,权值为 wi 的无向边。
1 <= d <= 4
2d <= n <= 10^4
0 <= m <= 10^4
1 <= ui, vi <= n
1 <= wi <= 1000

Output

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

Sample Input

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

Sample Output

8

HINT

Source

[Submit][Status][Discuss]

HOME Back