497. 有边数限制的最短路
时间限制：1000 MS 内存限制：64 MB
题目描述
# 有边数限制的最短路 ## 题目描述 给定一个有 $n$ 个点、$m$ 条边的有向图，点的编号为 $1$ 到 $n$。图中可能存在重边、自环、负权边和负权回路。 请你求出从 $1$ 号点到 $n$ 号点、最多经过 $k$ 条边的最短距离。若不存在满足边数限制的路径，则输出 `impossible`。 行走过程中可以重复经过同一个点或同一条边，每经过一条边都计入经过的边数。路径的距离为所经过各条边的权重之和。 允许经过零条边，其距离为 $0$；因此，当 $n=1$ 时，零条边的路径也是可行路径。 ## 输入格式 从文件 `limited.in` 读入数据。 第一行包含三个整数 $n,m,k$，分别表示点数、边数和最多允许经过的边数。 接下来 $m$ 行，每行包含三个整数 $x,y,z$，表示一条从点 $x$ 到点 $y$、权重为 $z$ 的有向边。 ## 输出格式 将结果输出到文件 `limited.out`。 输出一个整数，表示从 $1$ 号点到 $n$ 号点、最多经过 $k$ 条边的最短距离。 如果不存在满足边数限制的路径，则输出 `impossible`。 ## 数据范围 - $1 \le n,k \le 500$。 - $1 \le m \le 10000$。 - $1 \le x,y \le n$。 - $|z| \le 10000$。 - 图中允许存在重边、自环、负权边和负权回路。 时间限制：$1000$ 毫秒。 内存限制：$64$ MB。 ## 样例输入 ``` 3 3 1 1 2 1 2 3 1 1 3 3 ``` ## 样例输出 ``` 3 ``` ## 样例说明 最多只能经过 $1$ 条边，因此不能选择经过 $2$ 条边的路线 $1 \to 2 \to 3$。选择从 $1$ 号点直接到 $3$ 号点的边，最短距离为 $3$。