[COCI 2021/2022 #4] Autobus

Luogu

IDLGP8312

Time1000ms

Memory512MB

DifficultyP3

2021COCI（克罗地亚）

在一个国家里有 $n$ 座城市。这些城市由 $m$ 条公交线路连接，其中第 $i$ 条线路从城市 $a_i$ 出发，到 $b_i$ 停止，路程中耗时 $t_i$ 分钟。 Ema 喜欢旅行，但她并不喜欢在公交线路之间换乘。在旅行过程中，她希望**最多**只需坐 $k$ 个不同的公交线路。 Ema 想知道，从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间是多少（最多坐 $k$ 个不同的公交线路）。 ## Input 第一行包含两个整数 $n,m$，分别表示城市的数量和公交车线路的数量。接下来 $m$ 行，第 $i+1$ 包含三个整数 $a_i,b_i,t_i$，分别表示第 $i$ 条公交车线路的起点、终点和从起点到终点所需的时间。接下来一行包含两个整数 $k,q$，最大坐的不同公交线路的个数和问题题的个数。接下来 $q$ 行，第 $m+j+3$ 行包含两个整数 $c_j,d_j$，表示询问从城市 $c_j$ 到城市 $d_j$ 的最短旅行时间。 ## Output 输出包含 $q$ 行，第 $i$ 行包含一个整数，表示从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间。 [samples] ## Note **【样例解释】** ![](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。**

Samples

Input #1

Output #1

10
-1
0

Input #2

Output #2

6
4
0

Input #3

Output #3

3
4
0

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2021/2022 #4] Autobus",
    "description": {
      "content": "在一个国家里有 $n$ 座城市。这些城市由 $m$ 条公交线路连接，其中第 $i$ 条线路从城市 $a_i$ 出发，到 $b_i$ 停止，路程中耗时 $t_i$ 分钟。 Ema 喜欢旅行，但她并不喜欢在公交线路之间换乘。在旅行过程中，她希望**最多**只需坐 $k$ 个不同的公交线路。 Ema 想知道，从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间是多少（最多坐 $k$ 个不同的公交线",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8312"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在一个国家里有 $n$ 座城市。这些城市由 $m$ 条公交线路连接，其中第 $i$ 条线路从城市 $a_i$ 出发，到 $b_i$ 停止，路程中耗时 $t_i$ 分钟。\n\nEma 喜欢旅行，但她并不喜欢在公交线路之间换乘。在旅行过程中，她希望**最多**只需坐 $k$ 个不同的公交线路。\n\nEma 想知道，从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间是多少（最多坐 $k$ 个不同的公交线...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments