bzoj#P3575. [HNOI2014] 道路堵塞
[HNOI2014] 道路堵塞
题目描述
A 国有 座城市,依次标为 到 。同时,在这 座城市间有 条单向道路,每条道路的长度是一个正整数。现在,A 国交通部指定了一条从城市 到城市 的路径,并且保证这条路径的长度是所有从城市 到城市 的路径中最短的。不幸的是,因为从城市 到城市 旅行的人越来越多,这条由交通部指定的路径经常发生堵塞。
现在 A 国想知道,这条路径中的任意一条道路无法通行时,由城市 到 的最短路径长度是多少。
输入格式
第一行是三个用空格分开的正整数 和 ,分别表示城市数目、单向道路数目和交通部指定的最短路径包含多少条道路。
接下来 行,每行三个用空格分开的整数 , 和 ,表示存在一条由城市 到城市 的长度为 的单向道路。
这 行的行号也是对应道路的编号,即其中第 行对应的道路编号为 ,第 行对应的道路编号为 ,,第 行对应的道路编号为 。同时,在这 最后一行为 个用空格分开的整数 依次表示从城市 到城市 的由交通部指定的最短路径上的道路的编号。
输出格式
行,每行为一个整数,第 行()的整数表示删去编号为 的道路后从城市 到城市 的最短路径长度。
如果去掉后没有从城市 到城市 的路径,则输出 。
4 5 2
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
1 5
6
6
数据规模与约定
对于 的数据满足 ,。所用道路长度大于 小于 。
数据已加强 By Vfleaking
。