A5410. Shortest Path
编程题
普及/提高-
知识点
题目描述
在 Ancient Berland 有 $n$ 座城市和 $m$ 条长度均为 $1$ 的双向道路。城市从 $1$ 到 $n$ 编号。根据一个古老的迷信说法，如果一个旅行者连续访问了 $a_i,b_i,c_i$ 三座城市而不去拜访其他城市，来自东方的神秘力量将使他遭受巨大的灾害。一共有 $k$ 组这样的城市，每个三元组都是有序的，这意味着你可以按照 $a_i,c_i,b_i$ 这样的方式来访问一组城市而不遭受灾害。Vasya 想要从城市 $1$ 走到城市 $n$ 并且不受到诅咒。请告诉他最短路的长度，并输出一条路线。
输入格式
第 $1$ 行 $3$ 个整数 $n,m,k(2\le n\le 3000,1\le m\le2\times10^4,0\le k\le10^5)$，分别表示城市数、路径数以及三元组数量。
接下来 $m$ 行，每行 $2$ 个整数 $x_i,y_i(1\le x_i,y_i\le n)$，表示存在一条连接 $x_i$ 与 $y_i$ 的路，保证无重边和自环。
接下来 $k$ 行，每行 $3$ 个整数 $a_i,b_i,c_i(1\le a_i,b_i,c_i\le n)$，表示一个诅咒三元组。不存在两个相同的三元组，且三个城市两两不同。
接下来 $m$ 行，每行 $2$ 个整数 $x_i,y_i(1\le x_i,y_i\le n)$，表示存在一条连接 $x_i$ 与 $y_i$ 的路，保证无重边和自环。
接下来 $k$ 行，每行 $3$ 个整数 $a_i,b_i,c_i(1\le a_i,b_i,c_i\le n)$，表示一个诅咒三元组。不存在两个相同的三元组，且三个城市两两不同。
输出格式
可能从 $1$ 号城市出发无法到达 $n$ 号城市，这种情况下输出
否则第 $1$ 行输出最短路长度 $d$，第 $2$ 行输出 $d+1$ 个数，表示一条可行最短路径。路径必须从 $1$ 开始，在 $n$ 结束。
-1 。否则第 $1$ 行输出最短路长度 $d$，第 $2$ 行输出 $d+1$ 个数，表示一条可行最短路径。路径必须从 $1$ 开始，在 $n$ 结束。
输入输出样例
输入 #1
4 4 1 1 2 2 3 3 4 1 3 1 4 3
输出 #1
2 1 3 4
输入 #2
3 1 0 1 2
输出 #2
-1
输入 #3
4 4 2 1 2 2 3 3 4 1 3 1 2 3 1 3 4
输出 #3
4 1 3 2 3 4