BOJ 10473 인간대포

 

출발, 도착 지점과 대포들이 놓인 지점들을 정점으로 두고 각 정점들 사이의 이동시간을 가중치로 두면,

일반적인 최소 비용 문제(최단 경로 문제)가 된다.

 

대포를 이용해서 이동하거나 도보로 가거나 두 가지 선택지 있다.

위의 정보로부터 대포의 위치가 아닌 시작 정점을 제외한 정점에서 다른 정점을 잇는 간선의 가중치는

\[ time= \min( distance/5. \; , 2+|distance-50|/5.) \]

로 두면 된다. 시작 정점에서 다른 정점까지 가중치는

\[time = distance/5. \]

으로 둔다. (대포의 위치가 시작 위치와 겹쳐도 위의 식들은 유효하다. 0 시간을 이동해서 대포로 이동하는 상황이 될 것이다.)

 

 

#include<bits/stdc++.h>

using namespace std;

const double Inf=1e9;

struct info{
    double dst;
    int id;
    bool operator<(const info &rhs) const {
        return dst>rhs.dst;
    }
};

pair<double,double> sPos, ePos, arr[102];
double dst[102];
bool vst[102];

double cal_dist(int u, int v) {
    double dx=arr[u].first-arr[v].first, dy=arr[u].second-arr[v].second;
    return sqrt(dx*dx+dy*dy);
}

int main() {  
    scanf("%lf%lf%lf%lf",
            &sPos.first,&sPos.second,&ePos.first,&ePos.second);

    int n; scanf("%d",&n);
    arr[0]=sPos, arr[n+1]=ePos;

    for (int i=1; i<=n; i++) 
        scanf("%lf%lf", &arr[i].first, &arr[i].second);

    fill(dst, dst+n+2, Inf);
    dst[0] = 0;
    priority_queue<info> pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        info tInfo=pq.top();
        pq.pop();

        int cur=tInfo.id;
        if(cur==n+1) break;

        if (vst[cur]) continue;
        vst[cur] = true;

        for (int nxt=1; nxt<=n+1; nxt++) {
            double t1=cal_dist(cur, nxt)/5.;
            double t2=2.0+abs(cal_dist(cur, nxt)-50)/ 5.;
            double t=(cur==0)? t1 : min(t1, t2);
            if (dst[nxt]>dst[cur]+t) {
                dst[nxt]=dst[cur]+t;
                pq.push({dst[nxt], nxt});
            }
        }
    }
    printf("%f\n", dst[n+1]);
}