题目传送门(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 longchar 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原创, 转载必须以链接形式注明>原文链接<