全点間のユーグリッド距離求めてから50以下のものだけを辺として追加し、ダイクストラ。
最近番号が不規則に振られるからってmapで管理するのは非効率的だということに気づいた。コーディングスタイルを見直そう。
#include <iostream> #include <cmath> #include <map> #include <queue> #include <climits> #include <algorithm> using namespace std; typedef pair<double,double> P; typedef pair<double,int> NODE; #define X first #define Y second #define DST first #define POS second double ecd(P A,P B){ A.X = A.X-B.X; A.Y = A.Y-B.Y; return sqrt(A.X*A.X+A.Y*A.Y); } int main(){ int n,a,b,m; double x,y; while(cin >> n && n){ map<int,P> coord; map<int,int> from; map<int,vector< pair<int,double> > > info; map<int,double> memo,tmp; for(int i=0;i<n;i++){ cin >> a >> x >> y; coord[a] = make_pair(x,y); } for(map<int,P>::iterator it1 = coord.begin();it1 != coord.end();it1++){ for(map<int,P>::iterator it2 = coord.begin();it2 != coord.end();it2++){ if(!(ecd((*it1).second,(*it2).second) > 50.0)){ info[(*it1).first].push_back( make_pair((*it2).first,ecd((*it1).second,(*it2).second))); } } tmp[(*it1).first] = (1<<25); } cin >> m; for(int i=0;i<m;i++){ cin >> a >> b; vector<int> route; priority_queue<NODE,vector<NODE>,greater<NODE> > Q; Q.push(make_pair(0,a)); memo = tmp; memo[a]=0; from[a]=-1; while(Q.size()){ NODE q = Q.top();Q.pop(); if(q.POS == b){ int p = q.POS; while(~p){ route.push_back(p); p = from[p]; } break; } for(int i=0;i<info[q.POS].size();i++){ if(memo[info[q.POS][i].first] > q.DST + info[q.POS][i].second){ memo[info[q.POS][i].first] = q.DST + info[q.POS][i].second; from[info[q.POS][i].first] = q.POS; Q.push(make_pair(memo[info[q.POS][i].first],info[q.POS][i].first)); } } } if(route.size()){ reverse(route.begin(),route.end()); for(int i=0;i<route.size();i++){ if(i)cout << " "; cout << route[i]; } }else{ cout << "NA"; } cout << endl; } } }