#CW60. 莫追(pursuit)

莫追(pursuit)

题目描述

给定一个含 NN 个节点、MM 条有向边的图,节点编号为 1,2,…,N1,2,\dots,N。每条有向边从节点 uu 指向节点 vv,记作 u→vu\to v,权值为 ww。沿一条路径经过某条边时,必须遵守这条边的方向;边 u→vu\to v 不能反向当作 v→uv\to u 使用。

你可以选择一个整数 kk,然后从图中删除任意 kk 个节点以及与这些节点关联的全部边。删除后只保留其余 N−kN-k 个节点和边。要求剩余图中存在一条从节点 11 到节点 NN 的简单路径:路径从节点 11 出发,沿有向边前进,最终到达节点 NN,并且同一个节点不能在路径中出现两次;这条路径必须恰好经过 kk 个节点,包括起点和终点。

路径的代价是路径上所有有向边权值之和。需要在所有合法的删除方案和路径中,求代价最小的一个;如果不存在任何合法方案,输出 −1-1。

输入格式

从 pursuit.in 文件读入数据。

第一行输入 N,MN,M。接下来 MM 行输入 u,v,wu,v,w,表示有向边 u→vu\to v 及其权值。

输出格式

将结果输出到 pursuit.out 文件。

输出一个整数,表示最小边权和;无解输出 −1-1。

样例 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 解释

一种最优方案是删除节点 2,42,4(此时 k=2k=2),剩余图中取路径 1→61\to 6,路径恰好经过 22 个节点,代价为 1010。

数据范围

对于全部数据,满足 1≤N≤5001\le N\le 500,1≤M≤200001\le M\le 20000,1≤u,v≤N1\le u,v\le N,1≤w≤1091\le w\le 10^9,0≤k≤N0\le k\le N。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 20 1∼41\sim 4 N≤10N\le 10,M≤20M\le 20,无特殊性质
2 5∼85\sim 8 N≤500N\le 500,M≤2000M\le 2000,所有边权为 11
3 9∼129\sim 12 N≤500N\le 500,M≤2000M\le 2000,底层无向图是一条链
4 13∼1613\sim 16 N≤100N\le 100,M≤5000M\le 5000,无特殊性质
5 17∼2017\sim 20 N≤500N\le 500,M≤20000M\le 20000,无特殊性质