PKU 1847 Tram

http://poj.org/problem?id=1847
n個のノードがあって、ノードaからノードbまで移動したい。
この時、あるノードから伸びているエッジのうち一番目のエッジはコスト0で移動できる。それいがいはコストが1かかる。
最小コストを求めろというような問題。

ダイクストラ

vector<int> G[100];
int vis[100];

main(){
  int n,a,b;
  cin>>n>>a>>b;
  a--,b--;
  rep(i,n){
    int t;
    cin>>t;
    rep(j,t){
      int to;
      cin>>to;
      --to;
      G[i].pb(to);
    }
  }
  priority_queue<PI> q;
  q.push(mp(0,a));
  int ans=-1;
  memset(vis,-1,sizeof(vis));
  while(!q.empty()){
    int cc=-q.top().F,v=q.top().S;q.pop();
    if(vis[v]!=-1 && vis[v]<=cc)continue;
    vis[v]=cc;
    if(v==b){
      ans=cc;
      break;
    }
    rep(i,SZ(G[v])){
      int nc=cc;
      if(i)++nc;
      q.push(mp(-nc,G[v][i]));
    }
  }
  cout<<ans<<endl;
}