zoj 3030 Prester John

zoj 3030 Prester John

#include <algorithm> #include <set>#include <map>#include <queue>#include <cstdio>#include <vector>#include <string>#include <utility>using namespace std;vector<pair<int, int> > e[2][50005];int get_id(const char* str){    static map<string, int> mp;    static map<string, int>::const_iterator it;    int ret;    if (str == NULL) {        mp.clear();        ret = -1;    }    else if ((it = mp.find(str)) != mp.end()) {        ret = it->second;    }    else {        ret = mp.size();        mp[str] = ret;    }    return ret;}int main(){    int re, n[2], p[2], a, b, c, d;    static char buf[1024];    scanf("%d", &re);    while (re--) {        (void)get_id(NULL);        for (int i = 0; i < 2; i++) { scanf("%d%d", &n[i], &p[i]); for (int j = 0; j < n[i]; j++) {     e[i][j].clear(); } scanf("%d", &d); while (d--) {     scanf("%d%s%d", &a, buf, &b);     e[i][a].push_back(make_pair(get_id(buf), b)); } for (int j = 0; j < n[i]; j++) {     sort(e[i][j].begin(), e[i][j].end()); }        }        pair<int, int> src, cur, tar = make_pair(p[0], p[1]);        set<pair<int, int> > st;        queue<pair<int, int> > q;        vector<pair<int, int> >::const_iterator p;        st.insert(make_pair(0, 0));        q.push(make_pair(0, 0));        d = 0;        while (!q.empty() && st.count(tar) == 0) { c = q.size(); ++d; while (c--) {     src = q.front();     q.pop();     p = e[1][src.second].begin();     for (vector<pair<int, int> >::const_iterator i = e[0][src.first].begin(); i != e[0][src.first].end(); ++i) {         while (p != e[1][src.second].end() && p->first < i->first) {  ++p;         }         if (p == e[1][src.second].end()) {  break;         }         if (p->first == i->first) {  cur = make_pair(i->second, p->second);  if (st.count(cur) == 0) {      st.insert(cur);      q.push(cur);      if (cur == tar) {          break;      }  }         }     } }        }        printf("%dn", q.empty() ? -1 : d);    }    return 0;}