#P11795. [JOI 2016 Final] 铁路票价 / Train Fare
[JOI 2016 Final] 铁路票价 / Train Fare
题目描述
JOI 国有 个城市,编号分别为 。城市 是 JOI 国的首都。
JOI 国只有一家铁路公司,该公司在 JOI 国内共有 条线路,这些线路编号分别为 。每条线路都可看作一条无向边,线路 连接城市 和 。假设你只能依靠铁路运输在不同的城市间来往。当然你可以换乘不同线路。保证任意两个城市间都有线路直接或间接连接。
目前,任何线路的票价是 1 日元。该公司经营不善,只好计划在未来 年里提高票价。从提价计划开始的第 年初 ,线路 的票价会从 1 日元升至 2 日元。 之后该线路票价一直保持在 2 日元,不会再提高。
该公司每年都会对每个城市的居民进行满意度调查。在提价计划开始之前,任何一个城市的居民都对该公司感到满意。但由于价格上涨,可能有一些城市的居民会不满。每年的满意度调查都在当年提价后进行。因此,计划开始后第 年 进行满意度调查时,线路 已经提价,剩余线路的票价暂无变化。
在第 年的满意度调查中,如果当年城市 到首都的最低总票价 大于 提价计划开始前城市 到首都的最低总票价,城市 的居民会对铁路公司感到不满。
使用多条路线的费用是每条路线的运费的总和。首都人民不会对该公司感到不满。提价后最低费用的路线可能与计划开始前最低费用的路线有所不同。
输入格式
第一行有三个整数 ,用空格分隔。
在接下来的 行中,第 行有两个整数 ,用空格分隔。
在接下来的 行中,第 行有一个整数 。
输出格式
输出共 行,第 行有一个整数,表示在计划开始后第 年的满意度调查中,有多少个城市的居民对铁路公司不满。
5 6 5
1 2
1 3
4 2
3 2
2 5
5 3
5
2
4
1
3
0
2
2
4
4
4 6 6
1 2
1 3
1 4
2 3
2 4
3 4
1
4
2
5
3
6
1
1
2
2
3
3
2 1 1
1 2
1
1
提示
【数据范围与约定】
对于全部数据,均满足:
-
。
-
$1 \le U_i \le N (1\le i\le M),1\le V_i\le N (1\le i\le M),U_i \neq V_i(1\le i\le M)$。
-
$1\le R_j\le M (1\le j\le Q),R_j\neq R_k(1\le j<k\le Q)$。
-
对于任意两个城市,直接连接它们的线路不超过一条。
-
对于任何一个城市,都可以从该城市前往另一个城市。
1.Subtask ( pts):。
2.Subtask ( pts):。
3.Subtask ( pts):答案中出现的整数少于 种。
4.Subtask ( pts):无特殊限制。