Graph Paths II

题目描述

考虑一个有向带权图，图中有 n 个节点和 m 条边。你的任务是计算从节点 1 到节点 n 恰好经过 k 条边的最短路径长度。

输入格式

第一行输入包含三个整数 n、m 和 k：节点数、边数以及路径的长度。节点编号为 1,2,$\dots$ ,n。 接下来有 m 行描述边。每行包含三个整数 a、b 和 c：存在一条从节点 a 到节点 b 权重为 c 的边。

输出格式

输出最短路径长度。如果不存在这样的路径，输出 -1。

3 4 8
1 2 5
2 3 4
3 1 1
3 2 2

27

提示

$1 \le n \le 100$ $1 \le m \le n(n-1)$ $1 \le k \le 10^9$ $1 \le a,b \le n$ $1 \le c \le 10^9$

标签: CSES1724|数学

来源

CSES1724|数学