额，，貌似网上的题解都说超时之类的。
然而我这个辣鸡在做的时候不知道在想什么，连超时的都不会。
超时的大概是这样的，f[x][y]表示x到y的最短回文路，然后更新的话就是 f[x][y]更新到 f[a][b] 当x->a,y->b且边的颜色是一样的。
然后yy了一下为什么会超时呢。。。。
然后想到了一个sb的情况。。两个菊花图连起来。。。这样的复杂度就呵呵呵了。。每次用f[x][y]更新的话都要枚举一个颜色，然后把另一边的颜色找出来，这样显然是要爆炸的。
为了避免这种sb情况，就引入了一个叫题解的神奇的东西。
题解多设了一个东西，g[x][y][col]表示x到y且除了和y相连的那条颜色为col的边之外是回文最短路的长度。
然后有了g，就可以在一遍更新过g，f在另一边直接拿来用了。神奇2333
1 #include<iostream> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #define inf 0x3f3f3f3f 7 using namespace std; 8 9 const int maxn=100005; 10 const int QWQ=505; 11 12 struct edge{ 13 int to,from,next; 14 }e[maxn<<1],E[maxn<<1]; 15 int head[QWQ],cnt,HEAD[QWQ],CNT; 16 void insert(int x, int y) 17 { 18 e[++cnt].next=head[x]; e[cnt].to=y; e[cnt].from=x; head[x]=cnt; 19 E[++CNT].next=HEAD[y]; E[CNT].to=x; E[CNT].from=y; HEAD[y]=CNT; 20 } 21 22 int l,r=1; 23 int n,m,map[QWQ][QWQ],f[QWQ][QWQ],g[QWQ][QWQ][30]; 24 struct node{ 25 int from,to,col; 26 }q[QWQ*QWQ*30]; 27 void bfs() 28 { 29 while (l<r) 30 { 31 node u=q[l++]; 32 int x=u.from,y=u.to; 33 if (!u.col) 34 { 35 for (int i=head[y];i;i=e[i].next) 36 { 37 if (f[x][y]+1<g[x][e[i].to][map[y][e[i].to]]) 38 { 39 g[x][e[i].to][map[y][e[i].to]]=f[x][y]+1; 40 q[r++]=(node){x,e[i].to,map[y][e[i].to]}; 41 } 42 } 43 } 44 else 45 { 46 for (int i=HEAD[x];i;i=E[i].next) 47 { 48 if (g[x][y][map[E[i].to][x]]+1<f[E[i].to][y]) 49 { 50 f[E[i].to][y]=g[x][y][map[E[i].to][x]]+1; 51 q[r++]=(node){E[i].to,y,0}; 52 } 53 } 54 } 55 } 56 } 57 int main() 58 { 59 scanf("%d%d",&n,&m); 60 memset(f,0x3f,sizeof(f)); memset(g,0x3f,sizeof(g)); 61 for (int i=1; i<=m; i++) 62 { 63 int x,y; char Orz[2]; 64 scanf("%d%d%s",&x,&y,Orz); 65 insert(x,y); 66 map[x][y]=Orz[0]-‘a‘+1; 67 f[x][y]=1; 68 q[r++]=(node){x,y,0}; 69 } 70 for (int i=1; i<=n; i++) f[i][i]=0,q[r++]=(node){i,i,0}; 71 bfs(); 72 int T; scanf("%d",&T); 73 int x,y; scanf("%d",&x); 74 for (int i=2; i<=T; i++) 75 { 76 scanf("%d",&y); 77 if (f[x][y]!=inf) cout<<f[x][y]<<endl; 78 else puts("-1"); 79 x=y; 80 } 81 return 0; 82 }
原文：http://www.cnblogs.com/ccd2333/p/6731465.html