解题思路
普通的最短路状态如果直接记录“当前所在房间 + 当前钥匙颜色”，状态会非常大。关键观察是：
对于同一种颜色 c 的传送门，它们会把若干房间划分成若干个连通块。
如果当前在房间 u，并且购买了颜色 c 的钥匙，那么 hy 可以在颜色 c 所在的同色连通块中任意移动，之后到达这个连通块内的任意房间，且不再产生额外费用。
P4592.第3题-迷宫
题目内容
“光之女皇”是泰拉瑞亚困难模式的神圣之地Boss，对战可选，但并非游戏主线所需。尽管初期可通过召唤物“七彩草岭”通常认为应在击败石巨人后再发起挑战。hy想挑战光之女皇，却被邪恶的zzh和lyf将”七彩草蛉“藏入迷宫以阻挠。
迷宫由 n 个房间与 q 条传送门构成，第 i 条传送门双向连接房间 xi 与房间 yi，颜色为 ci ; 打开颜色 ci 的传送门需支付费用 ci 购买对应钥匙，每次仅能携带一把钥匙(钥匙可无限次使用、使用后不消失)，也可购买新钥匙替换旧钥匙。
仅当持有某颜色的钥匙时，才能使用该颜色的传送门，你可以在任何房间随时支付费用 ci 购买一把颜色为 ci 的新钥匙，并替换掉当前持有的钥匙。
zzh 和 lyf 在房间中一共放置了 k 只“七彩草蛉”，作为幸运房间——如果某个房间有“七彩草蛉”，可立即免费(费用 0 )制作一把任意颜色钥匙；但在其他房间制作钥匙仍需支付相应颜色费用。
hy 从房间 1 出发，目标是到达(或起始于)至少一个草蛉房间以获得幸运并最终抵达房间 n ；若无法完成任务，则失败。请计算 hy 完成任务的最小总花费；若无法完成，则直接输出 −1 。
【名词解释】
连通块：同一颜色传送门在迷宫中形成的可互达房间集合。
输入描述
第一行输入三个整数 n,k,q(1≤n,q≤2×105;1≤k≤n) 分别表示房间数，草蛉数量和传送数量。
第二行输入 k 个整数 p1,p2,...,pk(1≤pi≤n) 表示第 i 只草岭所在的房间编号，可能有多只草岭位于同个房间。
此后 q 行，第 i 行输入三个整数 xi,yi,ci(1≤xi,yi≤n;1≤ci≤2×105) 表示第 i 条传送门双向连接房间 xi 出与房间 yi ，颜色为 ci 。
输出描述
输出一个整数，表示完成任务的最小总花费；若无法完成，则输出 −1 。
样例1
输入
3 1 3
2
1 2 1
2 3 1
3 1 2
输出
说明
样例2
输入
输出
说明
在这个样例中，花费 1 购买颜色 1 的钥匙，依次穿越 1−>3−>2−>5−>6。因为 6 号房间有“七彩草蛉”，免费制作颜色 5 的钥匙；随后，依次穿越 6−>7−>8 。最终，总花费 1 。
样例3
输入
8 1 11
2
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5
输出
6
说明
在这个样例中，依次穿越 1−>3−>2−>5−>6−>7−>8，总花费 1+5=6 。
