백준 1884 - 고속도로(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1884

1884번: 고속도로

다익스트라를 이용한 문제입니다.

제한된 비용 안으로 목적지까지 가려고 할 때, 최소 거리를 구하는 문제입니다.

여기서 생각해볼 것은, 같은 정점이라도 다른 비용으로 방문할 수 있습니다.
그렇다면 항상 적은 비용으로 도달하는 경우가 최고의 경우이냐 하면 그건 아닙니다.
따라서, 같은 정점이라도 다른 비용으로 도착할 경우를 생각해, 2차원 배열을 이용해 모든 경우를 저장해야 합니다.
저는 [N][K]배열을 통해 X번 정점에 오고 비용이 K인 경우, 최소 거리를 저장했습니다.

하나만 더 생각을 해보자면, X번 정점에 4의 비용으로 1이라는 거리를 지나왔다고 가정하겠습니다.
그리고, 10이란 비용으로 5의 거리를 온 경우가 있습니다.
그렇다면, 해당 경우를 확인할 필요가 있냐? 하면 그럴 필요가 없습니다. 이미, 첫번째 경우가 나온 경우 중 최고의 경우이기 때문입니다.

따라서, X번 정점에 Y의 비용으로 Z의 거리를 왔다고 했을 때, 해당 비용인 Y부터 마지막 비용인 K까지 거리를 비교해,
Z의 값보다 큰 값들은 전부 Z로 바꿔주면 됩니다. 이미 이전 비용의 경우가 최선이기 때문입니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF INT_MAX
#define F first
#define S second

using namespace std;

int K, N, R;
vector<pair<int, pair<int, int>>> connect[101]; //정점, 길이, 비용
int Distance[101][10001]; // 정점, 길이
priority_queue<pair<int, pair<int, int>>> q; //길이, 비용, 정점

void reset_distance(){
	for(int i = 1; i <= N; i++){
		for(int j = 0; j <= K; j++){
			Distance[i][j] = INF;
		}
	}
}

void Dijstra(){
	q.push({-0, {0, 1}});
	Distance[1][0] = 0;
	while(!q.empty()){
		int x = q.top().S.S;
		int cost = q.top().S.F;
		int Len = -q.top().F;
		q.pop();
		if(Distance[x][cost] < Len) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			int n_cost = cost + connect[x][i].S.S;
			int n_Len = Len + connect[x][i].S.F;
			if(n_cost > K) continue;
			if(Distance[xx][n_cost] > n_Len){
				for(int j = n_cost; j <= K; j++){
					if(Distance[xx][j] <= n_Len) break;
					Distance[xx][j] = n_Len;
				}
				q.push({-Distance[xx][n_cost], {n_cost, xx}});
			}
		}
	}	
}

void solve(){
	reset_distance();
	Dijstra();
	int ans = INF;
	for(int i = 0; i <= K; i++){
		ans = min(ans, Distance[N][i]);
	}
	if(ans == INF) cout << "-1";
	else cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> K >> N >> R;
	for(int i = 1; i <= R; i++){
		int x, y, len, cost;
		scanf("%d %d %d %d", &x, &y, &len, &cost);
		connect[x].push_back({y, {len, cost}});
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.