koi 2016 고등부 본선 주유소(고등)

koi 2016 고등부 본선 주유소(고등)

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2267&sca=60&s1=&s2=&s3=&s4=

 

경로를 진행할 때 지금 까지 거쳐온 주유소 중 최소 가격으로 계속 주유하면서 가는 것이 최선이다. 
​
dp[i][j]를 현재 i(1<=i<=n)번째 노드에 있을 때, 지나온 경로 중 j번째의 주유소 가격이 최소일 때의 최소 비용이라 정의한다.
​이후 i번째에서 갈수 있는 다른 노드로 뻗어가면서 dp테이블을 완성하면 된다.
i번째 노드에서 k번째 노드로 갈 때.
이동 거리를 D라 하자
cost[i]는 i번째 노드의 주유소 값이라 하자.
if(cost[k]>cost[i]){
dp[k][j]=min(dp[k][j],dp[i][j]+D*cost[j]);
else
dp[k][k]=min(dp[k][k],dp[i][j]+D*cost[j]);
​
이 과정을 힙을 이용해서 시간제한 안에 해결한다.​
priroriy queue를 최소가 우선 순위가 되도록 짠다.
처음 모든 dp 배열을 무한대로 초기화한다.
이후 dp[1][1]=0 에서 시작.
priority_queue에  dp,i,j를 dp값이 첫번째 원소가 되도록 넣어 준다.
반복문을 돌리면서 priority_queue top에서 최소 dp 값을 뽑아서 다른 dp 테이블을 갱신 해주고 prioriy_queue에 넣어주면 된다.
dp[N][i](1<=i<=N) 중 최소가 정답이다. 
O(NM+N^2 log N)


주유소 풀이

#include <bits/stdc++.h>

#define N 2505

#define INF 9876543219876LL

using namespace std;

  

typedef long long ll;

typedef pair<int,pair<int,int> > pp;

vector<int> V[N],C[N];

priority_queue<pp,vector<pp>,greater<pp> > Q;

  

ll n,m,dp[N][N],val[N];

bool visit[N][N];

void input(){

    scanf("%lld %lld",&n,&m);

    ll i,x,y,z,j;

    for(i=1;i<=n;i++){

        scanf("%lld",&val[i]);

        for(j=1;j<=n;j++)

            dp[i][j]=INF;

    }

    for(i=1;i<=m;i++){

        scanf("%lld %lld %lld",&x,&y,&z);

        V[x].push_back(y);

        V[y].push_back(x);

        C[x].push_back(z);

        C[y].push_back(z);

    }

}

void process(){

    ll from,minv,to,i;

    dp[1][1]=0;

    Q.push(make_pair(0,make_pair(1,1)));

    while(!Q.empty()){

        from=Q.top().second.first;

        minv=Q.top().second.second;Q.pop();

        if(visit[from][minv]==1)

            continue;

        visit[from][minv]=1;

        for(i=0;i<V[from].size();i++){

            to=V[from][i];

            if(dp[to][(val[minv]>val[to])? to:minv]>dp[from][minv]+val[minv]*C[from][i]){

                dp[to][(val[minv]>val[to]?to:minv)]=dp[from][minv]+val[minv]*C[from][i];

                Q.push(make_pair(dp[to][(val[minv]>val[to]?to:minv)],make_pair(to,(val[minv]>val[to]?to:minv))));

            }

        }

    }

}

void output(){

    ll mn=INF,i;

    for(i=1;i<=n;i++)

        mn=min(mn,dp[n][i]);

    printf("%lld",mn);

}

int main(){

    input();

    process();

    output();

    return 0;

}

비슷한 문제 유형으로는
Prob No.05C6 : 목초지 최소 이동 시간 [CH03.4.USACO(Gold)]
http://koistudy.net/?mid=prob_page&NO=1478 가 있다. 추후 업데이트 예정