PKU 3033 Traveling Salesman
http://poj.org/problem?id=3033
地球になぞらえて3次元座標で頂点からなる国の座標情報が与えられる。
国同士は、同じ辺を持っている時移動することができる。
ある国からある国に移動するには何回国境を渡る必要があるかを答えろというような問題。
入力をグラフに落としてBFS。
グラフに落とす部分が結構めんどくさいです。
自分は座標にユニークな番号をつけて、その番号二つで辺を表して、その辺をもつ国を持ったりしてました。
時間的にはそこまで厳しくないような気がします。
vector<int> G[6000]; int po[20]; bool vis[6000]; void solve(){ memset(vis,0,sizeof(vis)); int a,b; scanf("%d%d",&a,&b); --a,--b; queue<PI> q; q.push(mp(a,0)); while(!q.empty()){ int v=q.front().F; int cc=q.front().S; q.pop(); if(vis[v])continue; //cout<<v<<' '<<cc<<endl; vis[v]=true; if(v==b){ cout<<cc<<endl; return; } FOR(it,G[v]){ if(vis[*it])continue; q.push(mp(*it,cc+1)); } } } main(){ int c; while(scanf("%d",&c),c){ map<pair<int,PI>,int> pton; map<PI,vector<int> > etov; rep(i,c){ G[i].clear(); int n; scanf("%d",&n); rep(j,n){ int x,y,z; scanf("%d%d%d",&x,&y,&z); if(!pton.count(mp(x,mp(y,z)))){ int sz=SZ(pton); pton[mp(x,mp(y,z))]=sz; } po[j]=pton[mp(x,mp(y,z))]; } rep(j,n){ int u=min(po[j],po[(j+1)%n]); int v=max(po[j],po[(j+1)%n]); vector<int> & ver=etov[mp(u,v)]; FOR(it,ver){ G[i].pb(*it); G[*it].pb(i); } ver.pb(i); } } int m; scanf("%d",&m); while(m--) solve(); } }