[G4] 백준 18223번 민준이와 마산 그리고 건우 C++ 다익스트라

리뷰

 

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

1에서 v까지의 최단 경로와 p를 거쳐가는 경로의 길이가 같은지 여부를 찾는 문제

 

 

전역 변수

• V : 배열의 최대 크기를 저장할 상수 변수
• v : 정점의 개수를 저장할 변수
• e : 간선의 개수를 저장할 변수
• p : 건우가 위치한 정점을 저장할 변수
• Edge : 간선 정보 다음 노드 nn, 간선의 크기 nv를 정의할 구조체
• edges : 간선 정보를 저장할 Edge타입 벡터
• Pos : 시뮬레이션 정보 현재 노드 cn, 누적 간선 크기 cv를 정의할 구조체, cv를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

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

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

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = edge.nv;
			if (dist[nn] > cv + nv) {
				dist[nn] = cv + nv;
				pq.push({ nn, dist[nn] });
			}
		}
	}
	return -1;
}

 

다익스트라를 통해 sn~dn까지의 최단 거리를 구하는 함수

 

문제풀이

1. 변수 v, e, p에 값을 각각 입력 받아준다.
2. e개의 간선 정보를 입력 받아 edges배열에 양방향으로 추가해 준다.
3. 변수 fast에 dijkstra함수를 통해 1~v까지의 최단 경로를 구해 저장해 준다.
4. fast가 1~p까지의 최단 경로, p~v까지의 최단 경로를 더한 값과 같다면 "SAVE HIM"을 출력해 준다.
5. 만약 같지 않다면 "GOOD BYE"를 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

없음

 

 

정답 코드

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

const int V = 5001;
int v, e, p;
struct Edge {
	int nn, nv;
};
vector<Edge> edges[V];
struct Pos {
	int cn, cv;
	bool operator<(const Pos& other) const {
		return cv > other.cv;
	}
};

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

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

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = edge.nv;
			if (dist[nn] > cv + nv) {
				dist[nn] = cv + nv;
				pq.push({ nn, dist[nn] });
			}
		}
	}
	return -1;
}

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

	cin >> v >> e >> p;
	while (e--) {
		int a, b, c; cin >> a >> b >> c;
		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}

	int fast = dijkstra(1, v);
	if (fast == dijkstra(1, p) + dijkstra(p, v)) cout << "SAVE HIM";
	else cout << "GOOD BYE";
}