P8312 [COCI 2021/2022 #4] Autobus

题目描述

在一个国家里有 $n$ 座城市。这些城市由 $m$ 条公交线路连接,其中第 $i$ 条线路从城市 $a_i$ 出发,到 $b_i$ 停止,路程中耗时 $t_i$ 分钟。 Ema 喜欢旅行,但她并不喜欢在公交线路之间换乘。在旅行过程中,她希望**最多**只需坐 $k$ 个不同的公交线路。 Ema 想知道,从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间是多少(最多坐 $k$ 个不同的公交线路)。

输入格式

输出格式

说明/提示

**【样例解释】** ![](https://cdn.luogu.com.cn/upload/image_hosting/kxv8k07a.png) 每个样例中的答案都已经标记在图中。 **【数据规模与约定】** **本题采用子任务捆绑测试。** - Subtask 1(15 pts):$k ≤ n ≤ 7$。 - Subtask 2(15 pts):$k ≤ 3$。 - Subtask 3(25 pts):$k ≤ n$。 - Subtask 4(15 pts):没有额外限制。 对于 $100\%$ 的数据,$2\le n \le 70,1\le m,t_i\le 10^6,1\le a_i,b_i,c_j,d_j\le n,1\le k\le10^9,1\le q \le n^2$。 **【提示与说明】** **本题分值按 COCI 原题设置,满分 $70$。** **题目译自 [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T2 Autobus。**