#CW60. 莫追(pursuit)
莫追(pursuit)
题目描述
给定一个含 个节点、 条有向边的图,节点编号为 。每条有向边从节点 指向节点 ,记作 ,权值为 。沿一条路径经过某条边时,必须遵守这条边的方向;边 不能反向当作 使用。
你可以选择一个整数 ,然后从图中删除任意 个节点以及与这些节点关联的全部边。删除后只保留其余 个节点和边。要求剩余图中存在一条从节点 到节点 的简单路径:路径从节点 出发,沿有向边前进,最终到达节点 ,并且同一个节点不能在路径中出现两次;这条路径必须恰好经过 个节点,包括起点和终点。
路径的代价是路径上所有有向边权值之和。需要在所有合法的删除方案和路径中,求代价最小的一个;如果不存在任何合法方案,输出 。
输入格式
从 pursuit.in 文件读入数据。
第一行输入 。接下来 行输入 ,表示有向边 及其权值。
输出格式
将结果输出到 pursuit.out 文件。
输出一个整数,表示最小边权和;无解输出 。
样例 1 输入
6 7
1 2 2
2 3 3
3 6 4
1 4 1
4 5 1
5 6 1
1 6 10
样例 1 输出
10
样例 1 解释
一种最优方案是删除节点 (此时 ),剩余图中取路径 ,路径恰好经过 个节点,代价为 。
数据范围
对于全部数据,满足 ,,,,。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 20 | ,,无特殊性质 | |
| 2 | ,,所有边权为 | ||
| 3 | ,,底层无向图是一条链 | ||
| 4 | ,,无特殊性质 | ||
| 5 | ,,无特殊性质 |