gym：Problem B Bless You Autocorrect!(字典树+最短路)

				2016-2017-acmicpc-nordic-collegiate-programming-contest-ncpc-2016

Problem B Bless You Autocorrect!

题目链接：http://codeforces.com/gym/101550

题意：就是给你一些单词，每个单词有一个热度，热度是按照给出的顺序排序的，你可以输入字母后点击TAB键自动补全，现在q次询问，每次询问给你一个单词，你需要输出得到这个单词包括字母、TAB键和删除键在内的最少点击次数。

解题思路：

• 刚开始还以为是一个二分查找，后来发现不太对，因为在打字的时候可以多次点击TAB键补全，还可以补全之后删去。这就很复杂无法排序后二分。
• 后来想了想，可以根据刚开始输入的每个单词建立字典树，然后在字段数上跑一个最短路，得到的就是从０开始到当前字符串需要的最少点击数，然后每一次输入就可以直接在字典树上查询，答案就是min(到当前点的最短路值+剩下的字母数目)。

---

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e6 + 100;

struct trip {
    int va, shortest_path_len, father;//记录这个节点的值、达到这个节点需要的最少按键次数、它的父亲
    int child[30];
} node[maxn];

int n, m, Len[maxn], cnt = 1, End[maxn];

char s[maxn];

void build_tree(int num) {
    int pos = 0;
    int len = int(strlen(s));
    Len[num] = len;
    for (int i = 0; i < len; i++) {
        int pos1 = pos;
        if (node[pos].child[s[i] - 'a']== 0) {
            node[pos].child[s[i] - 'a'] = cnt++;
            node[cnt - 1].va = num;
            node[cnt - 1].shortest_path_len = INT_MAX;
            if(i == len-1) {
                End[num] = cnt-1;//记录这个字符串的结束位置
            }
        }
        pos = node[pos].child[s[i] - 'a'];
        node[pos].father = pos1;//记录父节点方便跑最短路
    }
}

bool vis[maxn];

void bfs() {//只要有更短的路就一直更新
    queue <int> qu;
    qu.push(0);
    while(!qu.empty()) {
        int pos = qu.front();
        qu.pop();
        for(int i=0;i<26;i++) {
            if(node[pos].child[i]) {
                int pos1 = node[pos].child[i];
                if(!vis[node[pos1].va]) {//当前节点按TAB可以直接到结束位置，这个时候压如结束位置，并且判断结束位置是否就是下一个位置
                    vis[node[pos1].va] = true;
                    qu.push(End[node[pos1].va]);
                    node[End[node[pos1].va]].shortest_path_len = min(node[End[node[pos1].va]].shortest_path_len, node[pos].shortest_path_len+2);
                }
                if(node[pos1].shortest_path_len > node[pos].shortest_path_len+1) {
                    node[pos1].shortest_path_len = node[pos].shortest_path_len+1;
                    qu.push(pos1);
                }
            }
        }
        int pos1 = node[pos].father;//父节点可能也有更优的值进行更新
        if(node[pos1].shortest_path_len > node[pos].shortest_path_len+1) {
            node[pos1].shortest_path_len = node[pos].shortest_path_len+1;
            qu.push(pos1);
        }
    }
}

void init() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        build_tree(i);
    }
    bfs();
}

void find() {
    int len = int(strlen(s));
    int pos = 0, Min = INT_MAX;
    for (int i = 0; i < len; i++) {
        pos = node[pos].child[s[i] - 'a'];
        if(pos == 0)
            break;
        Min = min(Min, node[pos].shortest_path_len+(len-i-1));
        if(node[pos].va == 0) {
            break;
        }
    }
    if(Min == INT_MAX) Min = len;
    printf("%d\n", Min);
}

void query() {
    while (m--) {
        scanf("%s", s);
        find();
    }
}

int main() {
    //freopen("1.in", "r", stdin);
    init();
    query();
    return 0;
}