[BOJ/Gold 1] 백준 1884 고속도로(C++)

문제 링크

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

1884번: 고속도로

 

문제

봄캠프 기간 동안 고속도로의 통행료가 급격하게 올라, 참가자들이 자칫 집으로 돌아가지 못할 수도 있는 위기에 봉착했다! 통행료가 인하되기 전까지는 여기 속초에서 원쌤과 함께 계속 프로그래밍 공부를 해야 할 수도 있는 상황인 것이다! 이 모든 것은 귀가시에 사용할 교통비를, 고속도로 통행료가 오르기 전에 계산해서 들고 왔기 때문이다.

다급해진 여러분은 정해진 예산을 가지고 집으로 돌아갈 수 있을지 알아보고, 갈 수 있다면 그에 필요한 최단 이동거리를 계산하려고 한다. 이를 해결하기 위한 프로그램을 작성하라.

입력

첫 줄에 여러분이 준비해 둔 교통비 K가 주어진다. (0≤K≤10,000) 둘째 줄과 셋째 줄에는 각각 도시의 숫자 N과 도로의 숫자 R이 주어진다. (2≤N≤100, 1≤R≤10,000) 이후 R개의 줄에 각 도로의 정보가 주어지는데, 각 줄은 네 개의 숫자 s, d, l, t로 이루어져 있다. s는 도로의 출발 도시 번호이고, d는 도로의 도착 도시 번호이다. l은 도로의 길이이고, t는 도로의 통행료이다. (1≤s≤N, 1≤d≤N, 1≤l≤100, 0≤t≤100)

도시의 번호는 1번부터 N번까지 빠짐없이 붙어 있다. 이곳 속초는 1번 도시이고, 여러분의 집은 N번 도시에 있다. 각 도로는 일방통행로이다. 서로 다른 두 도로가 서로 같은 시작 도시와 서로 같은 도착 도시를 가질 수 있음에 유의하라.

출력

첫 줄에 정해진 예산 내에서 이용할 수 있는 경로 중 제일 짧은 것의 길이를 출력한다. 만약 가능한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1

5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

예제 출력 1

11

예제 입력 2

0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0

예제 출력 2

-1

알고리즘 분류

• 최단 거리 알고리즘

풀이

A에 도착해서 남은 교통비가 B일 때의 최단 거리를 기록하는 Cost[A][B] 2차원 배열을 선언해서 1번 정점을 시작점으로 잡고 다익스트라를 1번 수행해준다. 그리고 교통비가 0~K일 때 최단 거리의 최솟값을 구해준다.

그냥 골드2 다익스트라 문제들이랑 비슷해 보이는데 왜 골드1인지는 모르겠다.(근데 단방향인 거를 양방향 도로인 줄 알고 계속 틀렸다)

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX_N 101
#define MAX_K 10001
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	int Dest, Dist, Cost;
};

struct COMP {
	bool operator()(INFO A, INFO B) {
		return (A.Dist > B.Dist);
	}
};

int K, N, R;
vector<INFO> Edge[MAX_N];
int Cost[MAX_N][MAX_K];
int answer = INF;

void Input() {
	cin >> K;
	cin >> N;
	cin >> R;
	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			Cost[i][j] = INF;
		}
	}
	for (int i = 0; i < R; i++) {
		int S, D, L, T;
		cin >> S >> D >> L >> T;
		Edge[S].push_back({ D,L,T });
	}
}

void Dijkstra() {
	priority_queue<INFO, vector<INFO>, COMP> PQ;
	PQ.push({ 1,0,K });

	while (!PQ.empty()) {
		int CurD = PQ.top().Dist;
		int CurC = PQ.top().Cost;
		int CurX = PQ.top().Dest;
		PQ.pop();

		if (Cost[CurX][CurC] < CurD) {
			continue;
		}

		for (int i = 0; i < Edge[CurX].size(); i++) {
			int nextD = Edge[CurX][i].Dist;
			int nextC = Edge[CurX][i].Cost;
			int nextX = Edge[CurX][i].Dest;
			if (CurC < nextC) {
				continue;
			}
			if (Cost[nextX][CurC - nextC] > CurD + nextD) {
				Cost[nextX][CurC - nextC] = CurD + nextD;
				PQ.push({ nextX, Cost[nextX][CurC - nextC], CurC - nextC });
			}
		}
	};
}

void Find_Answer() {
	for (int i = 0; i <= K; i++) {
		answer = min(answer, Cost[N][i]);
	}
	if (answer == INF) {
		cout << -1 << "\n";
	}
	else {
		cout << answer << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Dijkstra();
	Find_Answer();

	return 0;
}