bzoj#P3575. [HNOI2014] 道路堵塞

[HNOI2014] 道路堵塞

题目描述

A 国有 nn 座城市,依次标为 11nn。同时,在这 nn 座城市间有 mm 条单向道路,每条道路的长度是一个正整数。现在,A 国交通部指定了一条从城市 11 到城市 nn 的路径,并且保证这条路径的长度是所有从城市 11 到城市 nn 的路径中最短的。不幸的是,因为从城市 11 到城市 nn 旅行的人越来越多,这条由交通部指定的路径经常发生堵塞。

现在 A 国想知道,这条路径中的任意一条道路无法通行时,由城市 11nn 的最短路径长度是多少。

输入格式

第一行是三个用空格分开的正整数 n,mn,mll,分别表示城市数目、单向道路数目和交通部指定的最短路径包含多少条道路。

接下来 mm 行,每行三个用空格分开的整数 aabbcc,表示存在一条由城市 aa 到城市 bb 的长度为 cc 的单向道路。

mm 行的行号也是对应道路的编号,即其中第 11 行对应的道路编号为 11,第 22 行对应的道路编号为 22\cdots,第 mm 行对应的道路编号为 mm。同时,在这 最后一行为 ll 个用空格分开的整数 sp1,sp2,,splsp_1,sp_2,\cdots,sp_l 依次表示从城市 11 到城市 nn 的由交通部指定的最短路径上的道路的编号。

输出格式

ll 行,每行为一个整数,第 ii 行(i=1,2,,li=1,2,\cdots,l)的整数表示删去编号为 spisp_i 的道路后从城市 11 到城市 nn 的最短路径长度。

如果去掉后没有从城市 11 到城市 nn 的路径,则输出 1-1

4 5 2
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
1 5
6
6

数据规模与约定

对于 100%100\% 的数据满足 2<n<1052<n<10^51<m<2×1051<m<2\times 10^5。所用道路长度大于 00 小于 10410^4

数据已加强 By Vfleaking