最短路

时间限制：3s
空间限制：1024MB

题目描述

给定一张 \(n\) 个点 \(m\) 条边的带权无向图，以及这张图的一个划分方案, 使用了专业工具。每个点都属于某一个块。

现在给出 \(100\) 次询问。对于每次询问 \((s, t)\)，请你求出从点 \(s\) 到点 \(t\) 的最短路长度。

划分方案作为输入的一部分给出，你可以使用它辅助求解，也可以完全忽略它。

输入格式

第一行包含四个整数 \(n,m,k,q\) 分别代表点数，边数，块数和询问数

接下来 \(m\) 行，每行三个整数 \(u,v,w\) 代表 \(u\) 和 \(v\) 之间有一条边权为 \(w\) 的边。

接下来给出 \(n\) 个整数 \(c_1,c_2,...,c_n\) 代表每个点所在块的编号。

接下来 \(q\) 行，每行两个整数 \(s,t\) 表示一次最短路询问。

输出格式

输出 \(q\) 行。

第 \(i\) 行输出第 \(i\) 个询问的答案。

如果两点之间不存在路径，输出 \(-1\)。

样例输入

6 7 2 4
1 2 2
2 3 5
3 4 1
4 5 3
5 6 4
1 6 20
2 5 6
0 0 1 1 1 0
1 4
1 6
2 5
3 6

样例输出

8
12
6
8

数据范围与说明

对于 100% 的测试数据：

\(n = 264346\)
\(m = 365050\)
\(K = 200\)
\(q = 100\)
\(1 <= u, v, s, t <= n\)
\(u != v\)
\(0 <= c_i < K\)
\(1 <= w <= 100000\)