BZOJ 3045: 电话线路 – [最短路/哈希]


题目传送门(BZOJ)

题解 :

惊了, JDFZ NOIP模拟赛为何考最短路模板 ?
惊了, Yirannn 为何最短路模板只得了70分?
惊了, Winniechen 为何最短路模板差10分曝氮?
好吧言归正传
这道题我们把所有电话号码读进来, 模一个大质数做拉链/查探哈希,
然后暴力枚举每个电话号码, 先 $10\times 10$ 枚举把哪位换成啥, 到表里查一下能和谁连边
然后 $10\times 10$ 枚举把哪两位交换, 再到表里查一下和谁连边
对于边权, 暴力求 LCP 即可
Winniechen神犇把前导零完全忽略了, 所以差点曝氮.
Yirannn 哈希写了个开放式寻址, 而且把 long long 硬生生分开读, 做的字符串哈希
然后发现没 unordered_map 快, 就换成了 umap 了, 所以卡 T 了 30
然鹅在 BZOJ 上, umap 轻松水过
震惊, llq 的 MacBook Air竟然比BZOJ 8¥ CPU 还要慢? (其实是BZOJ不是单点时间)

代码 :

#include <tr1/unordered_map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
using namespace std::tr1;
#define ll long long
#define ull unsigned long long
char buf[100000], *p1, *p2;
const int B = 2333;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
inline char gc() {
    char ch = nc();
    while(isspace(ch)) ch = nc();
    return ch;
}
unordered_map<ull, int> hsh;
int c[10], n, cnt;
int vis[51000];
priority_queue<pair<int, int> > q;
ll dis[51000];
struct EDGE {
    int to, val;
    EDGE* next;
}*h[50100], e[2000010];
inline void addEdge(int u, int v, int w) {
    if(u == v) return;
    w = c[w];
    EDGE* tmp = &e[++cnt];
    tmp->to = v;
    tmp->val = w;
    tmp->next = h[u];
    h[u] = tmp;
}
ll Dijkstra() {
    memset(dis, 0x3f, sizeof dis); dis[1] = 0;
    q.push(make_pair(0, 1));
    while(!q.empty()) {
        int u = q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(EDGE* i = h[u]; i; i = i->next) if(dis[i->to] > dis[u]+i->val) {
            dis[i->to] = dis[u]+i->val;
            q.push(make_pair(-dis[i->to], i->to));
        }
    }
    return dis[n];
}
struct NUMBER {
    ull hash;
    int num[10];
    bool operator == (const NUMBER &A) const {
        for(int i = 0; i < 10; i ++ ) if(num[i] != A.num[i]) return 0;
        return 1;
    }
    inline void read() {
        num[0] = gc()^48;
        for(int i = 1; i < 10; i ++ ) num[i] = nc()^48; 
    }
    inline void getHash() {
        hash = hash*B+num[0]; hash = hash*B+num[1]; 
        hash = hash*B+num[2]; hash = hash*B+num[3];
        hash = hash*B+num[4]; hash = hash*B+num[5]; 
        hash = hash*B+num[6]; hash = hash*B+num[7];
        hash = hash*B+num[8]; hash = hash*B+num[9];
    }
    inline int LCP(const NUMBER &A) const {
        if(num[0] != A.num[0]) return 0;
        int i;
        for(i = 0; i < 10; i ++ ) if(num[i+1] != A.num[i+1]) break;
        return i+1;
    }
}a[50100];
int main() {
    // freopen("zipcode.in", "r", stdin);
    // freopen("zipcode.out", "w", stdout);
    scanf("%d", &n);
    register int i, j, k;
    for(i = 0; i < 10; i ++ ) scanf("%d", &c[i]);
    for(i = 1; i <= n; i ++ ) a[i].read(), a[i].getHash(), hsh[a[i].hash] = i;
    for(i = 1; i <= n; i ++ ) {
        NUMBER tmp = a[i];
        for(j = 0; j < 10; j ++ ) {
            int were = tmp.num[j];
            for(k = 0; k < 10; k ++ ) {
                tmp.num[j] = k;
                tmp.hash = 0; tmp.getHash(); ull x = tmp.hash;
                if(hsh[x]) addEdge(i, hsh[x], a[i].LCP(tmp));
            }
            tmp.num[j] = were;
        }
        for(j = 0; j < 10; j ++ ) for(k = 0; k < 10; k ++ ) {
            swap(tmp.num[j], tmp.num[k]);
            tmp.hash = 0; tmp.getHash(); ull x = tmp.hash;
            if(hsh[x]) addEdge(i, hsh[x], a[i].LCP(tmp));
            swap(tmp.num[j], tmp.num[k]);
        }
    }
    ll ans = Dijkstra(); 
    printf("%lld\n", ans == dis[0] ? -1 : ans);
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<

发表评论

电子邮件地址不会被公开。 必填项已用*标注