[BOJ 16167 // C++] A Great Way

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16167번 문제인 A Great Way이다.
문제는 아래 링크를 확인하자.

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

16167번: A Great Way

주어진 문제의 상황은 가중치와 방향이 있는 간선으로 이루어진 그래프로 모델링할 수 있다.

 

또한 주어진 문제를 해결하는 것은 위와 같이 모델링한 그래프 위에서의 1번 노드에서 N번 노드까지의 최소비용 경로의 그 비용과 해당 경로가 가질 수 있는 가장 적은 노드의 개수를 구하는 문제를 해결하는 것과 같아진다.

 

dijkstra 알고리즘을 이용해 문제를 해결해주자. 이 때 가중치의 기준은 일반적인 dijkstra와 같이 비용으로 하되 두 번째 기준으로 해당 노드까지 (가장 적은 비용으로) 도달하는 데에 필요한 노드의 개수로 삼아 문제를 해결하자.

 

아래는 제출한 소스코드이다.

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

int N, E;
vector<pair<int,int>> G[101]; // {노드, 거리}
pair<int, int> dist[101];

void dijkstra() {
	dist[1] = { 0,1 };
	priority_queue<pair<pair<int, int>,int>> pq; // {{-거리, -노드수},노드}
	pq.push(make_pair(make_pair(0, -1), 1));

	while (!pq.empty()) {
		int d = -pq.top().first.first, cnt = -pq.top().first.second, cur = pq.top().second; pq.pop();
		if (dist[cur] < make_pair(d, cnt)) continue;
		for (auto& p : G[cur]) {
			int nxt = p.first, dd = d + p.second;
			if (dist[nxt] == make_pair(0, 0) || make_pair(dd, cnt + 1) < dist[nxt]) {
				dist[nxt] = make_pair(dd, cnt + 1);
				pq.push(make_pair(make_pair(-dd, -(cnt + 1)), nxt));
			}
		}
	}
}

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

	cin >> N >> E;
	while (E--) {
		int a, b, c, d, e; cin >> a >> b >> c >> d >> e;
		int t;
		if (e < 10) t = c;
		else t = c + d * (e - 10);
		G[a].emplace_back(make_pair(b, t));
	}

	dijkstra();

	if (dist[N] == make_pair(0, 0)) cout << "It is not a great way.";
	else cout << dist[N].first << ' ' << dist[N].second;
}