[ boj : 18223 ] 민준이와 마산 그리고 건우

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

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

해설 : 전형적인 다익스트라 문제입니다. 다만 신경쓸만한 부분은 최단거리 중에 건우를 만날수 있냐 없냐인데 이 부분은 배열 하나만 선언해주면 됩니다.

전 check 배열하나 선언해 준 다음 다익스트라를 돌리면서 가중치가 '작거나 같을때'  OR연산으로 체크해 주었습니다. 이때 주의할점은 priority_queue에 push 를 하는 경우는 무조건 가중치가 '작을때만' 해주어야 합니다. 

같을때 넣어주면 동일한 정점이 다수가 pq에 들어가게 되겠죠?

(참고로 전 1번에서 n 번정점이 아닌 뒤집어서 탐색해주었습니다.)

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

struct info {
	int to, weight;
	bool operator<(const info& cur) const {
		return weight > cur.weight;
	}
};

int n, m,p;
bool check[5001];
vector<info> v[5001];

void solve();
void djik(int x, int y);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	while (t--)solve();
	return 0;
}
void solve()
{
	cin >> n >> m >> p;
	int x, y, w;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> w;
		v[x].push_back({ y,w });
		v[y].push_back({ x,w });
	}
	djik(n, 1);
	//for (int i = 1; i <= n; i++)
	//	cout << check[i] << " ";
	if (check[1])cout << "SAVE HIM";
	else cout << "GOOD BYE";
}
void djik(int x, int y)
{
	int dist[5001];
	for (int i = 1; i <= n; i++) dist[i] = (int)1e9;

	priority_queue<info> pq;
	dist[x] = 0;
	pq.push({ x,0 });
	check[p] = true;

	while (!pq.empty())
	{
		info cur = pq.top();
		pq.pop();

		if (dist[cur.to] < cur.weight)continue;

		for (int i = 0; i < v[cur.to].size(); i++) {
			int next = v[cur.to][i].to;
			int next_weight = v[cur.to][i].weight;

			if (dist[next] >= next_weight + dist[cur.to]) {
				check[next] |= check[cur.to];
				if (dist[next] > next_weight + dist[cur.to]) {
					dist[next] = next_weight + dist[cur.to];
					pq.push({ next,dist[next] });
				}
			}
		}
	}
}