seuOJ162 - 最短路

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：10000 ms
• 空间限制：256 MiB
• 题目标签：春季, 校赛, 2019

题目描述

给出一张 $n$ 个点 $m$ 条边的无向图，每条边权为小于等于 $5$ 的正整数。给出 $k$ 个源点,求出每个源点到所有其他点的最短路。

为了简化输出，只要输出每个源点计算到其余点最短路的异或和。

输入格式

第一行一个整数 $T(T=1)$ 代表数据组数

每组数据第一行两个数 $n，m(1\leq n，m \leq 5*10^5)$，代表点数和边数。

下面 $m$ 行，每行三个数 $u，v，w(1\leq w \leq 5)$，表示点 $u$ 和 点 $v$ 之间有一条边权为 $w$ 的无向边。

然后一行一个整数 $k(1\leq k \leq 100)$。

下面一行 $k$ 个互不相同的数字，表示源点。

输出格式

$T$ 行每行 $k$ 个数字表示各个源点到其余所有点异或和。

样例

输入样例

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

输出样例

5 3

样例解释

$d(1,1) = 0, d(1,2) = 2, d(1,3) = 1, d(1,4) = 2, d(1,5) = 4, 2 xor 1 xor 2 xor 4 = 5$

$d(2,1) = 2, d(2,2) = 0, d(2,3) = 3, d(2,4) = 4, d(2,5) = 6, 2 xor 3 xor 4 xor 6 = 3$