[백준 18223] 민준이와 마산 그리고 건우 (C++)

문제 링크: https://www.acmicpc.net/problem/18223

18223번: 민준이와 마산 그리고 건우

1. 주의할 점

- 다익스트라 알고리즘에 대해 알고 있어야 한다

- 다익스트라 알고리즘을 수행할때, 초기화를 잘해줘야 한다

 

2. 구현

- 민준이가 건우를 도와서 마산에 도착하는 경우, 민준-> 건우 + 건우->마산까지의 거리가 민준->마산까지의 거리와 같을 때다(각 간선의 가중치는 1보다 큰 정수이기 때문이다)

- 모든 간선에 대한 정보를 V[] 배열에 입력받은 후, 다익스트라를 수행한다

- 민준 -> 마산까지 바로 갈때의 최단 거리를 Result[0]에 저장한다

- 민준 -> 건우 -> 마산까지의 최단거리를 Result[1]에 저장한다

- 삼항연산자를 통해 Result[0]와 Result[1]의 값을 비교하여 정답을 출력한다

 

#define MAX 987654321
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct info {
	int idx, val;
};
struct cmp {
	bool operator()(info& a, info& b) {
		return a.val > b.val;
	}
};
info tmp;
int node, edge, p, s, e, val,result[2],dist[5001];
vector<info> v[5001];

int dijkstra(int start, int dest) {
	int d = 0;
	for (int i = 1; i <= node; i++)
		dist[i] = MAX;
	dist[start] = 0;
	priority_queue<info, vector<info>, cmp> pq;
	tmp.idx = start;
	tmp.val = 0;
	pq.push(tmp);

	while (!pq.empty()) {
		int cidx = pq.top().idx;
		int cv = pq.top().val;
		pq.pop();
		if (cidx == dest) {
			d = cv;
			break;
		}
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i].idx;
			int nv = v[cidx][i].val;
			if (dist[next] > dist[cidx] + nv) {
				dist[next] = dist[cidx] + nv;
				tmp.idx = next;
				tmp.val = dist[cidx] + nv;
				pq.push(tmp);
			}
		}
	}
	return d;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> edge >> p;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		tmp.val = val;
		tmp.idx = s;
		v[e].push_back(tmp);
		tmp.idx = e;
		v[s].push_back(tmp);
	}
	result[0] = dijkstra(1, node);
	result[1] = dijkstra(1, p) + dijkstra(p, node);
	cout << (result[0] == result[1] ? "SAVE HIM" : "GOOD BYE");
	return 0;
}