ACM/ICPC 2016 青岛网络赛赛题 Barricade

题意

有图G(N, M)，每条边具有相同的长度和不同的权值。现在有敌人从点N沿最短长度路径到点1。现在要求在部分边上设置障碍，使敌人无论怎么走总能碰到障碍，求这些切断的边的最小权值之和。

思路

分析

因为敌人走最短路径，所以要建立新图，新图中只能保留死路和最短路径。因为每条路的长度都相等，所以可以采用bfs来寻找最短路径。在建立新图之后对新图用网络流即可。
从点N开始使用dis记录到各点最短路。当bfs到点x，尝试使用点x松弛所有相连点i并在新图中添加路径(x,i)；但当bfs到点1并且点当前点x的长度大于dis[i]（广度优先搜索总是最短路的），则不使用该点更新dis。
这样得到的图只含有死路（在得到dis[i]前bfs的部分）和最短路径。
代码

需要注意的地方

有几个地方需要注意：

第一个是使用bfs建立新图时
第二个是这道题源是N，汇是1，是反过来的
第三个因为最短路，所以只要添加单向边就好。
在bfs更新dis的时候我把u和v搞反了。