2007年予選第8問(AOJ:No.0155)
夏休みも終わり、新学期に入ったなあ。
友達を罠にハメようと画策した末、見事に自分が返り討を喰らって…
級長になりました(笑)
2学期の級長って面倒なんだよな。体育祭あったり文化祭あったりで…。
ま、高校時代の楽しい思い出づくりと思えば。
今日はパソコン甲子園2日前なので、もう大詰め(?)です。
そういえば、パソコン甲子園はてっきり去年同様、午前だと思っていたのに、
見事に13:30〜だったので、午後に予定していた広島県科学オリンピックセミナーは
出られなくなりました。
本日の問題はこちら。
パソコン甲子園2007年予選の第8問です。ちなみに18点だったか。
それでは続きからどうぞ。
#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分弱。
これは僕の実力から考えると、かなりストレートに到達出来てる。
ビル(頂点)を移動する最短距離を求めよということなので、
グラフの最短路問題になります。加えて最短路を出力するので経路復元です。
まずは…mainから。
しっかりと設問通り入力を受けて、変数に格納です。
座標はまたまたpairを使わせてもらいました。構造体を作るのも面倒だし、
STLなのでインスタンス化するだけで楽に扱えます。
注意すべきは、本問ではビル番号は1から始まるので、配列格納のために
- 1するのを忘れないこと。
dist関数は見たまんま、(x1, y1)と(x2, y2)の間の距離を求めます。
double型にしたのは、2点間の距離を求める際にルートをかけるので、
小数点以下がどうしても発生するため、きちんと受けるためです。
はじめはここをintにしていたので、正しく処理が行われませんでした。
dijkstra関数は…まあダイクストラ法で始点ビルsから各ビルへの
最短距離をそれぞれダイクストラ法で求め、sからgへの最短パスを弾きだします。
2ビル間の距離が50より大きかったら処理しないこと。これも忘れずに。
本当はdijkstraはプライオリティキューで実装したかったんですが、
前にプライオリティキューを使ったときはうまく動作しなかったので逃げましたｗ
まあどうせ、この程度の頂点数なら隣接行列で処理したところで処理速度は
落ちないので問題ないですが。
