#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
#define fst first
#define snd second
const int INF = 99999999;
struct graph {
int n;
struct edge { int src, dst, weight; };
vector<vector<edge>> adj, rdj;
graph(int n) : n(n), adj(n), rdj(n) { }
void add_edge(int u, int v, int w) {
adj[u].push_back({u, v, w});
rdj[v].push_back({v, u, w});
}
// bidirectional dijkstra
int shortest_path(int s, int t) {
if (s == t) return 0;
vector<int> ds(n, INF), dt(n, INF);
typedef pair<int, int> node;
priority_queue<node, vector<node>, greater<node>> Qs, Qt;
Qs.push({ds[s] = 0, s});
Qt.push({dt[t] = 0, t});
int mu = INF;
while (!Qs.empty() && !Qt.empty()) {
if (Qs.top().fst + Qt.top().fst >= mu) break;
if (Qs.top().fst <= Qt.top().fst) {
node x = Qs.top(); Qs.pop();
if (ds[x.snd] > x.fst) continue;
for (edge &e: adj[x.snd]) {
if (ds[e.src] + e.weight < ds[e.dst]) {
mu = min(mu, ds[e.src] + e.weight + dt[e.dst]);
ds[e.dst] = ds[e.src] + e.weight;
Qs.push({ds[e.dst], e.dst});
}
}
} else {
node x = Qt.top(); Qt.pop();
if (dt[x.snd] > x.fst) continue;
for (edge &e: rdj[x.snd]) {
if (dt[e.src] + e.weight < dt[e.dst]) {
mu = min(mu, dt[e.src] + e.weight + ds[e.dst]);
dt[e.dst] = dt[e.src] + e.weight;
Qt.push({dt[e.dst], e.dst});
}
}
}
}
return mu;
}
// single directional dijkstra
int shortest_path2(int s, int t) {
vector<int> dist(n, INF);
typedef pair<int, int> node;
priority_queue<node, vector<node>, greater<node>> Q;
Q.push({dist[s] = 0, s});
while (!Q.empty()) {
node x = Q.top(); Q.pop();
if (x.snd == t) break;
if (dist[x.snd] > x.fst) continue;
for (edge &e: adj[x.snd]) {
if (dist[e.src] + e.weight < dist[e.dst]) {
dist[e.dst] = dist[e.src] + e.weight;
Q.push({dist[e.dst], e.dst});
}
}
}
return dist[t];
}
};
// === tick a time ===
#include <ctime>
double tick() {
static clock_t oldtick;
clock_t newtick = clock();
double diff = 1.0*(newtick - oldtick) / CLOCKS_PER_SEC;
oldtick = newtick;
return diff;
}
int test() {
int n = 2000;
graph g(n);
for (int u = 0; u < n; ++u) {
int d = 1 + rand() % 30;
unordered_set<int> N;
while (N.size() < d) {
int v = rand() % n;
if (u != v) N.insert(v);
}
for (auto v: N) {
int w = 1 + rand() % 10;
g.add_edge(u, v, w);
}
}
double t1 = 0, t2 = 0;
for (int u = 0; u < n; ++u) {
int v = rand() % n;
tick();
int a = g.shortest_path(u, v);
t1 += tick();
int b = g.shortest_path2(u, v);
t2 += tick();
if (a != b) {
cout << u << " -> " << v << ": " << a << " / " << b << endl;
return false;
}
}
cout << t1 << " " << t2 << endl;
cout << "bidirectional dijkstra is " << t2/t1 << " times faster" << endl;
return true;
}
// verify: SPOJ SHPATH
void solve() {
int n;
scanf("%d", &n);
graph g(n);
map<string, int> id;
for (int u = 0; u < n; ++u) {
char name[1024];
scanf("%s", name);
id[name] = u;
int k;
scanf("%d", &k);
for (int j = 0; j < k; ++j) {
int v, d;
scanf("%d %d", &v, &d);
g.add_edge(u, v-1, d);
}
}
int k;
scanf("%d", &k);
for (int i = 0; i < k; ++i) {
char s[1024], t[1024];
scanf("%s %s", s, t);
printf("%d\n", g.shortest_path(id[s], id[t]));
}
}
int main() {
test();
return 0;
// verify: SPOJ SHPATH
int ncase; scanf("%d", &ncase);
for (int icase = 0; icase < ncase; ++icase) solve();
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDx1bm9yZGVyZWRfc2V0PgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgZnN0IGZpcnN0CiNkZWZpbmUgc25kIHNlY29uZAoKY29uc3QgaW50IElORiA9IDk5OTk5OTk5OwpzdHJ1Y3QgZ3JhcGggewogIGludCBuOwogIHN0cnVjdCBlZGdlIHsgaW50IHNyYywgZHN0LCB3ZWlnaHQ7IH07CiAgdmVjdG9yPHZlY3RvcjxlZGdlPj4gYWRqLCByZGo7CiAgZ3JhcGgoaW50IG4pIDogbihuKSwgYWRqKG4pLCByZGoobikgeyB9CiAgdm9pZCBhZGRfZWRnZShpbnQgdSwgaW50IHYsIGludCB3KSB7CiAgICBhZGpbdV0ucHVzaF9iYWNrKHt1LCB2LCB3fSk7CiAgICByZGpbdl0ucHVzaF9iYWNrKHt2LCB1LCB3fSk7CiAgfQoKICAvLyBiaWRpcmVjdGlvbmFsIGRpamtzdHJhCiAgaW50IHNob3J0ZXN0X3BhdGgoaW50IHMsIGludCB0KSB7CiAgICBpZiAocyA9PSB0KSByZXR1cm4gMDsKICAgIHZlY3RvcjxpbnQ+IGRzKG4sIElORiksIGR0KG4sIElORik7CiAgICB0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IG5vZGU7CiAgICBwcmlvcml0eV9xdWV1ZTxub2RlLCB2ZWN0b3I8bm9kZT4sIGdyZWF0ZXI8bm9kZT4+IFFzLCBRdDsKICAgIFFzLnB1c2goe2RzW3NdID0gMCwgc30pOwogICAgUXQucHVzaCh7ZHRbdF0gPSAwLCB0fSk7CiAgICBpbnQgbXUgPSBJTkY7CiAgICB3aGlsZSAoIVFzLmVtcHR5KCkgJiYgIVF0LmVtcHR5KCkpIHsKICAgICAgaWYgKFFzLnRvcCgpLmZzdCArIFF0LnRvcCgpLmZzdCA+PSBtdSkgYnJlYWs7CiAgICAgIGlmIChRcy50b3AoKS5mc3QgPD0gUXQudG9wKCkuZnN0KSB7CiAgICAgICAgbm9kZSB4ID0gUXMudG9wKCk7IFFzLnBvcCgpOwogICAgICAgIGlmIChkc1t4LnNuZF0gPiB4LmZzdCkgY29udGludWU7CiAgICAgICAgZm9yIChlZGdlICZlOiBhZGpbeC5zbmRdKSB7CiAgICAgICAgICBpZiAoZHNbZS5zcmNdICsgZS53ZWlnaHQgPCBkc1tlLmRzdF0pIHsKICAgICAgICAgICAgbXUgPSBtaW4obXUsIGRzW2Uuc3JjXSArIGUud2VpZ2h0ICsgZHRbZS5kc3RdKTsKICAgICAgICAgICAgZHNbZS5kc3RdID0gZHNbZS5zcmNdICsgZS53ZWlnaHQ7CiAgICAgICAgICAgIFFzLnB1c2goe2RzW2UuZHN0XSwgZS5kc3R9KTsKICAgICAgICAgIH0KICAgICAgICB9CiAgICAgIH0gZWxzZSB7CiAgICAgICAgbm9kZSB4ID0gUXQudG9wKCk7IFF0LnBvcCgpOwogICAgICAgIGlmIChkdFt4LnNuZF0gPiB4LmZzdCkgY29udGludWU7CiAgICAgICAgZm9yIChlZGdlICZlOiByZGpbeC5zbmRdKSB7CiAgICAgICAgICBpZiAoZHRbZS5zcmNdICsgZS53ZWlnaHQgPCBkdFtlLmRzdF0pIHsKICAgICAgICAgICAgbXUgPSBtaW4obXUsIGR0W2Uuc3JjXSArIGUud2VpZ2h0ICsgZHNbZS5kc3RdKTsKICAgICAgICAgICAgZHRbZS5kc3RdID0gZHRbZS5zcmNdICsgZS53ZWlnaHQ7CiAgICAgICAgICAgIFF0LnB1c2goe2R0W2UuZHN0XSwgZS5kc3R9KTsKICAgICAgICAgIH0KICAgICAgICB9CiAgICAgIH0KICAgIH0KICAgIHJldHVybiBtdTsKICB9CgogIC8vIHNpbmdsZSBkaXJlY3Rpb25hbCBkaWprc3RyYQogIGludCBzaG9ydGVzdF9wYXRoMihpbnQgcywgaW50IHQpIHsKICAgIHZlY3RvcjxpbnQ+IGRpc3QobiwgSU5GKTsKICAgIHR5cGVkZWYgcGFpcjxpbnQsIGludD4gbm9kZTsKICAgIHByaW9yaXR5X3F1ZXVlPG5vZGUsIHZlY3Rvcjxub2RlPiwgZ3JlYXRlcjxub2RlPj4gUTsKICAgIFEucHVzaCh7ZGlzdFtzXSA9IDAsIHN9KTsKICAgIHdoaWxlICghUS5lbXB0eSgpKSB7CiAgICAgIG5vZGUgeCA9IFEudG9wKCk7IFEucG9wKCk7CiAgICAgIGlmICh4LnNuZCA9PSB0KSBicmVhazsKICAgICAgaWYgKGRpc3RbeC5zbmRdID4geC5mc3QpIGNvbnRpbnVlOwogICAgICBmb3IgKGVkZ2UgJmU6IGFkalt4LnNuZF0pIHsKICAgICAgICBpZiAoZGlzdFtlLnNyY10gKyBlLndlaWdodCA8IGRpc3RbZS5kc3RdKSB7CiAgICAgICAgICBkaXN0W2UuZHN0XSA9IGRpc3RbZS5zcmNdICsgZS53ZWlnaHQ7CiAgICAgICAgICBRLnB1c2goe2Rpc3RbZS5kc3RdLCBlLmRzdH0pOwogICAgICAgIH0KICAgICAgfQogICAgfQogICAgcmV0dXJuIGRpc3RbdF07CiAgfQp9OwoKCi8vID09PSB0aWNrIGEgdGltZSA9PT0KI2luY2x1ZGUgPGN0aW1lPgpkb3VibGUgdGljaygpIHsKICBzdGF0aWMgY2xvY2tfdCBvbGR0aWNrOwogIGNsb2NrX3QgbmV3dGljayA9IGNsb2NrKCk7CiAgZG91YmxlIGRpZmYgPSAxLjAqKG5ld3RpY2sgLSBvbGR0aWNrKSAvIENMT0NLU19QRVJfU0VDOwogIG9sZHRpY2sgPSBuZXd0aWNrOwogIHJldHVybiBkaWZmOwp9CmludCB0ZXN0KCkgewogIGludCBuID0gMjAwMDsgCiAgZ3JhcGggZyhuKTsKICBmb3IgKGludCB1ID0gMDsgdSA8IG47ICsrdSkgewogICAgaW50IGQgPSAxICsgcmFuZCgpICUgMzA7CiAgICB1bm9yZGVyZWRfc2V0PGludD4gTjsKICAgIHdoaWxlIChOLnNpemUoKSA8IGQpIHsKICAgICAgaW50IHYgPSByYW5kKCkgJSBuOwogICAgICBpZiAodSAhPSB2KSBOLmluc2VydCh2KTsKICAgIH0KICAgIGZvciAoYXV0byB2OiBOKSB7CiAgICAgIGludCB3ID0gMSArIHJhbmQoKSAlIDEwOwogICAgICBnLmFkZF9lZGdlKHUsIHYsIHcpOwogICAgfQogIH0KICBkb3VibGUgdDEgPSAwLCB0MiA9IDA7CiAgZm9yIChpbnQgdSA9IDA7IHUgPCBuOyArK3UpIHsKICAgIGludCB2ID0gcmFuZCgpICUgbjsKICAgIHRpY2soKTsKICAgIGludCBhID0gZy5zaG9ydGVzdF9wYXRoKHUsIHYpOwogICAgdDEgKz0gdGljaygpOwogICAgaW50IGIgPSBnLnNob3J0ZXN0X3BhdGgyKHUsIHYpOwogICAgdDIgKz0gdGljaygpOwogICAgaWYgKGEgIT0gYikgewogICAgICBjb3V0IDw8IHUgPDwgIiAtPiAiIDw8IHYgPDwgIjogIiA8PCBhIDw8ICIgLyAiIDw8IGIgPDwgZW5kbDsKICAgICAgcmV0dXJuIGZhbHNlOwogICAgfQogIH0KICBjb3V0IDw8IHQxIDw8ICIgIiA8PCB0MiA8PCBlbmRsOwogIGNvdXQgPDwgImJpZGlyZWN0aW9uYWwgZGlqa3N0cmEgaXMgIiA8PCB0Mi90MSA8PCAiIHRpbWVzIGZhc3RlciIgPDwgZW5kbDsKICByZXR1cm4gdHJ1ZTsKfQoKLy8gdmVyaWZ5OiBTUE9KIFNIUEFUSAp2b2lkIHNvbHZlKCkgewogIGludCBuOyAKICBzY2FuZigiJWQiLCAmbik7CiAgZ3JhcGggZyhuKTsKICBtYXA8c3RyaW5nLCBpbnQ+IGlkOwogIGZvciAoaW50IHUgPSAwOyB1IDwgbjsgKyt1KSB7CiAgICBjaGFyIG5hbWVbMTAyNF07CiAgICBzY2FuZigiJXMiLCBuYW1lKTsKICAgIGlkW25hbWVdID0gdTsKICAgIGludCBrOwogICAgc2NhbmYoIiVkIiwgJmspOwogICAgZm9yIChpbnQgaiA9IDA7IGogPCBrOyArK2opIHsKICAgICAgaW50IHYsIGQ7CiAgICAgIHNjYW5mKCIlZCAlZCIsICZ2LCAmZCk7CiAgICAgIGcuYWRkX2VkZ2UodSwgdi0xLCBkKTsKICAgIH0KICB9CiAgaW50IGs7CiAgc2NhbmYoIiVkIiwgJmspOwogIGZvciAoaW50IGkgPSAwOyBpIDwgazsgKytpKSB7CiAgICBjaGFyIHNbMTAyNF0sIHRbMTAyNF07CiAgICBzY2FuZigiJXMgJXMiLCBzLCB0KTsKICAgIHByaW50ZigiJWRcbiIsIGcuc2hvcnRlc3RfcGF0aChpZFtzXSwgaWRbdF0pKTsKICB9Cn0KCmludCBtYWluKCkgewogIHRlc3QoKTsKICByZXR1cm4gMDsKCiAgLy8gdmVyaWZ5OiBTUE9KIFNIUEFUSAogIGludCBuY2FzZTsgc2NhbmYoIiVkIiwgJm5jYXNlKTsKICBmb3IgKGludCBpY2FzZSA9IDA7IGljYXNlIDwgbmNhc2U7ICsraWNhc2UpIHNvbHZlKCk7Cn0K