首页 > ACM题库 > HDU-杭电 > HDU 4511-小明系列故事――女友的考验-动态规划-[解题报告]HOJ
2015
07-17

HDU 4511-小明系列故事――女友的考验-动态规划-[解题报告]HOJ

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

问题描述 :

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

输入:

  输入包含多组样例,每组样例首先包含两个整数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

输出:

  输入包含多组样例,每组样例首先包含两个整数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

样例输入:

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

样例输出:

2.00
Can not be reached!
21.65

题目链接:Click here~~

题意:

中文题。抽象问题:给一个有向无环图,问从 1 号点到 n 号点的最短路径,路径中不能包含某些子串。

解题思路:

其实也不算难,如果能从“不能包含某些子串”联想到AC自动机,这题基本就解决了。

令 dp[i][j] 表示到达 i 号点且位于自动机中的 j 节点所要花费的最短距离。

#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define CLR(a,v) memset(a,v,sizeof(a))

typedef pair<double,double> PDD;

PDD p[55];

#define F first
#define S second

double d[55][55];

double sqr(double x)
{
    return x * x;
}

double dis(PDD& p1,PDD& p2)
{
    return sqrt( sqr(p1.F - p2.F) + sqr(p1.S - p2.S) );
}

namespace Trie
{
    const int N = 505;
    const int Size = 50;
    int top;
    struct Node{
        Node *next[Size], *f;
        bool ended;
    }node[N], *root;
    inline Node* new_node()
    {
        node[top].ended = false;
        CLR(node[top].next,NULL);
        return &node[top++];
    }
    void init()
    {
        top = 0;
        root = new_node();
    }
    void insert(char *s)
    {
        Node *u = root;
        for(int i=0;s[i];i++)
        {
            int id = s[i] - 1;
            if(u->next[id] == NULL)
                u->next[id] = new_node();
            u = u->next[id];
        }
        u->ended = true;
    }
}

namespace ACam
{
    using namespace Trie;
    void get_fail()
    {
        queue<Node*> Q;
        for(int i=0;i<Size;i++)
        {
            Node *&ch = root->next[i];
            if(!ch)
                ch = root;
            else
            {
                ch->f = root;
                Q.push(ch);
            }
        }
        while(!Q.empty())
        {
            Node *cur = Q.front();Q.pop();
            for(int i=0;i<Size;i++)
            {
                Node *&ch = cur->next[i];
                if(!ch)
                    ch = cur->f->next[i];
                else
                {
                    ch->f = cur->f->next[i];
                    ch->ended |= ch->f->ended;
                    Q.push(ch);
                }
            }
        }
    }
    double dp[55][N];
    double solve(int n)
    {
        const double inf = 1e12;
        fill(&dp[0][0],&dp[54][Size-1],inf);
        int state_init = node[0].next[0] - node;
        if(node[state_init].ended)
            return -1;
        dp[0][state_init] = 0;
        for(int i=0;i<n-1;i++)
        {
            for(int j=0;j<top;j++)
            {
                if(dp[i][j] == inf)
                    continue;
                for(int k=i+1;k<n;k++)
                {
                    int jj = node[j].next[k] - node;
                    if(node[jj].ended)
                        continue;
                    dp[k][jj] = min(dp[k][jj],dp[i][j]+dis(p[i],p[k]));
                }
            }
        }
        double ans = inf;
        for(int j=0;j<top;j++)
            ans = min(ans,dp[n-1][j]);
        return ans == inf ? -1 : ans;
    }
}

char str[9];

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m),n||m)
    {
        ACam::init();
        for(int i=0;i<n;i++)
            scanf("%lf%lf",&p[i].F,&p[i].S);
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
                d[i][j] = dis(p[i],p[j]);
        }
        while(m--)
        {
            int k;
            scanf("%d",&k);
            for(int i=0;i<k;i++)
            {
                int id;
                scanf("%d",&id);
                str[i] = id;
            }
            str[k] = '\0';
            ACam::insert(str);
        }
        ACam::get_fail();
        double ans = ACam::solve(n);
        if(ans == -1)
            puts("Can not be reached!");
        else
            printf("%.2f\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/dgq8211/article/details/17481639