BOJ 18223

31 Jan 2020 • ProblemSolving

민준이와 마산 그리고 건우

문제출처

문제 해석

  • 민준이가 마산까지 가는 최단경로에 건우가 있는지 판단하는 문제입니다.

설계(5)

  • 최단경로를 찾기 위해 dijkstra알고리즘을 사용합니다.
  • (민준->마산)거리 == (민준->건우)거리 + (건우->마산)거리 인지 계산하여 결과를 도출합니다.

구현(15)

코드
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

#define MAXN 5001
#define INF 987654321

vector<pair<int, int> > adj[MAXN];

int dist[MAXN];
int V, E, P;

int dijkstra(int start, int end) {
	for (int i = 1; i <= V; i++) {
			dist[i] = INF;
	}
	priority_queue<pair<int, int> > pq;
	pq.push({ 0,start });
	dist[start] = 0;
	while (!pq.empty()) {
		int here = pq.top().second;
		int weights = -pq.top().first;
		
		pq.pop();
		if (dist[here] < weights) continue;
		for (int i = 0; i < adj[here].size(); i++) {
			int next = adj[here][i].first;
			int next_weights = adj[here][i].second + weights;
			if (dist[next] > next_weights) {
				dist[next] = next_weights;
				pq.push({ -next_weights,next });
			}
		}
	}
	return dist[end];
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> V >> E >> P;
	for (int i = 0; i < E; i++) {
		int u, v, weights;
		cin >> u >> v >> weights;
		adj[u].push_back({ v,weights });
		adj[v].push_back({ u,weights });
	}
	if (dijkstra(1, V) == dijkstra(1, P) + dijkstra(P, V)) {
		cout << "SAVE HIM\n";
	}
	else {
		cout << "GOOD BYE\n";
	}
	return 0;
}
디버깅
제출결과

8ms

마무리

  • 다익스트라 알고리즘을 사용하는 기본 문제입니다. 주의할 점은 딱히 없습니다.
 BOJ

Related Posts