分数: 625 点
问题陈述
给你一个有向图 N 顶点和 M 边缘。顶点已编号 1,2,\dots,N。边缘 j (j=1,2,\dots,M) 从顶点出发 u_j 到顶点 v_j。保证顶点 N 可从顶点到达 1.
最初,所有边都有权重 0。我们准确选择 K 出 M 边并将其权重更改为 1。求距顶点的最短距离的最大可能值 结果图中的 1 到顶点 N 。
约束
- 2 \leq N \leq 30
- 1 \leq K \leq M \leq 100
- 1 \leq u_j, v_j \leq N
- u_j \neq v_j
- 在给定的图中,顶点 N 可从顶点到达 1.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M K u_1 v_1 u_2 v_2 \vdots u_M v_M
输出
打印答案。
示例输入 1
3 3 2 1 2 2 3 1 3
示例输出 1
1
通过选择边 1,3,距顶点的最短距离 1 到顶点 3 变为 1。没有办法让距离最短 2 或更大,所以答案是 1.
示例输入 2
4 4 3 1 2 1 3 3 2 2 4
示例输出 2
2
通过选择边 1,2,4,距顶点的最短距离 1 到顶点 4 变为 2。没有办法让距离最短 3 或更大,所以答案是 2.
示例输入 3
2 2 1 1 2 1 2
示例输出 3
0
请注意,可能存在多边。