QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
Statistics

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

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

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

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

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

输入格式

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

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

接下来 $m$ 行,第 $i$ 行四个正整数 $x_i,y_i,a_i,b_i$ 表示 $x_i$ 到 $y_i$ 有一条单向道路,翻修前后长度为 $a_i,b_i$。

输出格式

一行 $m+1$ 个正整数,分别表示 $x=0,1\cdots 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$,$p_i\in[2,n]$ 且互不相同,$x_i,y_i\in[1,n]$,$1\leq b_i\leq a_i \leq 10^5$。

不保证无重边自环。

$n,m\leq 100,k\leq 8$。

Subtask 1(15pts):$n,m\leq 10$。

Subtask 2(15pts):$k=1$。

Subtask 3(15pts):$k=2$。

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

时间限制:1s。

空间限制:256MB。