PKU 1570 Exchange Rates

http://poj.org/problem?id=1570
物々交換のレートのようなものと、現在のあるアイテムaとアイテムbの交換レートを尋ねるクエリが与えられるので、それを順次処理していくというような問題。

幅優先探索。
デバッグのためのコードをつけていたせいでWAになっていて、多少はまりました。

map<string,vector<pair<string,PI> > >edge;

main(){
  char c;

  while(cin>>c,c!='.'){

    if(c=='!'){
      int a,b;
      string ita,itb;
      cin>>a>>ita>>c>>b>>itb;

      int g=__gcd(a,b);
      edge[ita].pb(mp(itb,mp(a/g,b/g)));
      edge[itb].pb(mp(ita,mp(b/g,a/g)));
    }else{
      string ita,itb;
      cin>>ita>>c>>itb;
      set<string> vis;
      queue<pair<string,PI> >q;
      q.push(mp(ita,mp(1,1)));
      bool ok=false;
      while(!q.empty()){
        string v=q.front().F;
        PI cc=q.front().S;
        q.pop();
        if(vis.count(v))continue;
        vis.insert(v);
        if(v==itb){
          cout<<cc.S<<' '<<ita<<" = "<<cc.F<<' '<<itb<<endl;
          ok=true;
          break;
        }
        const vector<pair<string,PI> >& ed=edge[v];
        rep(i,SZ(ed)){
          if(vis.count(ed[i].F))continue;
          PI nc=cc;
          nc.F*=ed[i].S.S;
          nc.S*=ed[i].S.F;
          int g=__gcd(nc.F,nc.S);
          nc.F/=g;
          nc.S/=g;
          q.push(mp(ed[i].F,nc));
        }
      }
      if(ok)continue;
      cout<<"? "<<ita<<" = ? "<<itb<<endl;
    }
  }
}