配点: 100 点
問題文
在JOI王国,将举行鼓笛军团游行,以纪念JOIG的开业。
在JOI王国 有 N 个城市, 它们的编号最大为1 减去 N 。另外,还有一条单行道可供鼓笛队通过。 M 书籍可用,1 减去 M 。路 i (1 \leqq i \leqq M) 是一座城市 A_i 来自城市 这个想法是建立一条通往 B_i 的单向路,长度为 C_i 。
游行中,鼓队和笛队的移动必须满足以下条件。 从
- 都市 1 开始,沿着行进方向的几条道路反复行驶,在城市中移动。 前往 N 。
- 鼓队和笛队所走路径的总长度为 L 以下。
作为JOI王国的女王,你已经意识到,鼓笛军团的旅行路线可能没有满足这个条件的。因此,为了举办游行,在游行当天, 0 我决定反转多条道路的行驶方向。
为了避免混乱,我想尽可能减少反向行驶的道路数量。
JOI王国城市和道路信息和整数 给定 L ,通过反转部分道路的行进方向来判断是否可以举行游行,如果可以,则输出举行游行所需反转行进方向的道路数量的最小值。
制約
- 2 \leqq N \leqq 1\,000.
- 0 \leqq M \leqq 1\,000.
- 1 \leqq L \leqq 1\,000\,000\,000.
- 1 \leqq A_i \leqq N (1 \leqq i \leqq M).
- 1 \leqq B_i \leqq N (1 \leqq i \leqq M).
- A_i \neq B_i (1 \leqq i \leqq M).
- (A_i, B_i) \neq (A_j, B_j) (1 \leqq i < j \leqq M).
- 1 \leqq C_i \leqq 1\,000\,000 (1 \leqq i \leqq M).
- 所有输入值都是整数。
小課題
- (7 点) M = N - 1,(A_i, B_i) = (i, i + 1) 或 至少 (A_i, B_i) = (i + 1, i) (1 \leqq i \leqq M).
- (14 点) M 是偶数,A_{2i - 1} = B_{2i},A_{2i} = B_{2i - 1},C_{2i - 1} = C_{2i} (1 \leqq i \leqq \frac M 2).
- (18 点) N \leqq 15,M \leqq 15.
- (20 点) C_i = 1 (1\leqq i \leqq M),L = 1\,000\,000\,000.
- (20 点) C_i = 1 (1\leqq i \leqq M).
- (21 点)没有额外的限制。
评分注意事项
所有提交的内容都将通过评审系统进行评分。
当提交的源代码为与该子作业对应的所有评分输入数据返回正确的结果时,该源代码被认为对于该子作业是正确的。
每次提交的分数是所提交的源代码回答正确的子任务分数的总和。
该作业的分数是此作业所有提交的最高分。
您可以在“提交结果”选项卡上的“我的分数状态”中查看您当前的分数。
入力
输入是按以下格式从标准输入给出的。
N M L A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
出力
反转游行行进方向所需的最少道路数量写入标准输出。
输出为 1 行。然而,如果无论怎样改变行进方向都无法举行游行,
您可以通过反转-1 。
入力例 1
3 2 5 2 1 2 2 3 3
出力例 1
1
道 1 的方向来进行游行。
由于这是最小值,1 。 你只需要砍掉
此输入示例是一个小作业。 1,3,6 满足约束。
入力例 2
3 1 10 2 1 5
出力例 2
-1
无论怎样改变行进方向,游行都无法举行。-1 。
你只需要砍掉
此输入示例是一个小作业。 3,6 满足约束。
入力例 3
4 8 11 3 1 6 1 3 6 2 4 3 4 2 3 4 3 6 3 4 6 2 1 5 1 2 5
出力例 3
0
此输入示例是一个小作业。 2,3,6 满足约束。
入力例 4
5 6 1000000000 5 2 1 2 3 1 3 4 1 4 2 1 2 1 1 1 3 1
出力例 4
1
此输入示例是一个小作业。 3,4,5,6 满足约束。
入力例 5
6 15 777777 1 3 497295 4 1 422722 4 5 607164 2 3 135688 5 2 995652 5 1 670296 3 1 138860 4 6 736614 6 3 620085 2 1 796353 6 4 949756 4 2 750680 6 5 591550 5 3 229431 3 2 668173
出力例 5
2
此输入示例是一个小作业。 3,6 满足约束。