백준 17396 c++ "백도어" -[PlusUltraCode]

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

 

 

[필자 사고]

 

전형적인 다익스트라 문제이다.

 

이 문제의 중요한 점은 ward배열이다. 즉 발각 되냐 안되냐에 있다.

 

와드가 1로 되어 있는 곳은 탐색을 하면 안되므로 그 부분을 신경 써주면 된다.

 

또한 값들이 매우 크다. int형 범위로는 담을 수 없을수도 있기 때문에 사전에 long으로 바꿔서 문제를 풀어준다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include<cstring>
#include <string>
using namespace std;

typedef pair<long, int> Node;

int N, M;

vector<int> ward;
vector<vector<Node>> Arr;
vector<long> pathLoad;
vector<int> visited;

void Dijkstra() {
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	pq.push({ 0,0 });
	pathLoad[0] = 0;
	while (!pq.empty()) {
		int nowIdx = pq.top().second;
		long ac_path = pq.top().first;
		if (nowIdx == N - 1) {
			cout << ac_path;
			return;
		}
		pq.pop();
		if (visited[nowIdx])continue;
		visited[nowIdx] = true;
		for (Node nextNode : Arr[nowIdx]) {
			int nextIdx = nextNode.second;
			int nextCost = nextNode.first;
			
			if (ward[nextIdx] == 1)continue;
			if (pathLoad[nextIdx] > pathLoad[nowIdx] + nextCost) {
				pathLoad[nextIdx] = pathLoad[nowIdx] + nextCost;
				pq.push({ pathLoad[nextIdx],nextIdx });
			}
		}
	}
}

void Input() {
	cin >> N >> M;
	Arr.resize(N);
	pathLoad.resize(N, LONG_MAX);
	visited.resize(N, false);
	ward.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> ward[i];
	}
	ward[N - 1] = 0;
	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		Arr[s].push_back({ w,e });
		Arr[e].push_back({ w,s });
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Dijkstra();
	if (pathLoad[N - 1] == LONG_MAX) {
		cout << -1;
	}
}