2842 「JOISC 2018 Day 4」野猪

译自 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$ 沿着 $1$ 号道路到结点 $2$，再沿 $2$ 号道路到结点 $3$，再沿 $3$ 号道路到结点 $1$。

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

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

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

对于所有数据，

• $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}$。