[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。
#include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <map> #define INF (1<<21) #define MAXV 1000 using namespace std; typedef pair<int, int> P; int n, m; P B[MAXV]; // ビル情報 double dist( int x1, int y1, int x2, int y2 ) { return sqrt( pow( x1-x2, 2 ) + pow( y1-y2, 2 ) ); } void dijkstra( int s, int g ) { int prev[MAXV]; // 直前に通った頂点 double d[MAXV]; // 最短距離 bool used[MAXV]; // 最短距離が確定しているか fill( prev, prev + n, -1 ); fill( d, d + n, INF ); fill( used, used + n, false ); d[s] = 0; while(1) { int v = -1; for( int u = 0; u < n; u++ ) { if( !used[u] && ( v == -1 || d[u] < d[v] )) v = u; } if( v == -1 ) break; used[v] = true; for( int u = 0; u < n; u++ ) { double cost = dist( B[v].first, B[v].second, B[u].first, B[u].second ); if( cost <= 50 && d[u] > d[v] + cost ) { d[u] = d[v] + cost; prev[u] = v; } } } if( d[g] == INF ) { cout << "NA" << endl; return; } vector<int> path; for( int t = g; t != -1; t = prev[t] ) path.push_back(t); reverse( path.begin(), path.end() ); for( int i = 0; i < path.size(); i++ ) { cout << path[i] + 1; if( i < path.size() - 1 ) cout << " "; else cout << endl; } } main() { int s, t; while( cin >> n && n ) { for( int i = 0; i < n; i++ ) { cin >> s; cin >> B[s-1].first >> B[s-1].second; } cin >> m; for( int i = 0; i < m; i++ ) { cin >> s >> t; dijkstra( s-1, t-1 ); } } }自分では割ときれいに解けた方ではないかと思う。たぶん30分弱。
COMMENT