#1709. 翻修道路

    ID: 1709 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1059来源:qoj.ac数据:公开样例最短路二分答案

翻修道路

翻修道路

题目描述

标题: 翻修道路 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

有 n 个城市,用 m 条单向道路连接。

第 i 条道路的长度是 ai,如果对其进行翻修,则长度变为 bi。

1 号城市是首都,有 k 个省会城市。

你希望首都到省会城市的最短距离的最大值尽可能小,但是你不能翻修太多道路。

对于所有 x∈[0,m] 求出翻修 x 条道路之后最小的最大值。

输入格式

第一行三个正整数 n,m,k。

第二行 k 个正整数,第 i 个 为 pi,表示所有省会城市。

接下来 m 行,第 i 行四个正整数 xi,yi,ai,bi 表示 xi 到 yi 有一条单向道路,翻修前后长度为 ai,bi。

输出格式

一行 m+1 个正整数,分别表示 x=0,1⋯m 时的答案。

样例输入

3 3 2
2 3
1 2 12 5
1 3 9 8
2 3 5 2

样例输出

12 9 7 7

样例解释

不翻修道路,1 到 2 的最短距离为 12,1 到 3 为 9,答案为 12。

翻修第一条道路,1 到 2 的最短距离变为 5,答案为 9。

翻修第一条和第三条道路,1 到 3 的最短距离变为 7,答案为 7。

数据范围

保证从 1 号点出发能到达所有点,k<n,pi∈[2,n] 且互不相同,xi,yi∈[1,n],1≤bi≤ai≤105。

不保证无重边自环。

n,m≤100,k≤8。

Subtask 1(15pts):n,m≤10。

Subtask 2(15pts):k=1。

Subtask 3(15pts):k=2。

Subtask 4(55pts):无特殊限制。

时间限制:1s。

空间限制:256MB。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 3 2
2 3
1 2 12 5
1 3 9 8
2 3 5 2
12 9 7 7