[G2] 백준 16227번 의약품 수송 C++ 다익스트라

리뷰

 

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

0번 노드부터 n + 1번 노드까지 이동하는 최단 시간을 구하는 문제, 모래를 씻어야 한다는 제약 조건이 추가된 최단 경로 문제이다.

 

 

전역 변수

• N : 최대 노드의 개수를 정의할 상수 변수
• n : 특수 장비의 개수, 즉 출발지와 도착지를 제외한 노드의 개수를 저장할 변수
• k : 포장 도로의 개수, 즉 간선의 개수를 저장할 변수
• Edge : 간선 정보, 이동할 노드와 가중치를 정의할 구조체
• edges : 간선 정보를 저장할 Edge타입 벡터 배열
• Pos : 이동 정보, 현재 노드와 누적 가중치, 누적 모래를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

int dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 0, 0, 0 });
	vector<int> dist(n + 2, 2e9);
	dist[0] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cv = pos.cv, cs = pos.cs;
		if (dist[cn] < cv) continue;
		if (cn == n + 1) return cv;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv, ns = cs + edge.nv;
			if (ns > 100) {
				nv += 5;
				ns = edge.nv;
			}

			if (dist[nn] > nv) {
				dist[nn] = nv;
				pq.push({ nn, nv, ns });
			}
		}
	}
	return -1;
}

 

다익스트라를 통해 0번 노드에서 n + 1번 노드까지 이동에 걸리는 최단 시간을 구하는 함수

 

문제풀이

1. n, k값을 입력 받고, k개의 간선을 edges배열에 양방향으로 추가하고, dijkstra함수를 호출해 준다.
2. Pos타입의 우선순위 큐 pq를 초기화 하고, 초기 노드 0, 가중치 0, 모래 0을 push해준다.
3. n + 2크기의 정수형 벡터 dist를 매우 큰 값을 초기값으로 저장해준다.
4. 0번 노드의 dist값을 0으로 저장해 준다.
5. pq가 빌 때까지 while 루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
6. 변수 cn, cv, cs에 현재 노드, 누적 가중치, 누적 모래양을 파싱하여 저장해 준다.
7. 첫 번째 기저조건으로 dist[cn]이 cv보다 작을경우 더 최적값이 있는 것이므로 continue처리해 준다.
8. 두 번째 기저조건으로 cn이 n + 1일경우 cv에 저장된 값을 리턴해 준다.
9. cn의 인접리스트를 순회하며 이동할 노드를 nn에, 가중치를 cv와 cs에 더해준 값을 변수 nv, ns에 저장해 준다.
10. 만약 ns가 100보다 클 경우 nv에 5를 추가로 더해주고, ns는 간선의 가중치로 변경해 준다.
11. dist[nn]이 nv보다 클 경우 dist[nn]을 nv로, pq에 nn, nv, ns를 push해준다.
12. 두 번째 기저조건이 실행되어 리턴된 값을 출력해 준다.

 

트러블 슈팅

1. ns를 cv + nv로 정의했었다, nv가 아닌 간선의 가중치인 edge.nv로 저장해 주었다.
2. ns가 100보다 클 경우 ns를 0으로 초기화 해주었다, ns를 edge.nv로 저장해 주었다.
3. 위 두 조건을 수정하고 난 뒤 제출하니 AC를 받았다.

 

참고 사항

1. 차량은 최대 100분간 씻지 않고 주행할 수 있으므로 c가 100보다 클 경우 인접리스트에 추가할 필요가 없다.
2. 항상 두 개척지 사이를 차량으로 오갈 수 있는 경우만 주어지므로 무조건 두번째 기저 조건에 걸리게 된다.

 

정답 코드

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

const int N = 1002;
int n, k;
struct Edge {
	int nn, nv;
};
vector<Edge> edges[N];
struct Pos {
	int cn, cv, cs;
	bool operator<(const Pos& other) const {
		return cv > other.cv;
	}
};

int dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 0, 0, 0 });
	vector<int> dist(n + 2, 2e9);
	dist[0] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cv = pos.cv, cs = pos.cs;
		if (dist[cn] < cv) continue;
		if (cn == n + 1) return cv;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv, ns = cs + edge.nv;
			if (ns > 100) {
				nv += 5;
				ns = edge.nv;
			}

			if (dist[nn] > nv) {
				dist[nn] = nv;
				pq.push({ nn, nv, ns });
			}
		}
	}
	return -1;
}

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

	cin >> n >> k;
	while (k--) {
		int a, b, c; cin >> a >> b >> c;
		if (c > 100) continue;
		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}

	cout << dijkstra();
}