题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4511
题目大意：从1走到N，中间可以选择性经过某些点，比如1->N，或1->2->N，但是某些段路径（注意不是某些条）是被禁止的。问从1->N的最短距离。
解题思路：
AC自动机部分：
如果只是禁掉某些边，最短路算法加提前标记被禁的边即可。
但是本题是禁掉指定的路段，所以得边走边禁，需要一个在线算法。
所以使用AC自动机来压缩路段，如禁掉的路段是1->2->3，那么insert字符串（123) ，注意点只有1~50，所以0~50用ASCII 压缩成字符串即可。
这样就能够完成禁止路段的在线状态转移。
状态压缩DP部分：
其实就是手艹一个两点之间的最短路。dp[i][j]表示在地点i，当前字符是j的状态。
初始化：fill（&dp0][0],&dp[maxn-1][maxp-1],inf)，inf=1e12，double的inf很头疼，memset是不能用的。
边界：首先找下出发点在pool中的位置，s=root->next[0]，如果s被禁，那么就不用算了。否则dp[0][s]=0;
方程: dp[k][t]=min(dp[k][t],dp[i][j]+dist(i,k))
答案：min(dp[n-1][0..cnt])
解释下方程，其中for(0...i...n-1)，for(i+1...k....n) ，枚举两个点。
然后就是中间多出的AC自动机的状态压缩for(0....j....cnt)，负责打出所有的路径转移状态。
#include "cstdio"
#include "cstring"
#include "string"
#include "iostream"
#include "queue"
#include "math.h"
using namespace std;
#define maxn 55
#define maxp 10*100
#define inf 1e12
struct Point
{
double x,y;
}P[maxn];
struct Trie
{
Trie *next[maxn],*fail;
int cnt;
}pool[maxp],*root,*sz;
int pre,now;
double dp[][maxp];
Trie *newnode()
{
Trie *ret=sz++;
memset(ret->next,,sizeof(ret->next));
ret->fail=;
ret->cnt=;
return ret;
}
void init()
{
sz=pool;
root=newnode();
}
void Insert(string str)
{
Trie *pos=root;
for(int i=;i<str.size();i++)
{
int c=str[i];
if(!pos->next[c]) pos->next[c]=newnode();
pos=pos->next[c];
}
pos->cnt++;
}
void getfail()
{
queue<Trie *> Q;
for(int c=;c<maxn;c++)
{
if(root->next[c])
{
root->next[c]->fail=root;
Q.push(root->next[c]);
}
else root->next[c]=root;
}
while(!Q.empty())
{
Trie *x=Q.front();Q.pop();
for(int c=;c<maxn;c++)
{
if(x->next[c])
{
x->next[c]->fail=x->fail->next[c];
x->next[c]->cnt+=x->fail->next[c]->cnt;
Q.push(x->next[c]);
}
else x->next[c]=x->fail->next[c];
}
}
}
double dist(Point a,Point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
int main()
{
//freopen("in.txt","r",stdin);
int n,m,k,p;
while(scanf("%d%d",&n,&m)!=EOF&&n)
{
init();
for(int i=;i<n;i++) scanf("%lf%lf",&P[i].x,&P[i].y);
for(int i=;i<=m;i++)
{
scanf("%d",&k);
string tt;
for(int i=;i<=k;i++)
{
scanf("%d",&p);
tt.push_back(p-);
}
Insert(tt);
}
getfail();
int s=root->next[]-pool;
if(root->next[]->cnt) printf("Can not be reached!\n");
else
{
int cnt=sz-pool;
fill(&dp[][],&dp[][maxp-],inf);
dp[][s]=;
for(int i=; i<n-; i++)
{
for(int j=; j<cnt; j++)
{
Trie *pos=pool+j;
for(int k=i+; k<n; k++)
{
if(pos->next[k]->cnt) continue;
int t=pos->next[k]-pool;
dp[k][t]=min(dp[k][t],dp[i][j]+dist(P[i],P[k]));
}
}
}
double ans=inf;
for(int i=; i<cnt; i++) ans=min(ans,dp[n-][i]);
if(ans==inf) printf("Can not be reached!\n");
else printf("%.2lf\n",ans);
}
}
}
| 11848330 | 2014-10-11 14:48:53 | Accepted | 4511 | 109MS | 748K | 2865B | C++ | Physcal |