[C++] 백준 17396번: 백도어

문제 링크

17396번: 백도어

문제 요약

무향 가중치 그래프에 N개의 정점이 존재하고, 일부 정점은 방문이 불가능하다. 0번 정점에서 N - 1번 정점으로 이동하기 위한 최단경로를 구해야 한다.

접근 방법

음의 가중치가 존재하지 않기 때문에 음수 사이클 생각없이 편하게 다익스트라 알고리즘을 돌려주면 됩니다. 인접한 정점이 방문 불가능한 정점인 경우에는 그냥 무시해주는 식으로 간단하게 처리해주면 됩니다.

단, 간선의 갯수가 최대 30만개이고, 가중치도 최대 10만까지 입니다. 따라서 최악의 경우 int로 표현 가능한 범위를 넘을 수 있기 때문에 long long을 사용해주는 것이 좋습니다. 단순 다익스트라 문제임에도 정답률이 살짝 낮은 이유는 아마 여기에 걸리신 분들이 다수 있어서 그런 것 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const long long MAX = 100001, INF = 1e11;
int n, m;
long long dist[MAX];
bool spotted[MAX];
vector<pair<long long, int>> adj[MAX];

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

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		cin >> spotted[i];
	
	spotted[n - 1] = false;

	fill_n(dist, MAX, INF);

	while (m--)
	{
		int a, b, t;
		cin >> a >> b >> t;
		adj[a].push_back({ b, t });
		adj[b].push_back({ a, t });
	}

	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
	pq.push({ 0, 0 });

	while (!pq.empty())
	{
		auto now = pq.top();
		pq.pop();

		if (now.first > dist[now.second])
			continue;

		for (auto& i : adj[now.second])
		{
			if (spotted[i.first])
				continue;
			pair<long long, int> next = { now.first + i.second, i.first };
			if (next.first < dist[next.second])
			{
				dist[next.second] = next.first;
				pq.push(next);
			}
		}
	}

	cout << (dist[n - 1] == INF ? -1 : dist[n - 1]);
	return 0;
}