백준 1162 도로포장

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

1162번: 도로포장

 

양수 weight의 간선으로 이루어진 그래프에서

한 점으로부터 다른 점까지의 최단거리를 구하는 알고리즘은 다익스트라알고리즘이다. 

 

이 문제는 여기서 한 술 더 뜬다.

내가 원하는 간선의 weight를 0으로 만들 수 있다! 이것만 잘 생각하면 일반적인 다익스트라 문제와 똑같다.

 

N개 중에 K개를 고르는 문제는 어떻게 풀어야할까?

 

N개 중에 K개를 고르는 모든 경우의 수를 구할 수도 있다. 즉 next_permutation 함수를 활용할 수도 있다.

하지만 각 경우가 나뉠 때 Recursion을 활용할 수도 있다.

 

이 문제는 함수 자체를 다시 호출하지는 않지만 Priority queue의 while문 안에서 현재 간선을 0 으로 만드는 것과 현재 간선의 weight를 유지하는 것을 비교한다

 

/* 도로포장 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

#define INF 2100000000
#define ll long long int

struct node {
public:
	ll num, cost, cnt;
	
	node(ll num, ll cost, ll cnt) {
		this->num = num; 
		this->cost = cost; 
		this->cnt = cnt;
	}
	bool operator < (const node n) const {
		return n.cost < cost;
	}
};

using namespace std;

int N, M, K;
ll dist[10001][21];
vector<pair<int,int>> edge[10000 + 1];

void input();
void solve();
void dijkstra(int src);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	input();
	solve();

	return 0;
}

void dijkstra(int src) {
	priority_queue<node>  pq;

	pq.push({ src, 0, 0 });

	while (!pq.empty()) {

		ll cst = pq.top().cost;
		ll num = pq.top().num;
		ll cnt = pq.top().cnt;
		pq.pop();

		if (cst > dist[num][cnt]) continue;

		for (auto conn_node : edge[num]) {
			ll nxt_node = conn_node.first;
			ll nxt_cost = conn_node.second + cst;

			if (nxt_cost < dist[nxt_node][cnt]) {
				dist[nxt_node][cnt] = nxt_cost;
				pq.push({ nxt_node, nxt_cost, cnt });
			}

			if (cnt < K && cst < dist[nxt_node][cnt+1]) {
				dist[nxt_node][cnt + 1] = cst;
				pq.push({ nxt_node, cst, cnt + 1 });
			}
		}
	}
}

void input() {
	cin >> N >> M >> K;

	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		edge[a].push_back({ b,c });
		edge[b].push_back({ a,c });
	}
}

void solve() {
	memset(dist, 0x7F, sizeof(dist));
	// K개 만큼 포장을 할 수 있다.
	dist[1][0] = 0;
	dijkstra(1);
	ll maxi = 1e18;
	for (int i = 0; i <= K; i++) {
		maxi = min(maxi, dist[N][i]);
	}
	cout << maxi << '\n';
}