7402. 图上路径 II (Graph Paths II)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 图上路径 II (Graph Paths II) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 考虑一个包含 $n$ 个节点和 $m$ 条有向带权边的有向图。您的任务是计算从节点 $1$ 到节点 $n$、且恰好包含 $k$ 条有向边的最少路径长度。 ## 输入格式 第一行包含三个整数 $n$、$m$ 和 $k$：分别代表节点的数量、边的数量以及路径中的边数。节点从 $1, 2, \dots, n$ 编号。 接下来有 $m$ 行描述边。每行包含三个整数 $a$、$b$ 和 $c$，表示存在一条从节点 $a$ 指向节点 $b$ 的有向边，其权值为 $c$。 ## 输出格式 输出最短路径的总权值和。如果不存在任何一条满足条件的路径，输出 `-1`。 ## 输入输出样例 ### 输入 #1 ```text 3 4 8 1 2 5 2 3 4 3 1 1 3 2 2 ``` ### 输出 #1 ```text 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$ ---