Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <bits/stdc++.h>
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<uint, int> P;
vector<P> 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<int V>
struct Dijkstra {
typedef int T; /// 辺の距離の型
const int INF = 1e9;
typedef pair<T, int> P;
vector<P> 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<P, vector<P>, greater<P>> 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<string, int> 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment