#2287. 道路堵塞

    ID: 2287 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest2460来源:qoj.ac数据:公开样例最短路径

道路堵塞

道路堵塞

题目描述

第3 页,共5 页 

第2 题:道路堵塞(road),运行时限1s,内存上限128M 【问题描述】

A 国有N 座城市,依次标为1 到N。同时,在这N 座城市间有M 条单向道路,每条道路 的长度是一个正整数。现在,A 国交通部指定了一条从城市1 到城市N 的路径,并且保证这条 路径的长度是所有从城市1 到城市N 的路径中最短的。

不幸的是,因为从城市1 到城市N 旅行的人越来越多,这条由交通部指定的路径经常发 生堵塞。现在A 国想知道,这条路径中的任意一条道路无法通行时,由城市1 到N 的最短路 径长度是多少。 【输入格式】 输入文件名为road.in。 输入文件第一行是三个用空格分开的正整数N、M和L,分别表示城市数目、单向道路数 目和交通部指定的最短路径包含多少条道路。 接下来M行,每行三个用空格分开的整数a、b和c,表示存在一条由城市a到城市b的长度 为c的单向道路。这M行的行号也是对应道路的编号,即其中第1行对应的道路编号为1,第2行 对应的道路编号为2,…,第M行对应的道路编号为M。 最后一行为L个用空格分开的整数sp(1),…,sp(L),依次表示从城市1到城市N的由交通部指 定的最短路径上的道路的编号。 【输出格式】 输出文件名为road.out。 输出文件包含L 行,每行为一个整数,第i 行(i=1,2,…,L)的整数表示删去编号为sp(i)的道 路后从城市1 到城市N 的最短路径长度。如果去掉后没有从城市1 到城市N 的路径,则输出 -1。 【输入输出样例】 road.in road.out 6 6 4 1 2 1 2 3 1 -1 7 7

2014‐05‐11  3 4 1 4 6 1 2 5 2 5 4 3 1 2 3 4 -1 【数据范围】 10%的数据满足N≤10; 40%的数据满足N≤2000,1≤M≤10000; 100%的数据满足2≤N≤100000,1≤M≤200000。所用道路长度大于0小于10000。 输入的路径一定是一条合法的从城市1到城市N的最短路径。 【编译命令】

对于c++语言: g++ -o road road.cpp –lm 对于c语言: gcc -o road road.c –lm 对于pascal语言: fpc road.pas

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6 6 4
1 2 1
2 3 1
3 4 1
4 6 1
2 5 2
5 4 3
1 2 3 4
-1
7
7
-1