[백준] 17396 백도어 c++

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

17396번: 백도어

 

풀이과정

어려운 문제인 줄 알았지만, 다익스트라에서 1개의 조건만 더 추가하면 되는 기본 문제였다. 

상대의 시야를 num 배열에 담고 0이면 안 보이는 것, 1이면 보이는 것으로 해석한다. 상대의 시야에 걸리는 곳을 지나칠 수 없으니까 num이 1일 경우에는 continue를 이용해서 그 분기점을 넘어가도록 구현했다.

 

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
#define INF 10000000001

int N, M, x, y, z;
int num[100001];

vector <long long> dist;
vector <pair <int, int>> edge[100001];

priority_queue <pair <long long, int>> pq;

void dijkstra() {
	dist.resize(N, INF);
	dist[0] = 0;
	pq.push({ 0, 0 }); // 가중치, 정점

	while (!pq.empty()) {
		long long cost = -pq.top().first;
		int now = pq.top().second;
		pq.pop();

		if (num[now] || dist[now] < cost) continue;
		for (int i = 0; i < edge[now].size(); i++) {
			int next = edge[now][i].first;
			long long nextcost = edge[now][i].second;

			if (dist[next] > dist[now] + nextcost) {
				dist[next] = dist[now] + nextcost;
				pq.push({ -dist[next], next });
			}
		}
	}
}

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

	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> num[i];
	for (int i = 0; i < M; i++) {
		cin >> x >> y >> z;
		edge[x].push_back({ y, z });
		edge[y].push_back({ x, z });
	}
	dijkstra();

	if (dist[N - 1] != INF) cout << dist[N - 1];
	else cout << -1; // dist[N - 1] == INF 상대 넥서스까지 갈 수 없다.
}