2502:Subway - komiyamの日記

keyword

概要

2次元平面上に、現在地と目的地と、電車の路線図が与えられる。電車と徒歩の速度は一定の値をとる。電車を自由に使ってよいとき、目的地までの移動にかかる最小の時間を求める問題。
ダイクストラの練習問題。

static double g[610][610];
static pair<double, double> ps[610];

int main(){

    const double walk = 10*1000./60, subway = 40*1000./60;
    int i, j;
    int x, y, p = 0;
    double dist[610];
    x = readint();
    y = readint();
    ps[p++] = MP(x,y);
    ps[p++] = MP(-(1<<30),-(1<<30));

    x = readint();
    y = readint();
    ps[p++] = MP(x,y);
    ps[p++] = MP(-(1<<30),-(1<<30));

    while(scanf("%d%d",&x,&y)!=EOF){
        if(x == -1 && y == -1){
            ps[p++] = MP(-(1<<30),-(1<<30));
        }
        else{
            ps[p++] = MP(x,y);
        }
    }

    REP(i,p)REP(j,p){
        g[i][j] = getDist(ps[i],ps[j])/((abs(i-j)==1)?subway:walk);
    }

    priority_queue< pair<double, int>, vector<pair<double,int> >, greater<pair<double,int> > >Q;
    REP(i,p) dist[i] = -1;
    REP(i,p) Q.push( MP(0,0) );
    while(!Q.empty()){
        pair<double, int> tp = Q.top(); Q.pop();
        if(dist[tp.sc] >= 0) continue;
        dist[tp.sc] = tp.fs;
        REP(i,p)if(dist[i] < 0){
            Q.push( MP(tp.fs + g[tp.sc][i], i) );
        }
    }

    printf("%d\n", (int)(dist[2]+0.5));

    return 0;
}