백준 도로 포장 [c++]
1162 도로포장 플레티넘 5
문제
준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 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개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.
풀이
DP에 다익스트라가 적용된 문제.
도로 중 최소거리를 구하는데, 포장(한 도로를 0으로 만듦)을 k번 이하로 해서 가능한 최소거리를 구하는 문제로, 그래프의 최소거리를 구하는데 다익스트라를 이용한다.
만약 포장이 없었다면, 일차원배열 cost만으로 계산할 수 있다.
그런데 최대 k번, k이하로 포장할 수 있으므로 이차원 배열을 이용해 포장을 k번했을때, 해당 위치의 최소거리를 저장해나간다.
BFS를 이용해 priority_queue에 넣어가며 계산할 수 있다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 987654321987654321
vector< vector<pair<int, int> > > load;
long long costs[10001][21];
int n, m, k;
void dijkstra(){
for(int i = 0; i < 10001; i++)
{
for(int j = 0; j < 21; j++)
{
costs[i][j] = INF;
}
}
priority_queue<pair<long long, pair<int, int> > > pq;
pq.push(make_pair(0,make_pair(1,0)));
costs[1][0] = 0;
while(!pq.empty())
{
int Pos = pq.top().second.first;
int cnt = pq.top().second.second;
long long cost = -1 * pq.top().first;
pq.pop();
if(costs[Pos][cnt] < cost){
continue;
}
for(int i = 0; i < load[Pos].size(); i++)
{
int nPos = load[Pos][i].first;
long long nCost = cost + load[Pos][i].second;
if(costs[nPos][cnt] > nCost){
costs[nPos][cnt] = nCost;
pq.push(make_pair(-1 * nCost, make_pair(nPos, cnt)));
}
if(costs[nPos][cnt + 1] > cost && cnt + 1 <= k){
costs[nPos][cnt + 1] = cost;
pq.push(make_pair(-1 * cost, make_pair(nPos, cnt + 1)));
}
}
}
}
int main(){
cin >> n >> m >> k;
load.resize(n+1);
for(int i = 0; i < m; i++)
{
int s, e, cost;
cin >> s >> e >> cost;
load[s].push_back(make_pair(e, cost));
load[e].push_back(make_pair(s, cost));
}
long long minCost = INF;
dijkstra();
for(int i = 0; i <= k; i++)
{
minCost = min(minCost, costs[n][i]);
}
cout << minCost << endl;
return 0;
}