[BOJ 25636 // C++] 소방차

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

 

이번에 볼 문제는 백준 25636번 문제인 소방차이다.
문제는 아래 링크를 확인하자.

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

25636번: 소방차

교차로 S에서 T로 이동하는 최단경로 중 물을 가장 많이 실을 수 있는 경로를 찾는 문제이다.

 

일반적인 dijkstra 알고리즘에서의 탐색 순서의 우선순위를 (도달 거리가 짧은 순)으로 잡는 것을 변형하여 우선순위를 (도달거리가 짧으면서, 같은 도달거리면 물을 더 많이 길은)과 같이 설정해 문제를 해결할 수 있다. 이는 아래의 구현으로 확인할 수 있다.

 

또는, 단순히 dijkstra 알고리즘만을 우선 이용하여 S에서 각 노드로 갈 수 있는 최단경로를 구성하는 에지의 모음으로 새로운 DAG를 구성 후, 그 위에서 각 노드까지 물의 이동량의 최댓값을 다시 계산해 문제를 해결할 수도 있다.

 

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

int N, M, S, T;
ll water[100001];
ll dist[100001];
ll storedwater[100001];
vector<pair<int, ll>> G[100001]; // {노드번호, 거리}

priority_queue<pair<pair<ll, ll>, int>> pq; // {{-거리,물양},노드번호}
void dijkstra() {
	for (int i = 1; i <= N; i++) dist[i] = 1000000000000000007LL;
	dist[S] = 0, storedwater[S] = water[S];
	pq.push(make_pair(make_pair(0, water[S]), S));

	while (!pq.empty()) {
		ll d = -pq.top().first.first, w = pq.top().first.second; int cur = pq.top().second; pq.pop();
		if ((dist[cur] < d) || ((dist[cur] == d) && (storedwater[cur] < w))) continue;
		for (auto& p : G[cur]) {
			int node = p.first; ll dd = p.second;
			ll dtmp = d + dd, wtmp = w + water[node];
			if (dist[node] > dtmp || ((dist[node] == dtmp) && (storedwater[node] < wtmp))) {
				dist[node] = dtmp, storedwater[node] = wtmp;
				pq.push(make_pair(make_pair(-dtmp, wtmp), node));
			}
		}
	}
}

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> water[i];
	cin >> M;
	while (M--) {
		int u, v, w; cin >> u >> v >> w;
		G[u].emplace_back(make_pair(v, w));
		G[v].emplace_back(make_pair(u, w));
	}
	cin >> S >> T;

	dijkstra();

	if (dist[T] == 1000000000000000007LL) cout << -1;
	else cout << dist[T] << ' ' << storedwater[T];
}