题意：
给出一个n个点m条边的有向图；
每条边上有一个字符，一个路径表示的字符串就是沿途走边组成字符串；
D次求两点之间最短回文路径；
n<=400，m<=60000，D<=100；
题解：
这道题范围不大，问的东西却比较奇怪；
一开始打算搜索，利用双向BFS，对字符串Hash来求解；
实际上速度还行，但是面对特殊数据菊花图等东西就卡不动了；
正解是DP，状态即为f[i][j]为i到j的最短回文路长度；
这个状态直接转移太暴力了；
所以我们需要一个辅助状态帮助转移；
设g[i][j][k]为从i到j，除最后一个字符以外是回文串且最后一个字符为k的最小路径长度；
这样转移复杂度就是科学的了，O(n*n*k+n*m)的样子？
具体实现是BFS推状态，，一层f一层g。。
代码：
#include<queue>#include<stdio.h>#include<string.h>#include<algorithm>#define N 440#define pr pair<int,int>#define par pair<pr,int>using namespace std;int next[N*N],to[N*N],ch[N*N],head[2][N],ce;char str[3];int f[N][N],g[N][N][26];queue<par>q;void add(int x,int y,bool t,int c){to[++ce]=y;ch[ce]=c;next[ce]=head[t][x];head[t][x]=ce;}int main(){int n,m,c,i,j,k,size,tx,ty,x,y;scanf("%d%d",&n,&m);memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));for(i=1;i<=n;i++){q.push(par(pr(i,i),-1));f[i][i]=0;}for(i=1;i<=m;i++){scanf("%d%d%s",&x,&y,str);add(x,y,0,str[0]-'a');f[x][y]=1,q.push(par(pr(x,y),-1));add(y,x,1,str[0]-'a');}while(!q.empty()){x=q.front().first.first,y=q.front().first.second;k=q.front().second;q.pop();if(k==-1){for(i=head[0][y];i;i=next[i]){if(g[x][to[i]][ch[i]]==0x3f3f3f3f)q.push(par(pr(x,to[i]),ch[i])),g[x][to[i]][ch[i]]=f[x][y]+1;}}else{for(i=head[1][x];i;i=next[i]){if(ch[i]==k){if(f[to[i]][y]==0x3f3f3f3f)q.push(par(pr(to[i],y),-1)),f[to[i]][y]=g[x][y][k]+1;}}}}scanf("%d%d",&m,&tx);for(c=1;c<m;c++){scanf("%d",&ty);printf("%d\n",f[tx][ty]>1e8?-1:f[tx][ty]);tx=ty;}return 0;}
只有一条路不能选择——那就是放弃的路;
