[BOJ/Gold 3] 백준 16167 A Great Way(C++)

문제 링크

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

16167번: A Great Way

 

문제

정우는 대회 준비를 위해 중앙대학교에서 숭실대학교까지 가려 한다. 그런데 중앙대학교에서 숭실대학교까지 가기 위해서는 몇 개의 거점을 지나쳐야 한다. 각 거점을 경유할 시 발생하는 10분간 기본요금과 1분당 추가요금은 모두 다르다. 정우는 숭실대학교까지 가장 적은 비용을 사용해서 도착하려 한다. 정우를 위하여 중앙대학교에서 숭실대학교까지 가는 최소 비용과 거쳐야 하는 거점의 수를 알아내는 프로그램을 작성하자.

입력

첫 번째 줄에 거점의 수 N과 경로의 개수 R이 주어진다. (2 ≤ N ≤ 100, 1 ≤ R ≤ 200) 모든 거점에는 1부터 N까지 번호가 매겨져 있으며 중앙대학교는 1번, 숭실대학교는 N번이다. 두 번째 줄부터는 R개의 줄에 걸쳐 각 경로에 대한 정보 (a, b, c, d, e)가 순서대로 주어진다. a는 시작 거점, b는 도착 거점, c는 기본요금, d는 1분당 추가요금, e는 걸리는 시간이다. (1 ≤ a, b ≤ 100, 1 ≤ c, d, e ≤ 100) 단, c, d, e는 정수이다.

출력

첫 번째 줄에 최소 비용과 거쳐야 하는 거점의 수를 차례대로 출력한다. 중앙대학교부터 숭실대학교까지 도착할 방법이 없을 경우에는 'It is not a great way.'를 출력한다. 단, 최소 비용 경로가 여러 가지 존재하면 거점의 수를 최소화하여 출력해야 한다.

예제 입력 1

3 3
1 2 3 1 12
1 3 5 2 20
2 3 3 2 8

예제 출력 1

8 3

예제 입력 2

4 2
1 2 5 2 11
2 3 8 1 21

예제 출력 2

It is not a great way.

알고리즘 분류

• 최단 거리 알고리즘

풀이

N까지의 최단 거리를 구하기 위해 다익스트라를 사용한다.

다익스트라를 사용하는 와중에 N까지 오는 데 지나친 거점의 개수를 기록해준다.

코드

#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 101
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	int Cost, X, Vertex;
};

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

int N, R;
vector<pair<int, int> > Edge[MAX];
int Prev[MAX];
int Cost[MAX];

void Input() {
	cin >> N >> R;
	for (int i = 1; i <= N; i++) {
		Cost[i] = INF;
		Prev[i] = INF;
	}
	for (int i = 0; i < R; i++) {
		int A, B, C, D, E;
		cin >> A >> B >> C >> D >> E;
		if (E <= 10) {
			Edge[A].push_back(make_pair(B, C));
		}
		else {
			int Fee = C + (E - 10) * D;
			Edge[A].push_back(make_pair(B, Fee));
		}
	}
}

void Dijkstra() {
	priority_queue<INFO ,vector<INFO>, COMP> PQ;
	Cost[1] = 0;
	PQ.push({ 0,1,1 });

	while (!PQ.empty()) {
		int CurCost = PQ.top().Cost;
		int CurX = PQ.top().X;
		int CurVertex = PQ.top().Vertex;
		PQ.pop();

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

		for (int i = 0; i < Edge[CurX].size(); i++) {
			int nextCost = Edge[CurX][i].second;
			int nextX = Edge[CurX][i].first;
			if (Cost[nextX] > CurCost + nextCost) {
				Cost[nextX] = CurCost + nextCost;
				Prev[nextX] = CurVertex + 1;
				PQ.push({ Cost[nextX],nextX,CurVertex + 1 });
			}
			else if (Cost[nextX] == CurCost + nextCost) {
				Prev[nextX] = min(Prev[nextX], CurVertex + 1);
			}
		}
	};
}

void Find_Answer() {
	if (Cost[N] == INF) {
		cout << "It is not a great way.\n";
	}
	else {
		cout << Cost[N] << " " << Prev[N] << "\n";
	}
}

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

	return 0;
}