- 题目提供者 洛谷
- 评测方式 云端评测
- 标签 动态规划,动规,dp 广度优先搜索,BFS POI 2009 Special Judge 高性能
- 难度 尚无评定
- 时空限制 1000ms-10000ms / 256MB
Bytie-boy is one of the youngest habitats of Byteburg. Let the fact that he has only just learnt to read and write speak for his age. He is, however, old enough to go school by himself. Every morning he leaves home and comes by all his friends; the whole group goes to school together only when everyone is joined.
One day the teacher asked Bytie to prepare a list of the streets Bytie walks on his way to school, and to read it loud during the very next class.
It soon turned out that the list is very long; so long in fact that it could take a vast amount of paper. Therefore it was decided that Bytie-boy would write down only the first letter from the name of every street he walks.
The streets Byteburg are, with no exception, one-way, and each one connects two different crossings.
While reading the list of letters, Bytie makes a pause only at the spots at which he picked up a friend. Thus each part of his walk can be treated as a single word. Reading is still somewhat difficult for the boy: sometimes he reads from right to left instead of left-to-right. So he may read the word milk as milk, but also as klim. As Bytie's parents are aware of his problems, they decided to aid him by finding a route whose every fragment remains the same whether it is read left-to-right or right-to-left. For obvious reasons, the parents would also like to keep each fragment (word) as short as possible.
They ask you for help. Write a programme that reads the city's description from the standard input, determines a route from Bytie's house to the school such that each of its fragments is as short as possible and its description reads the same left-to-right and right-to-left, prints out the description (with fragments suitably separated) to the standard output.
The first line of the standard input contains two integer, and , separated by a single space (, ).
These denote, respectively, the number of crossings in Byteburg and the number of streets connecting them.
The streets descriptions follow in the next lines.
Three numbers are given in the -th line: , , (, , ); these deno…输出格式：
The output should consist of lines.
There should be a number ans a sequence of characters in the -th line, separated by a single space.
The number denotes the minimum length of the route complying with the task's conditions that connects the crossings and , while is the sequence of first letters of the streets in this rout.
If there is no route between some two crossings that satisfies aforementioned conditions, should be output.
It is possible there are severa…