地铁

Luogu

IDLGP9618

Time5000ms

Memory128MB

DifficultyP4

著名工程学专家 625OutContradiction 设计了一张地铁交通网 $G$．$G$ 拥有 $n$ 个站点和 $m$ 条地铁线路．第 $i$ 条地铁线路 $P_i$ 会经过交通网上的若干站点，形如 $P_i=(u_1,u_2,u_3,...,u_{k_i})(k_i>0)$：每两个相邻站点 $u_j,u_{j+1}(j<k_i)$ 之间存在一段属于线路 $i$ 的从 $u_j$ 通向 $u_{j+1}$ 的单向地铁轨道．保证一条地铁线路不重复经过同一站点．但一个站点可能被若干条地铁线路经过．丹羽和艾莉欧准备从 $1$ 号站点前往 $n$ 号站点．然而他们的自行车坏掉了，只好准备乘坐地铁．现在他们需要决定出行的方案．一种出行方案具体是这样的：从 $1$ 号站点出发，选定一条经过 $1$ 号站点的地铁线路并开始乘坐地铁．沿当前地铁线路乘坐地铁的过程中，可以选择换乘其他任意一条经过当前站点的地铁线路．要求最终到达 $n$ 号站点．乘坐地铁过程中重复经过某一站点或某段地铁轨道是被允许的． **请注意：从 $1$ 号站点出发，第一次乘坐地铁不被算作换乘．** 艾莉欧提出了 $q$ 个问题．对于每个问题，艾莉欧会提供三个参数 $a, b, c$．在这次问题中，一个出行方案如果经过了 $x$ 段地铁轨道并进行了 $y$ 次换乘，那么它的疲惫值为 $ax+by$．您需要回答换乘次数不超过 $c$ 的出行方案中最小的疲惫值是多少． ## Input 第一行三个整数 $n, m, q$．接下来 $m$ 行，第 $i$ 行形如：$k_i,u_1,u_2,u_3,...,u_{k_i}$．表示一条地铁线路．接下来 $q$ 行，每行三个整数，表示 $a,b,c$． ## Output $q$ 行，对应每个问题的回答． [samples] ## Background > 两年级生孤单一人 > > 仰望上空陋市苍穹 > > 在宇宙这个约会室中 > > Maybe 我们只是刚好没能邂逅呢 ## Note ### 样例 #1 说明 $1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$ 是给出的第一条地铁线路，$1\rightarrow 3$，$2\rightarrow 4\rightarrow 5$ 是第二三条地铁线路．对于第一二组询问，均存在一种最优的出行方案为，在 $1$ 站点搭乘第二条地铁线路到达 $3$ 站点，在 $3$ 站点换乘第一条地铁线路到达终点；共经过 $3$ 段地铁轨道，并进行了 $1$ 次换乘，故第一二组询问的答案分别为 $3\times 1+1\times 1=4$，$3\times 3+1\times 0=9$．对于第三组询问，由于换乘的代价较大，最优的方案为顺着第一条地铁线路一直通向终点，途径 $4$ 段地铁轨道，答案为 $4$． ### 数据点约束对于所有数据满足： $1\le n \le 10^5$，$1\le m \le 10^4$，$1\le q \le 10^5$，$\sum k_i \le 3\times 10^5$． $0 \le a,b \le 10^6$，$0 \le c \le 20$． --- 对于 $10\%$ 的数据满足：$n \le 20$，$\sum k_i \le 40$，$q \le 30$． --- 对于另外 $20\%$ 的数据满足：$c=0$． --- 对于另外 $30\%$ 的数据满足：$q=1$． --- 题目中可能存在只经过一个地铁站的地铁线路．这种线路可以直接忽视．数据保证：对于任意一组询问，存在一条合法的路线可以到达终点．

Samples

Input #1

5 3 3
5 1 2 3 4 5
2 1 3
3 2 4 5
1 1 1
3 0 2
1 5 2

Output #1

4
9
4

Input #2

10 7 10
10 1 2 3 4 5 6 7 8 9 10
5 3 8 5 1 6
2 1 6
4 3 7 8 5
1 1
2 10 2
6 8 4 7 3 1 5
5 10 6
17 14 0
11 14 5
8 8 3
8 13 9
11 2 9
7 1 6
11 11 8
15 3 0
0 17 4

Output #2

Input #3

10 7 10
10 1 2 3 4 5 6 7 8 9 10
3 2 7 1
3 5 10 9
2 2 7
5 4 8 1 7 2
3 10 9 4
4 2 1 7 8
18 6 0
16 11 0
18 1 0
14 0 0
19 14 0
3 2 0
18 15 0
5 18 0
2 17 0
20 10 0

Output #3

API Response (JSON)

{
  "problem": {
    "name": "地铁",
    "description": {
      "content": "著名工程学专家 625OutContradiction 设计了一张地铁交通网 $G$．$G$ 拥有 $n$ 个站点和 $m$ 条地铁线路． 第 $i$ 条地铁线路 $P_i$ 会经过交通网上的若干站点，形如 $P_i=(u_1,u_2,u_3,...,u_{k_i})(k_i>0)$：每两个相邻站点 $u_j,u_{j+1}(j<k_i)$ 之间存在一段属于线路 $i$ 的从 $u_j$ 通向 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9618"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "著名工程学专家 625OutContradiction 设计了一张地铁交通网 $G$．$G$ 拥有 $n$ 个站点和 $m$ 条地铁线路．\n\n第 $i$ 条地铁线路 $P_i$ 会经过交通网上的若干站点，形如 $P_i=(u_1,u_2,u_3,...,u_{k_i})(k_i>0)$：每两个相邻站点 $u_j,u_{j+1}(j<k_i)$ 之间存在一段属于线路 $i$ 的从 $u_j$ 通向 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments