[AdditionalFile5100.zip](file://AdditionalFile5100.zip?type=additional_file)

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

题目背景

English Edition

题目描述

给出一张 $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

输入 #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$。

同时保证不会出现重边与自环。

#5100. 「POI2009 R2」拜图斯的散步 The Walk of Bytie-boy

标签: 传统 | 时间限制: 7000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XVI OI Olimpiada Informatyczna – II etap Przechadzka Bajtusia

Bajtuś 是拜托城最年幼的居民之一，刚刚学会读写，但已能独自上学。每天清晨，他从家出发，依次接上所有小伙伴，最后一起前往学校。

某天，Bajtuś 的老师要求他记录从家到学校的街道列表，并在下次课上朗读。然而，完整记录可能耗费大量纸张。于是，约定只记录每条街道名称的首字母。拜托城的每条街道为单向，连接两个不同交叉口。

Bajtuś 朗读时，仅在接小伙伴的地点停顿。因此，他从家到学校的路径可分为若干段，每段的街道首字母序列视为一个单词。Bajtuś 阅读尚不熟练，常从右向左读，例如 mleko 可能读成 okelm。他的父母深知这一问题，决定帮他规划一条特殊路径：每段路径的首字母序列无论正读反读都相同，且每段路径尽量短。他们向你求助。

编写程序，完成以下任务：

• 从标准输入读取城市描述。
• 规划从家到学校的路径，使每段路径最短，且其首字母序列为回文。
• 在标准输出中输出每段路径的长度及其首字母序列。

输入格式

第一行包含两个整数 $n, m$ $(2 \leq n \leq 400, 1 \leq m \leq 60000)$，分别表示拜托城的交叉口数和街道数。

接下来的 $m$ 行描述街道，第 $i+1$ 行包含三个值 $x_i, y_i, c_i$ $(1 \leq x_i, y_i \leq n, x_i \neq y_i)$，表示街道从交叉口 $x_i$ 到 $y_i$，首字母为小写英文字母 $c_i$。任意两交叉口间同方向最多有一条街道。

下一行包含一个整数 $d$ $(2 \leq d \leq 100)$，表示 Bajtuś 路径上的交叉口数。

最后一行包含 $d$ 个整数 $s_i$ $(1 \leq s_i \leq n)$，表示 Bajtuś 从家（交叉口 $s_1$）出发，依次经过小伙伴所在地（交叉口 $s_2, s_3, \ldots, s_{d-1}$），到达学校（交叉口 $s_d$）。相邻交叉口编号不同，但列表中可能有重复交叉口。若两相邻交叉口间无符合要求的路径，Bajtuś 将抄近路，不记录任何内容。

输出格式

输出 $d-1$ 行，第 $i$ 行包含一个整数 $r_i$ 和一个字符串 $w_i$，用单空格分隔。$r_i$ 表示从交叉口 $s_i$ 到 $s_{i+1}$ 的最短路径长度，满足题目要求；$w_i$ 为该路径上街道首字母序列。若无符合要求的路径，输出 $-1$。若有多条符合要求的 $w_i$，输出任意一条。

样例

输入

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

输出

3 ala
-1