1162 - 도로포장

문제 링크: https://www.boj.kr/1162 

1162번: 도로포장

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128MB	5133	659	456	22.072%

문제

준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 k개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.

문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로릉 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 또한 편의상 서울은 반드시 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.

입력

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.

출력

첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

예제 입력 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

예제 출력 1

1

C++ code

#include <stdio.h>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;
const ll inf = LLONG_MAX;

typedef struct
{
	vector<int> to, cost;
}Road;

typedef struct
{
	ll city, cost, kk;
}pq_elem;

bool operator<(pq_elem x, pq_elem y)
{
	return x.cost > y.cost;
}

int main(void)
{
	int n, m, k, size;
    vector<Road> road;
    vector<vector<ll>> ans;
    priority_queue<pq_elem, vector<pq_elem>> pq;
    
    scanf("%d %d %d", &n, &m, &k);
    road.resize(n+1);
    ans.resize(n+1, vector<ll>(k+1, inf));
    
    for (int i = 0; i < m; i++)
    {
    	int s, e, c;
        scanf("%d %d %d", &s, &e, &c);
        road[s].to.push_back(e);
        road[s].cost.push_back(c);
        road[e].to.push_back(s);
        road[e].cost.push_back(c);
    }
    
    pq.push(pq_elem{1, 0, 0});
    ans[1][0] = 0;
    
    while (pq.size())
    {
    	ll city = pq.top().city, cost = pq.top().cost, kk = pq.top().kk;
        pq.pop();
        
        size = road[city].to.size();
        for (int i = 0; i < size; i++)
        {
        	pq_elem temp;
            temp.city = road[city].to[i];
            temp.cost = cost + road[city].cost[i];
            temp.kk = kk;
            
            if (ans[temp.city][temp.kk] > temp.cost)
            {
            	ans[temp.city][temp.kk] = temp.cost;
                pq.push(temp);
            }
            
            temp.cost = cost;
            temp.kk++;
            if (temp.kk <= k && ans[temp.city][temp.kk] > temp.cost)
            {
            	ans[temp.city][temp.kk] = temp.cost;
                pq.push(temp);
            }
        }
    }
    
    ll minans = ans[n][0];
    for (int i = 1; i <= k; i++)
    	minans = min(minans, ans[n][i]);
    
    printf("%lld\n", minans);
    return 0;
}