Cyber Bird

夏休みも終わり、新学期に入ったなあ。
友達を罠にハメようと画策した末、見事に自分が返り討を喰らって…
級長になりました(笑)

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はプライオリティキューで実装したかったんですが、
前にプライオリティキューを使ったときはうまく動作しなかったので逃げましたｗ
まあどうせ、この程度の頂点数なら隣接行列で処理したところで処理速度は
落ちないので問題ないですが。