[BOJ] 1162 : Revamping Trails

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

---

다익스트라 그래프 그래프이론

 1번 노드에서 시작해서 N번 노드까지 가는 최단 거리를 찾는 문제인데, K개 만큼의 길을 이동 거리(cost)를 0으로 만들 수 있는 상황에서의 최단 거리를 찾는 문제입니다.

 출발 노드가 정해져있으므로 다익스트라 알고리즘을 이용하고 몇 개의 길을 cost를 0으로 만들었는지에 따라 최단거리가 달라지므로, dist배열을 2차원 배열로 다음과 같이 정의하면 된다.

 

●  dist[M][K] := K개 만큼의 길을 0으로 만들어서 1번 정점에서 시작해서 M번 정점까지 이동한 최단 거리.

 

주의할 점 : 최단 거리가 int 형 범위를 벗어난다.

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

const long long INF = 10000000001;
int N, M, K;
long long dist[10001][21];
vector<pair<int, int>> map[10001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M >> K;
	for (int i = 0, x, y, z; i < M; i++) {
		cin >> x >> y >> z;
		map[x].push_back({ y, z });
		map[y].push_back({ x, z });
	}
	memset(dist, INF, sizeof(dist));
	priority_queue<pair<long long, pair<int, int>>> pq;
	pq.push({ 0, { 0, 1 } });
	for (int i = 0; i <= K; i++)
		dist[1][i] = 0;

	while (!pq.empty()) {
		long long cost = -pq.top().first;
		int road = pq.top().second.first;
		int cur = pq.top().second.second;
		pq.pop();
		if (dist[cur][road] < cost) continue;
		for (int i = 0; i < map[cur].size(); i++) {
			int next = map[cur][i].first;
			long long nextDist = cost + map[cur][i].second;
			// 현재 정점
			if (nextDist < dist[next][road]) {
				dist[next][road] = nextDist;
				pq.push({ -nextDist, {road, next} });
			}
			// 포장하고 진행
			nextDist = cost;
			if (road < K && nextDist < dist[next][road + 1]) {
				dist[next][road + 1] = nextDist;
				pq.push({ -nextDist, {road + 1, next} });
			}
		}
	}
	cout << dist[N][K] << '\n';
	return 0;
}

---