[1162번] 도로포장

문제 출처 :

https://www.acmicpc.net/problem/1162

알고리즘 분석 :

문제 해결에 필요한 사항

1. 다익스트라 알고리즘 :: http://www.crocus.co.kr/546

2. 다익스트라 응용

우선순위 큐 기반 다익스트라 알고리즘을 이용하여 문제를 해결 할 수 있다.

이전에 기본적으로 이용하던 다익스트라 알고리즘과 다른 부분은 dist가 2차원 배열로 변했는 것이고

이 dist 2차원 배열의 2번째 차수에는 cnt에 대한 정보를 넣어둔다.

우선순위 큐에서 push하는 조건은

1. cnt가 0보다 큰 경우 dist[there][cnt-1](there,cnt-1까지 최단 거리)이 cost(here까지 최단 거리)보다 크다면

dist[there][cnt-1]의 최단 거리를 cost(here까지 최단 거리)로 갱신시켜 버린다. 

즉, here->there의 길을 도로 포장을 통해 0으로 길을 만들어 버리는 과정이다.(단, cnt > 0이어야 한다.)

2. 일반적인 우선순위 큐에 쌓는 경우(도로포장을 할 수 없는 경우)

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
 
#define min(a,b)(a < b ? a : b)
#define INF 987654321
 
using namespace std;
 
typedef long long ll;
 
typedef struct _INFO_
{
    ll val;
    int to;
    int k;
}INFO;
 
struct cmp
{
    bool operator()(INFO a, INFO b)
    {
        return a.val > b.val;
    }
};
 
typedef pair<ll, ll> pll;
 
vector<pll> vc[10001];
ll dist[10001][21];
 
int V, E, k;
 
void dijkstra(int src)
{
    for (int i = 0; i < 10001; i++)
        for (int j = 0; j < 21; j++)
            dist[i][j] = INF;
 
    dist[src][k] = 0;
 
    priority_queue<INFO, vector<INFO>, cmp> pq;
 
    pq.push(INFO{ 0,src,k });
 
    while (!pq.empty())
    {
        ll cost = pq.top().val;
        int here = pq.top().to;
        int cnt = pq.top().k;
 
        pq.pop();
 
        if (dist[here][cnt] < cost)
            continue;
 
        for (int i = 0; i < vc[here].size(); i++)
        {
            int there = vc[here][i].first;
            ll thereCost = cost + vc[here][i].second;
 
            // there,cnt-1의 최단 거리가 현재 최단 거리보다 크면
            // 도로 포장을 해버려서 there의 최단 거리를 here의 최단거리와 같도록
            if (cnt > 0 && dist[there][cnt - 1] > cost)
            {
                dist[there][cnt - 1] = cost;
                pq.push(INFO{ cost, there, cnt - 1 });
            }
 
            // there,cnt의 최단 거리가 현재 최단 거리 + there 가중치보다 크면
            if (dist[there][cnt] > thereCost)
            {
                dist[there][cnt] = thereCost;
                pq.push(INFO{ thereCost, there, cnt});
            }
        }
    }
 
}
int main()
{
 
    scanf("%d %d %d", &V, &E, &k);
 
    V++;
 
    for (int i = 0; i < E; i++)
    {
        int from, to, val;
        scanf("%d %d %d", &from, &to, &val);
 
        vc[from].push_back(pll(to, val));
        vc[to].push_back(pll(from, val));
    }
 
    dijkstra(1);
 
    ll get = INF;
    for (int i = 0; i <= k; i++)
        get = min(get, dist[V-1][i]);
 
    printf("%lld", get);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>