题意：让你求从1走到n的最短路，但是有些路径是不能走的，且走到每次走只能走比当前点大的点
解题思路：看到有些路径是不能走的，想到用AC自动机标记结点，跑出一个trie图来，在trie图上进行路径更新，dist【i】【j】表示在trie状态结点j的时候，到正常结点i的花费
代码：
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; const double inf=1e18; double dist[600][600]; int trie[6000][60]; int fail[600],tot; int t[10]; double x[150],y[150]; bool visit[600]; int n,m,k; void build_trie(int *arr,int len) { int root=0; for(int i=1;i<=k;i++) { int id=arr[i]; if(!trie[root][id]) trie[root][id]=++tot; root=trie[root][id]; } visit[root]=1; } void build_fail() { queue<int>q; for(int i=1;i<=n;i++) { if(trie[0][i]!=0) q.push(trie[0][i]); } while(!q.empty()) { int now=q.front();q.pop(); if(visit[fail[now]]==1) visit[now]=1; for(int i=1;i<=n;i++) { if(!trie[now][i]) { trie[now][i]=trie[fail[now]][i]; continue; } fail[trie[now][i]]=trie[fail[now]][i]; q.push(trie[now][i]); } } } void init() { tot=0; memset(visit,0,sizeof(visit)); memset(trie,0,sizeof(trie)); memset(fail,0,sizeof( fail)); } double dis(int a,int b) { double tmp=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])); return tmp; } void solve() { for(int i=1;i<=n;i++) for(int j=0;j<=tot;j++) dist[i][j]=inf; dist[1][trie[0][1]]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=tot;j++) { if(dist[i][j]<inf) { for(int k = i + 1; k <= n; k++) if(!visit[trie[j][k]]) { dist[k][trie[j][k]] = min(dist[k][trie[j][k]],dist[i][j]+dis(i,k)); } } } } double ans=inf; for(int i=0;i<=tot;i++) { ans=min(ans,dist[n][i]); } if(ans>=inf) cout<<"Can not be reached! "; else printf("%.2f ",ans); } int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0)return 0; init(); for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]); while(m--) { scanf("%d",&k); for(int i=1;i<=k;i++) { scanf("%d",&t[i]); } build_trie(t,k); } build_fail(); solve(); } }