{{ message }}

Instantly share code, notes, and snippets.

# yosupo06/gist:9e42b9a17684611f4c8a

Created Apr 5, 2015
 #include using namespace std; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; int bsr(uint x) { if (x == 0) return -1; return 31-__builtin_clz(x); } struct RadixHeap { typedef pair P; vector

v[33]; uint last, sz; RadixHeap() { last = sz = 0; } void push(uint x, int p) { assert(last <= x); sz++; v[bsr(x^last)+1].push_back(P(x, p)); } void push(P p) { push(p.first, p.second); } P top() { return pop(false); } P pop(bool f = true) { assert(sz); if (!v[0].size()) { int i = 1; while (!v[i].size()) i++; last = min_element(v[i].begin(), v[i].end())->first; for (P p: v[i]) { v[bsr(p.first^last)+1].push_back(p); } v[i].clear(); } P r = v[0].back(); if (f) { sz--; v[0].pop_back(); } return r; } int size() { return sz; } bool empty() { return sz == 0; } void clear() { last = sz = 0; for (int i = 0; i < 33; i++) { v[i].clear(); } } }; /** * Dijkstra法により最短距離を求める * * template引数のint Vは頂点数 */ template struct Dijkstra { typedef int T; /// 辺の距離の型 const int INF = 1e9; typedef pair P; vector

g[V]; /// 辺のクリア void init() { for (int i = 0; i < V; i++) { g[i].clear(); } } /// 辺の追加 void add(int from, int to, T dist) { g[from].push_back(P(dist, to)); } T res[V]; /// execを行うと、これに最短距離が入る void exec(int s) { fill_n(res, V, INF); priority_queue, greater

> q; // RadixHeap q; q.push(P(0, s)); res[s] = 0; while (!q.empty()) { P p = q.top(); q.pop(); if (res[p.second] < p.first) continue; for (P e: g[p.second]) { if (p.first+e.first < res[e.second]) { res[e.second] = p.first+e.first; q.push(P(e.first+p.first, e.second)); } } } return; } }; Dijkstra<10100> dijk; int main() { int T; scanf("%d", &T); for (int t = 0; t < T; t++) { dijk.init(); int n; scanf("%d", &n); unordered_map mp; for (int i = 0; i < n; i++) { char name[20]; scanf("%s", name); string s = name; mp[s] = i; int m; scanf("%d", &m); for (int j = 0; j < m; j++) { int a, d; scanf("%d %d", &a, &d); a--; dijk.add(i, a, d); } } int r; scanf("%d", &r); for (int i = 0; i < r; i++) { char namea[20], nameb[20]; scanf("%s %s", namea, nameb); string as = namea, bs = nameb; int a = mp[as], b = mp[bs]; dijk.exec(a); printf("%d\n", dijk.res[b]); } } return 0; }