[BAEKJOON] 1162번 도로포장

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

문제조건

1.  N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장
2. 포장하게 되면 도로를 지나는데 걸리는 시간이 0
3. 서울은 1번 도시, 포천은 N번 도시
4.  K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간은?

접근방법

 

가중치가 있는 그래프에서 특정지점에서 시작해서 다른지점까지의 최단거리를 구하는 알고리즘인 다익스트라가 떠올랐다. 사실 이 문제는 푸는것 자체는 크게 어렵지 않았다. 다익스트라 알고리즘 자체가 dp를 기반으로 이때까지 계산된 거리와 새로운 거리를 비교해서 계속해서 기록하는 구조이므로, 엄청나게 큰값이 들어 갈수 있기때문엥 21억이 넘는 수 까지 처리해주기 위해서 long long형을 사용했다. 그리고 시간복잡도를 O(n^2)에서 O(n log n)으로 줄이기 위해 우선순위큐를 사용했고, dist배열도 이차원으로 선언해서 포장을 한경우 / 안한 경우 를 나누고, 포장개수에 따라 어떤 것이 가장 작은 값인지 모르므로, for문을 돌면서 최솟값을 갱신했다.

 

소스코드

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#define MAX 10001
using namespace std;
typedef long long ll;

struct edge {
	ll weight;
	ll city;
	ll pojang;
	bool operator<(const edge& a) const {
		return weight > a.weight;
	}
};

int n, m, k;
vector<pair<ll, ll> > v[MAX];
ll dist[MAX][21];
ll res;

void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	res = INT64_MAX;
	priority_queue<edge> pq;
	pq.push({ 0,1,0 });
	dist[1][0] = 0;
	while (!pq.empty()) {
		ll city = pq.top().city;
		ll time = pq.top().weight;
		ll pojang = pq.top().pojang;
		pq.pop();
		// 거쳐가는 경로 vs 바로가는 경로비교
		if (dist[city][pojang] < time) continue;
		for (auto target : v[city]) {
			ll nxt = target.second;
			ll nxtT = time + target.first;
			// 길을 포장하지 않은경우
			if (nxtT < dist[nxt][pojang]) {
				pq.push({ nxtT, nxt, pojang });
				dist[nxt][pojang] = nxtT;
			}

			// 길을 포장한 경우
			if (pojang < k && time < dist[nxt][pojang + 1]) {
				pq.push({ time, nxt, pojang + 1 });
				dist[nxt][pojang + 1] = time;
			}
		}
	}

	for (int i = 0; i <= k; i++) res = min(res, dist[n][i]);
}

int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int a, b, t;
		cin >> a >> b >> t;
		v[a].push_back({ t,b });
		v[b].push_back({ t,a });
	}
	dijkstra();
	cout << res;
}

 

여기서 계속 틀렸던 이유는 다익스트라를 진행하면서 최댓값 설정을 잘못해줬기 때문인데, 나는 0x3f로 설정해줬다.

0x3f면 뭘까? 사실 memset과 함께 0x3f 혹은 0x7f를 많이 사용한다. 0x3f의 경우1061109567의 값을 가지는데 이걸 이진수로 변환하면 00111111 00111111 00111111 00111111 이고, 16진수로 변환하면 0x3f이다.

아무튼 다익스트라 문제가 나오면 memset을 쓸거면 0x3f로 초기화하는 방법을 다른 문제를 만났을때 써봐야겠다.