P3485 [POI 2009] BAJ-The Walk of Bytie-boy

[English Edition](/paste/9lmt83m9)

You are given a directed graph with $n$ vertices and $m$ edges. Each edge has a letter on it. You are also given an integer $d$ and a sequence $s_1, s_2, \dots, s_d$. For each $i$ ($1 \le i < d$), you need to find a shortest path from $s_i$ to $s_{i+1}$ such that the letters on the edges of this path, concatenated in order, form a palindrome. It is not guaranteed that each vertex appears at most once in $s$.

The first line contains two integers $n, m$. Then follow $m$ lines. Each line contains two integers $x_i, y_i$ and a letter $c_i$, indicating there is a directed edge from $x_i$ to $y_i$, and the letter on this edge is $c_i$. The next line contains an integer $d$. The last line contains $d$ integers, giving the sequence $s$.

Output $d-1$ lines. On the $i$-th line, output a path from $s_i$ to $s_{i+1}$ that satisfies the condition. If no such path exists, output `-1`; otherwise, output all letters on this path. If there are multiple valid paths, output any one of them.

For $100\%$ of the testdata, $2 \le n \le 400$, $1 \le m \le 6\times 10^4$, $1 \le x_i, y_i \le n$, $2 \le d \le 100$, $1 \le s_i \le n$. It is also guaranteed that there are no multiple edges or self-loops. Translated by ChatGPT 5