F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 3575. -- [Hnoi2014]道路堵塞

3575: [Hnoi2014]道路堵塞

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1057  Solved: 350
[Submit][Status][Discuss]

Description

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

Input

第一行是三个用空格分开的正整数N、M和L,分别表示城市数目、单向道路数目和交通部指定的最短路径包含多少条道路。
按下来M行,每行三个用空格分开的整数a、b和c,表示存在一条由城市a到城市b的长度为c的单向道路。
这M行的行号也是对应道路的编号,即其中第1行对应的道路编号为1,第2行对应的道路编号为2,…,第M行对应的道路编号为M。
最后一行为L个用空格分开的整数sp(1)…,,sp(L),依次表示从城市1到城市N的由交通部指定的最短路径上的道路的编号。
2<N<100000,1<M<200000。所用道路长度大于0小于10000。

Output

L行,每行为一个整数,第i行(i=1,2…,,L)的整数表示删去编号为sp(i)的道路后从城市1到城市N的最短路径长度。
如果去掉后没有从城市1到城市N的路径,则输出一1。

Sample Input

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

Sample Output

6
6

HINT

数据已加强By Vfleaking,另2017.9.1再加数据一组,未重测。

Source

[Submit][Status][Discuss]

HOME Back