CSES1724 图的路径 II
#CS1724. 图的路径 II
图的路径 II
题目背景
翻译自 CSES-1724 题。
题目描述
考虑一个有向带权图，该图有 n 个节点和 m 条边。你的任务是计算从节点 1 到节点 n 的路径，且路径的长度恰好为 k 条边的最短路径长度。
输入格式
第一行输入三个整数 n，m，kn，m，kn，m，k：分别表示节点数、边数和路径的长度。节点编号为 1,2,…,n1,2,…,n1,2,…,n。
接下来的 m 行描述了每一条边，每行包含三个整数 a,b,ca,b,ca,b,c，表示从节点 a 到节点 b 有一条带权重 c 的有向边。
输出格式
输出从节点 1 到节点 n 的路径长度的最小值，路径的长度恰好为 k 条边。如果没有这样的路径，输出 −1−1−1。
样例
3 4 2
1 2 5
2 3 3
1 3 8
2 1 2
8
说明/提示