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