gistfile1.cpp

#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;
}