hdu 4511 小明系列故事——女友的考验

小明系列故事——女友的考验

Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 822 Accepted Submission(s): 176

Problem Description

　　终于放寒假了，小明要和女朋友一起去看电影。这天，女朋友想给小明一个考验，在小明正准备出发的时候，女朋友告诉他，她在电影院等他，小明过来的路线必须满足给定的规则：
　　1、假设小明在的位置是1号点，女朋友在的位置是n号点，则他们之间有n-2个点可以走，小明每次走的时候只能走到比当前所在点编号大的位置；
　　2、小明来的时候不能按一定的顺序经过某些地方。比如，如果女朋友告诉小明不能经过1 -> 2 -> 3，那么就要求小明来的时候走过的路径不能包含有1 -> 2 -> 3这部分，但是1 -> 3 或者1 -> 2都是可以的，这样的限制路径可能有多条。
　　这让小明非常头痛，现在他把问题交给了你。
　　特别说明，如果1 2 3这三个点共线，但是小明是直接从1到3然后再从3继续，那么此种情况是不认为小明经过了2这个点的。
　　现在，小明即想走最短的路尽快见到女朋友，又不想打破女朋友的规定，你能帮助小明解决这个问题吗？

Input

　　输入包含多组样例，每组样例首先包含两个整数n和m，其中n代表有n个点，小明在1号点，女朋友在n号点，m代表小明的女朋友有m个要求；
　　接下来n行每行输入2个整数x 和y（x和y均在int范围），代表这n个点的位置（点的编号从1到n）；
　　再接着是m个要求，每个要求2行，首先一行是一个k，表示这个要求和k个点有关，然后是顺序给出的k个点编号，代表小明不能走k1 -> k2 -> k3 ……-> ki这个顺序的路径；
　　n 和 m等于0的时候输入结束。

　　[Technical Specification]
　　2 <= n <= 50
　　1 <= m <= 100
　　2 <= k <= 5

Output

　　对于每个样例，如果存在满足要求的最短路径，请输出这个最短路径，结果保留两位小数；否则，请输出”Can not be reached!” （引号不用输出）。

Sample Input

3 1 1 1 2 1 3 1 2 1 2 2 1 0 0 1 1 2 1 2 5 3 0 0 5 3 1 2 1 22 5 21 3 1 2 3 2 4 5 2 1 5 0 0

Sample Output

2.00 Can not be reached! 21.65

Source

2013腾讯编程马拉松初赛第二场（3月22日）

题意：中文，不解释

思路：对禁止的构造一个AC自动机，然后在跑spfa， dis[i][j] 表示，到i 点，在AC自动机位置为 J时

的最短路，转移注意禁止不能走就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<map>
#include<ctime>
#include<bitset>
#define LL long long
#define INF 4365893645897389.0
#define maxn 510
#define eps 1e-6
using namespace std;

struct trie
{
    int ch[maxn][60] , cnt ,end[maxn] ,root ,fail[maxn] ;
    int newnode()
    {
        memset(ch[cnt],-1,sizeof(ch[cnt])) ;
        end[cnt] = 0 ;fail[cnt++] = -1 ;
        return cnt-1 ;
    }
    void init()
    {
        cnt = 0 ;
        root = newnode();
    }
    void insert( int a[],int n )
    {
        int c , u = root ;
        for( int i = 0 ; i < n ;i++ )
        {
            c = a[i];
            if(ch[u][c] == -1 ) ch[u][c] = newnode() ;
            u = ch[u][c] ;
        }
        end[u] = 1 ;
    }
    queue<int>Q ;
    void getfail()
    {
        int i , u = root ;
        fail[root] = root ;
        for( i = 0 ; i < 50;i++ )
            if(ch[root][i] == -1 ) ch[root][i] = root ;
            else
            {
                fail[ch[root][i]] = root ;
                Q.push(ch[root][i]) ;
            }
        while(!Q.empty())
        {
            int pos = Q.front() ;Q.pop() ;
             if(end[fail[pos]])
                end[pos]=1;
            for( i = 0 ; i < 50 ;i++ )
                if(ch[pos][i] == -1 )
                  ch[pos][i] = ch[fail[pos]][i] ;
                else
                {
                    fail[ch[pos][i]] = ch[fail[pos]][i] ;
                    Q.push(ch[pos][i]) ;
                }
        }
    }
}AC;
double xx[100],yy[100] ,dis[60][510],len[100][100];
bool vi[60][510] ;
struct node
{
    int val,u;
    node(){}
    node(int x,int y)
    {
        u=x;
        val=y;
    }
};
double Dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) ;
}
void init(int n )
{
    for( int i = 0 ; i < n ;i++)
        for( int j = 0 ; j < n ;j++){
         len[i][j]=Dis(xx[i],yy[i],xx[j],yy[j]) ;
        }
}
void spfa(int s,int n )
{
    for( int i = 0 ; i < n ;i++)
        for( int j = 0 ; j < AC.cnt ;j++)
    {
        vi[i][j]=0;
        dis[i][j]=INF ;
    }
    if(AC.end[AC.ch[0][0]]) return ;
    dis[s][AC.ch[0][0]]=0;
    vi[s][AC.ch[0][0]]=1;
    node aa ;
    queue<node>q;
    q.push(node(s,AC.ch[0][0])) ;
    int i,v,e;
    while(!q.empty())
    {
        aa=q.front();q.pop();
        for(  i = 0 ; i < n ;i++)if(i>aa.u)
          {
              e=AC.ch[aa.val][i] ;
              if(AC.end[e]) continue ;
              if(dis[i][e] > dis[aa.u][aa.val]+len[aa.u][i])
              {
                  dis[i][e] = dis[aa.u][aa.val]+len[aa.u][i];
                  if(!vi[i][e])
                  {
                      vi[i][e]=1;
                      q.push(node(i,e)) ;
                  }
              }
          }
          vi[aa.u][aa.val]=false;
    }
}
int main()
{
    int n,m,i,j,k;
    int a[10] ;
    while(scanf("%d%d",&n,&m) != EOF)
    {
        if(n+m==0) break ;
        AC.init();
        for( i = 0 ; i < n ;i++)
        {
            scanf("%lf%lf",&xx[i],&yy[i]) ;
        }
        init(n) ;
        while(m--)
        {
            scanf("%d",&k) ;
            for( i = 0 ; i < k ;i++){
                scanf("%d",&a[i]) ;
                a[i]--;
            }
            AC.insert(a,k) ;
        }
        AC.getfail();
        spfa(0,n) ;
        double ans=INF ;
        for( i = 0;i < AC.cnt;i++)if(!AC.end[i])
        {
            ans=min(ans,dis[n-1][i]) ;
        }
        if(fabs(ans-INF) <= eps) puts("Can not be reached!");
        else printf("%.2lf
",ans) ;
    }
    return 0 ;

}
/*
2 1
0 0
1 1
1
1
*/

View Code