4799. D. 第 k 短路
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 > 有向无环图指的是一个无回路的有向图 有一个 nn 个节点和 mm 条边的有向无环图。 现在喵喵想从 11 号点走到 nn 号点，很明显行走的方案有很多。 喵喵想问你这些行走方案中第 kk 短的路径长度是多少。 ## 输入格式 第一行输入三个整数 n,m,kn,m,k。 接下来 mm 行，每行输入两个整数 ui,viui,vi 表示从 uiui 到 vivi 有一条有向边。 ## 输出格式 输出第 kk 短路的路径长度，如果不存在输出 -1-1。 ##### 样例 ## 输入 ```in1 5 6 2 1 2 2 3 1 3 3 5 3 4 4 5 ``` ## 输出 ```out1 3 ``` ```in2 5 6 4 1 2 2 3 1 3 3 5 3 4 4 5 ``` ```out2 4 ``` ## 提示 ## 数据范围 对于所有测试数据有：2\len\le1032\len\le103, m\len\times(n-1)2,k\le109m\le2n\times(n-1),k\le109 | 测试点 | n\len\le | 特殊性质 | | --- | --- | --- | | 1∼21∼2 | 1010 | 无 | | 3∼43∼4 | 103103 | AA | | 55 | 103103 | BB | | 6∼106∼10 | 103103 | 无 | - 特殊性质 AA：k\le2k\le2 - 特殊性质 BB: 对于所有的边，满足 ui\leviui\levi，且对于所有的 x\in[1,n]x\in[1,n] 满足最长路和最短路长度相同 ## 说明 四种路径： 1. [1 - 2 - 3 - 4 - 5][1 - 2 - 3 - 4 - 5] 2. [1 - 3 - 4 - 5][1 - 3 - 4 - 5] 3. [1 - 2 - 3 - 5][1 - 2 - 3 - 5] 4. [1 - 3 - 5][1 - 3 - 5]