+题目大意：给定一张有向图，每个点有一个字符，多次求两点的最短回文路
据说这道题第一次做的人都会T？ 一开始的思路是这样的：令表示从点 然后广搜，果断T了= =
冗余的转移太多了…… 正解是这样的： 令的最短路 然后转移是这样的： 这样的复杂度是的，，就可以通过了
using namespace std;struct abcd{int to,c,next;}table[60600];int head[M],tot;int n,m;int f[M][M],g[M][M][26];pair<pair<int,int>,int> q[M*M*27];int r,h;vector<int> a[M][26];void Add(,int z){table[++tot].to=y;table[tot].c=z;table[tot].next=head[x];head[x]=tot;}void BFS(){vector<int>::iterator it;int i;while(r!=h){pair<pair<int,int>,int> temp=q[++h];int x=temp.first.first,y=temp.first.second;if(temp.second==-1){for(i=head[y];i;i=table[i].next)if(g[x][table[i].to][table[i].c]==-1)g[x][table[i].to][table[i].c]=f[x][y]+1,q[++r]=make_pair(make_pair(x,table[i].to),table[i].c);}else{for(it=a[x][temp.second].begin();it!=a[x][temp.second].end();it++)if(f[*it][y]==-1)f[*it][y]=g[x][y][temp.second]+1,q[++r]=make_pair(make_pair(*it,y),-1);}}}int main(){int i,x,y;char p[10];cin>>n>>m;memset(f,-1,sizeof f);memset(g,-1,sizeof g);for(i=1;i<=n;i++)f[i][i]=0,q[++r]=make_pair(make_pair(i,i),-1);for(i=1;i<=m;i++){scanf(“,&x,&y,p+1);Add(x,y,p[1]-‘a’);a[y][p[1]-‘a’].push_back(x);if(~f[x][y]) continue;f[x][y]=1,q[++r]=make_pair(make_pair(x,y),-1);}BFS();static int a[M],d;cin>>d;for(i=1;i<=d;i++)scanf(“%d”,&a[i]);for(i=2;i<=d;i++)printf(“%d\n”,f[a[i-1]][a[i]]);return 0;}
不必在乎目的地，在乎的是沿途的风景以及看风景的心情，让心灵去旅行！
