코드 복사/붙여넣기 하는 당신이 아름답습니다.

1162 : 도로포장

풀이

dp[노드번호i][포장갯수k]로 놓고 다익스트라를 돌리자!

원래 다익스트라에서 사용하던 dist[i]대신 dp[i][j]를 참조하면서 돌면 된다.

now.dst는 지금까지 누적해 온 dst값이고, nxt.dst는 노드 사이의 거리(가중치)이다.

코드

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int n_ = 10000 + 1;

struct edg {
	int idx, dst, cnt;
	edg() {}
	edg(int idx, int dst) : idx(idx), dst(dst) {}
	edg(int idx, int dst, int cnt) : idx(idx), dst(dst), cnt(cnt) {}
	bool operator <(edg A)const { return dst > A.dst; }
};

int n, m, k;
int dst[n_][21];
vector<edg> gph[n_];

void dijkstra() {
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= k; ++j) dst[i][j] = 987654321;
	dst[1][k] = 0;

	priority_queue<edg> pq;
	pq.push(edg(1, 0, k));

	while (!pq.empty()) {
		edg now = pq.top();
		pq.pop();

		if (now.dst != dst[now.idx][now.cnt]) continue;

		for (auto nxt : gph[now.idx]) {
			if (dst[nxt.idx][now.cnt] > now.dst + nxt.dst) {
				dst[nxt.idx][now.cnt] = now.dst + nxt.dst;
				pq.push(edg(nxt.idx, dst[nxt.idx][now.cnt], now.cnt));
			}
			if (now.cnt > 0) {
				if (dst[nxt.idx][now.cnt - 1] > now.dst) {
					dst[nxt.idx][now.cnt - 1] = now.dst;
					pq.push(edg(nxt.idx, now.dst, now.cnt - 1));
				}
			}
		}
	}
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 0; i < m; ++i) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		gph[x].push_back(edg(y, z));
		gph[y].push_back(edg(x, z));
	}

	dijkstra();

	int ans = 999999999;
	for (int i = 0; i <= k; ++i) ans = min(ans, dst[n][i]);

	printf("%d", ans);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-02-17 23:55

Read more posts by this author