[POI2009]Baj 最短回文路

Time Limit:10000MS  Memory Limit:165536K
Total Submit:10 Accepted:1
Case Time Limit:3000MS

Description

N个点用M条有向边连接，每条边标有一个小写字母。

对于一个长度为D的顶点序列，回答每对相邻顶点Si到Si+1的最短回文路径。

如果没有，输出-1。

如果有，输出最短长度以及这个字符串。

Input

第一行正整数N和M ( 2 ≤ N ≤ 400 , 1 ≤ M ≤ 60,000 )
接下来M行描述边的起点，终点，字母。
接下来D表示询问序列长度 ( 2 ≤ D ≤ 100 )
再接下来D个1到N的整数

Output

对于D-1对相邻点，按要求输出一行。
如果没合法方案，输出-1。

如果有合法，输出最短长度以及这个字符串。空格隔开。

Sample Input

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

Sample Output

3 ala

-1

Source
首先一开始我的想法是对于
(a,b)如果a->c的边和b->c上的边的字母一样的话就可以转移。。然后状态就是(a,b)。。
这样状态数有N^2。。每次转移是度数的平方级别的。。显然会TLE囧。。。
然后换种思路：
这个更新说白了就是a走一步，b顺着同样的边走一步。
那么有两种可能的情况轮到a走，轮到b走。。
如果是a走，那么a随便走一步就行了。。
如果是b走，b要跟a走到那个一样。。
换言之状态就是 (a,b,now,pre)a和b意义如上，now表示是a走还是b走，pre表示上一个是哪个（a走到话就忽略）。。
那么实际上就一共有N*N*（26+1）种状态。。同时更新也变成O（M）级别了。。
A了。。代码如下。。。
http://www.ideone.com/EpXy9