K站中转内最便宜的航班

查看题解查看答案

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

请先登录再刷题，不会做的题目右上可以查看题解和答案~

输入输出格式

输入描述:

第一行输入四个整数 `n, src, dst, k`，分别表示城市数量、出发城市、目的地城市、最多中转次数。
第二行输入一个整数 `m`，表示航班的数量。
接下来 `m` 行，每行输入三个整数 `from_i, to_i, price_i`，表示一条航班的信息。
数据范围
- `1 ≤ n ≤ 100`
- `0 ≤ flights.length ≤ (n × (n - 1)) / 2`
- `0 ≤ from_i, to_i < n` 且 `from_i ≠ to_i`
- `1 ≤ price_i ≤ 10^4`
- `0 ≤ src, dst, k < n` 且 `src ≠ dst`
- 航班无重复，无自环

输出描述:

输出一个整数，表示从 `src` 到 `dst` 最多经过 `k` 次中转的最便宜价格。如果不存在这样的路线，输出 `-1`。

输入输出样例

输入样例#:

输出样例#:

复制

提示

样例解释：
从城市 0 到城市 3，最多经过 1 次中转的最佳路径为 `0 → 1 → 3`，费用为 100 + 600 = 700。
路径 `0 → 1 → 2 → 3` 虽然更便宜，但经过了 2 次中转，不符合 `k=1` 的限制。