[POI2009] BAJ-The Walk of Bytie-boy
题目背景
[English Edition](/paste/9lmt83m9)
题目描述
给出一张 $n$ 个点 $m$ 条边的有向图,每条边上有一个字母,并给出一个整数 $d$ 和一个序列 $s_1, s_2, \dots, s_d$。
你需要对每一个 $i(1\le i<n)$ 求出一条从 $s_i$ 到 $s_{i+1}$ 的最短路径满足这条路径上的边上的字母连起来后是回文的。
不保证每个点最多只在 $s$ 中出现一次。
输入输出格式
输入格式
第一行两个整数 $n, m$。
之后 $m$ 行,每行两个整数 $x_i, y_i$ 与一个字母 $c_i$,表示有一条从 $x_i$ 到 $y_i$ 的边,这条边上的字母是 $c_i$。
之后一行一个整数 $d$。
之后一行 $d$ 个整数, 表示序列 $s$。
输出格式
输出共 $d-1$ 行,第 $i$ 行输出一条从 $s_i$ 到 $s_{i+1}$ 的满足条件的路径。
若不存在这样的路径,则输出 `-1`,否则输出这条路径上的所有字母。
如果有多条满足条件的路径,任意输出一条即可。
输入输出样例
输入样例 #1
6 7
1 2 a
1 3 x
1 4 b
2 6 l
3 5 y
4 5 z
6 5 a
3
1 5 3
输出样例 #1
3 ala
-1
说明
对于 $100\%$ 的数据,$2\le n\le 400$,$1\le m\le 6\times10^4$,$1\le x_i,y_i\le n$,$2\le d\le100$,$1\le s_i\le n$。
同时保证不会出现重边与自环。