题目详情题解（0）讨论（0）提交记录（0）

AT_abc369_e.[ABC369E] Sightseeing Tour

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

题目大意

给你一张 NN 个点，MM 条边的无向图（可能有重边）。第 ii 条边的端点是 UiU_i 和 ViV_i，长度是 TiT_i。

给定 QQ 个询问，每个询问会给出 KK 条边。对于每个询问，请求出经过这 KK 条边（一定经过这 KK 条边，但是也可以经过其他的边）的 11 到 NN 的最短路的长度。

输入格式

第一行是两个正整数 N,MN,M。

接下来 MM 行，第 i+1i+1 行输入编号为 ii 的边：Ui,Vi,TiU_i,V_i,T_i。

接下来一行，输入询问的个数 QQ。

接下来 Q×2Q \times 2 行，每两行描述一个询问。
每个询问的第一行是给出的边的数量 KiK_i，第二行有 KiK_i 个数：Bi,1 Bi,2⋯Bi,KiB_{i,1}\space B_{i,2}\cdots B_{i,K_i}，表示给出的边的编号。

输出格式

对于每个询问，输出一行一个整数表示你的答案。

输入输出样例

  • 输入#1

    3 5
1 2 10
1 3 20
1 3 30
2 3 15
2 3 25
2
1
1
2
3 5

    输出#1

    25
70

  • 输入#2

    6 6
1 5 1
2 5 1
2 4 1
3 4 1
3 6 1
1 6 1
2
5
1 2 3 4 5
1
5

    输出#2

    5
3

  • 输入#3

    5 5
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
1 5 1000000000
1
1
3

    输出#3

    4000000000

说明/提示

  • 2≤N≤4002 \leq N \leq 400
  • N−1≤M≤2×105N-1 \leq M \leq 2 \times 10^5
  • 1≤Ui<Vi≤N1 \leq U_i < V_i \leq N
  • 1≤Ti≤1091 \leq T_i \leq 10^9
  • 1≤Q≤30001 \leq Q \leq 3000
  • 1≤Ki≤51 \leq K_i \leq 5
  • 1≤Bi,1<Bi,2<⋯<Bi,Ki≤M1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M
  • 所有输入值都是整数。
  • 这个图是连通图。

translate by @wujiawei36

输入解题思路，AI测评打分。不知道怎么写?

首页