#2842. 「JOISC 2018 Day 4」野猪

内存限制:1024 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

译自 JOISC 2018 Day4 T3「イノシシ / Wild Boar

JOI 君是生活在 IOI 森林里的一头野猪。森林可视为一个包含 N 个结点, M 条带权无向边的连通图。结点的编号分别为 1\ldots N i 号边连接结点 A_i B_i ,权值为 C_i 。保证 (A_i,B_i)\neq(A_j,B_j) ,并且保证:对于任意两点互相可达。

开始时有一个长度为 L 的序列 X_1, X_2 \ldots X_L ,表示 JOI 君开始时在 X_1 ,它要依次访问结点 X_2 \ldots X_L 。序列中可能有重复结点,但保证序列中相邻两结点不同,即保证序列中 X_j\not=X_{j+1} 。注意,不要求从 X_j 直达 X_{j+1} ,JOI 君可以从 X_j 出发,经过其他结点作为中转,再到达 X_{j+1} 。但是,JOI 君不能沿原路返回前一个到达的结点。参见样例。

接下来有 T 次修改,每次修改会给出两个整数 P_k, Q_k ,表示将 X_{P_{\scriptsize k}} 修改为 Q_k 。每次修改后,JOI 君想知道:他能否找到满足要求的路径。如果能,请输出最短路的长度,反之则输出 -1

输入格式

第一行,四个整数 N,M,T,L
接下来 M 行,每行三个整数 A_i, B_i, C_i
接下来 L 行,每行一个整数 X_j
接下来 T 行,每行三个整数 P_k, Q_k

保证输入均合法。

输出格式

输出共 T 行,第 i 行有一个整数,表示查询的结果。

样例

样例输入 1

3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
3
3 1

样例输出 1

3

样例说明 1

从结点 1 沿着 1 号道路到结点 2 ,再沿 2 号道路到结点 3 ,再沿 3 号道路到结点 1

注意 JOI 君在结点 2 时不能沿着 1 号道路直接回到结点 1

样例输入 2

4 4 4 3
1 2 1
2 3 1
1 3 1
1 4 1
4
1
3
3 4
1 2
3 2
2 4

样例输出 2

5
2
3
-1

样例说明 2

在第一天, \{X_n\}=4,1,4 ,JOI 君可以沿着 4 号道路从结点 4 1 。然后 JOI 君再依次经过 1, 2, 3, 4 号道路回到结点 4

注意,尽管 JOI 君开始沿着 4 号道路从结点 4 1 ,后来又沿着 4 号道路从结点 1 4 ,但由于 JOI 君没有沿原路返回前一个到达的结点,因此这一方案合法。

样例输入 3

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

样例输出 3

38

数据范围与提示

对于所有数据,

  • 2\le N\le 2000 N-1\le M\le 2000 1\le T\le 10^5 2\le L\le 10^5
  • 1\le A_i<B_i\le N ,保证图是连通图;
  • 1\le C_i\le 10^9
  • X_j\neq X_{j+1}
子任务 分值 附加限制
1 12 N,M,L,C_i\le 10; T=1
2 35 N,M\le 500; T=1
3 15 T=1
4 38