首页 > 代码库 > bzoj 1138: [POI2009]Baj 最短回文路 dp优化
bzoj 1138: [POI2009]Baj 最短回文路 dp优化
1138: [POI2009]Baj 最短回文路
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 161 Solved: 48
[Submit][Status]
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
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
-1
-1
一看题，这不是水dp么？设dp[i][j]为i到j的回文最短路长度，随便转移一下就行了，写出来才发现TLE的一塌糊涂。在一系列常数优化后直接在网上找题解了。。。
优化0：这算不上什么优化吧，由于每次只枚举特定起点特定颜色的边，用前向星比枚举边要快一些。
优化1：这个for是不是嵌套的太多了，冗余状态很多，用类似于spfa的方法优化一下。
优化2：直觉时卡时间的点应该有很多重边，先将边去重。
优化3：是不是觉得我们在dp[i][j]向下转移的过程中分别从起点终点枚举边很慢，我们外加一个数组dp2[i][j][k]表示从i到j经过一条边权为k的边和一个回文串的最短距离，每次转移变为了dp与dp2的相互更新，很不幸的一点是仔细想一想这样并不能优化时间复杂度级别，但是是一个很强劲的剪枝。
网上的题解称光优化3就能过，本人太弱，用了优化3还是T，就把优化1,2,3都加上了。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MAXN 450#define MAXM 61000#define INF 0x3f3f3f3fstruct edge{ int s,t,c;}e[MAXM],e2[MAXM];bool cmp_edge(edge e1,edge e2){ if (e1.s!=e2.s)return e1.s<e2.s; if (e1.c!=e2.c)return e1.c<e2.c; if (e1.t!=e2.t)return e1.t<e2.t; return false;}bool cmp_edge2(edge e1,edge e2){ if (e1.t!=e2.t)return e1.t<e2.t; if (e1.c!=e2.c)return e1.c<e2.c; if (e1.s!=e2.s)return e1.s<e2.s; return false;}bool operator ==(edge e1,edge e2){ return e1.s==e2.s && e1.t==e2.t && e1.c==e2.c;}int head[MAXN*26],head2[MAXN*26];int dp[MAXN][MAXN],dp2[MAXN][MAXN][26];inline bool deal(int &x,int y){ if (x>y) { x=y; return true; }else return false;}pair<int,int> q[10000000];bool vis[MAXN][MAXN];int main(){ freopen("input.txt","r",stdin); int i,j,k,x,y,z,n,m,a,b; scanf("%d%d\n",&n,&m); char ch; for (i=0;i<m;i++) { scanf("%d%d %c\n",&x,&y,&ch); e[i].s=x; e[i].t=y; e[i].c=ch-‘a‘; e2[i]=e[i]; } sort(e,e+m,cmp_edge); sort(e2,e2+m,cmp_edge2); x=m; m=unique(e,e+x)-e; m=unique(e2,e2+x)-e2; for (i=0;i<m;i++) { head[e[i].s*26+e[i].c]++; head2[e[i].t*26+e[i].c]++; } for (i=1;i<=n*26+26;i++) head[i]+=head[i-1],head2[i]+=head2[i-1]; for (i=n*26+25;i>=1;i--) head[i]=head[i-1],head2[i]=head2[i-1]; head[0]=0;head2[0]=0; e[m].s=e2[m].t=INF; memset(dp,INF,sizeof(dp)); memset(dp2,INF,sizeof(dp2)); for (i=1;i<=n;i++) dp[i][i]=0; for (i=0;i<m;i++) dp[e[i].s][e[i].t]=1; int h=-1,t=-1; for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (dp[i][j]!=INF) q[++t]=make_pair(i,j),vis[i][j]=true;; while (h<t) { x=q[++h].first; y=q[h].second; vis[x][y]=false; for (a=head2[x*26+k];e2[a].t==x;a++) { if (dp2[e2[a].s][y][e2[a].c]>dp[x][y]+1) { dp2[e2[a].s][y][e2[a].c]=dp[x][y]+1; if (!vis[e2[a].s][y]) { vis[e2[a].s][y]=true; q[++t]=make_pair(e2[a].s,y); } } } for (b=head[y*26+k];e[b].s==y;b++) { if (dp[x][e[b].t]>dp2[x][y][e[b].c]+1) { dp[x][e[b].t]=dp2[x][y][e[b].c]+1; if (!vis[x][e[b].t]) { vis[x][e[b].t]=true; q[++t]=make_pair(x,e[b].t); } } } } int q; scanf("%d",&q); scanf("%d",&x); for (i=1;i<q;i++) { scanf("%d",&y); if (dp[x][y]==INF) { printf("%d\n",-1); }else { printf("%d\n",dp[x][y]); } x=y; }}
bzoj 1138: [POI2009]Baj 最短回文路 dp优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。