hdu 4511 - 샤 오 밍 시리즈 - 여자친 구 의 시련 (AC 자동 동기 + dp)

샤 오 밍 시리즈 - 여자친 구 의 시련 시간 Limit: 500 / 200 MS (Java / Others) 메모리 Limit: 65535 / 32768 K (Java / Others) Total Submission (s): 863 Accepted Submission (s): 192
Problem Description 이 드디어 겨울방학 이 되 었 습 니 다. 샤 오 밍 은 여자 친구 와 함께 영 화 를 보 러 가 려 고 합 니 다.이날 여자 친 구 는 샤 오 밍 에 게 시련 을 주 려 고 했다. 샤 오 밍 이 출발 준 비 를 하고 있 을 때 여자 친 구 는 그 에 게 영화관 에서 그 를 기다 리 고 있다 고 말 했다. 샤 오 밍 이 오 는 노선 은 반드시 주어진 규칙 을 만족 시 켜 야 한다. 1. 샤 오 밍 이 있 는 위치 가 1 번 점 이 고 여자 친구 가 있 는 위치 가 n 번 점 이 라면 그들 사이 에 n - 2 개의 점 이 걸 을 수 있다 고 가정 했다.샤 오 밍 은 갈 때마다 현재 지점 보다 번호 가 큰 위치 에 만 갈 수 있다.2. 샤 오 밍 이 올 때 일정한 순서에 따라 어떤 곳 을 지나 갈 수 없다.예 를 들 어 여자친 구가 샤 오 밍 에 게 1 - > 2 - > 3 을 거치 지 말 라 고 하면 샤 오 밍 이 올 때 걸 어 온 경 로 는 1 - > 2 - > 3 부분 을 포함 할 수 없 지만 1 - > 3 또는 1 - > 2 는 모두 가능 하 다. 이런 제한 경 로 는 여러 가지 가 있 을 수 있다.이것 은 샤 오 밍 을 매우 골 치 아 프 게 했 는데, 지금 그 는 문 제 를 너 에 게 맡 겼 다.특히 하나, 둘, 셋 이라는 세 점 의 공선 이 있 는데 도 샤 오 밍 이 1 에서 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 은 모든 사례 에 대해 요 구 를 만족 시 키 는 가장 짧 은 경로 가 존재 한다 면 이 가장 짧 은 경 로 를 출력 하 십시오. 결 과 는 두 개의 작은 수 를 유지 합 니 다.그렇지 않 으 면 출력 하 십시오. "도달 할 수 없습니다!"(인용 부 호 는 출력 할 필요 가 없다).
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 텐 센트 프로 그래 밍 마라톤 1 차 전 2 차 전 (3 월 22 일)
Recommend liuyiding | We have carefully selected several similar problems for you: 5209 5208 5207 5206 5205
일부 경로 가 존재 하지 않 는 다 는 것 을 알려 드 립 니 다. 이것 은 분명 한 힌트 입 니 다. 바로 자동 동기 dp 입 니 다. dp [i] [j] 는 자동 동기 노드 i 를 표시 하고 j 를 누 를 때 가장 짧 은 경로 입 니 다. 처음에 제 순환 방식 이 틀 렸 을 수도 있 습 니 다. 나중에 바 꾸 면 됩 니 다. 좌 표를 직접 double 로 읽 는 것 이 좋 겠 습 니 다.

/************************************************************************* > File Name: hdu4511.cpp > Author: ALex > Mail: [email protected] > Created Time: 2015 04 16      18 24 11  ************************************************************************/

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <bitset>
#include <set>
#include <vector>

using namespace std;

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;

const int MAX_NODE = 510;
int n;
double dp[MAX_NODE][55];

struct node
{
    double x, y;
}point[55];

double dist(node a, node b)
{
    double x = (a.x - b.x);
    double y = (a.y - b.y);
    return sqrt(x * x + y * y);
}

struct AC_Automation
{
    int next[MAX_NODE][55];
    int fail[MAX_NODE];
    int end[MAX_NODE];
    int root, L;

    int newnode()
    {
        for (int i = 0; i < n; ++i)
        {
            next[L][i] = -1;
        }
        end[L++] = 0;
        return L - 1;
    }

    void init ()
    {
        L = 0;
        root = newnode();
    }

    void Build_Trie (vector <int> buf)
    {
        int now = root;
        int len = buf.size();
        for (int i = 0; i < len; ++i)
        {
            if (next[now][buf[i]] == -1)
            {
                next[now][buf[i]] = newnode();
            }
            now = next[now][buf[i]];
        }
        end[now] = 1;
    }

    void Build_AC ()
    {
        queue <int> qu;
        fail[root] = root;
        for (int i = 0; i < n; ++i)
        {
            if (next[root][i] == -1)
            {
                next[root][i] = root;
            }
            else
            {
                fail[next[root][i]] = root;
                qu.push (next[root][i]);
            }
        }
        while (!qu.empty())
        {
            int now = qu.front();
            qu.pop();
            if (end[fail[now]])
            {
                end[now] = 1;
            }
            for (int i = 0; i < n; ++i)
            {
                if (next[now][i] == -1)
                {
                    next[now][i] = next[fail[now]][i];
                }
                else
                {
                    fail[next[now][i]] = next[fail[now]][i];
                    qu.push(next[now][i]);
                }
            }
        }
    }

    void solve()
    {
        for (int i = 0; i < L; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                dp[i][j] = (1LL << 60);
            }
        }
        dp[next[root][0]][0] = 0.0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < L; ++j)
            {
                if (dp[j][i] < (1LL << 60))
                {
                    for (int k = i + 1; k < n; ++k)
                    {
                        int nxt = next[j][k];
                        if (end[nxt])
                        {
                            continue;
                        }
                        dp[nxt][k] = min(dp[nxt][k], dp[j][i] + dist(point[k], point[i]));
                    }
                }
            }
        }
        double ans = (1LL << 60);
        for (int i = 0; i < L; ++i)
        {
            if (end[i] == 0)
            {
                ans = min(ans, dp[i][n - 1]);
            }
        }
        if (ans == (1LL << 60))
        {
            printf("Can not be reached!
");
        }
        else
        {
            printf("%.2f
", ans);
        }
    }

}AC;

vector <int> buf;

int main()
{
    int m;
    while (~scanf("%d%d", &n, &m))
    {
        if (!n && !m)
        {
            break;
        }
        AC.init();
        int tmp;
        for (int i = 0; i < n; ++i)
        {
            scanf("%lf%lf", &point[i].x, &point[i].y);
        }
        for (int i = 1; i <= m; ++i)
        {
            int k;
            buf.clear();
            scanf("%d", &k);
            while (k--)
            {
                scanf("%d", &tmp);
                --tmp;
                buf.push_back(tmp);
            }
            AC.Build_Trie(buf);
        }
        AC.Build_AC();
        AC.solve();
    }
    return 0;
}