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

문제 링크

BOJ 17396-백도어

문제

예제 입력1

5 7
0 0 0 1 1
0 1 7
0 2 2
1 2 4
1 3 3
1 4 6
2 3 2
3 4 1

에제 출력1

12

예제 입력2

5 7
0 1 0 1 1
0 1 7
0 2 2
1 2 4
1 3 3
1 4 6
2 3 2
3 4 1

에제 출력2

-1

풀이

다익스트라 알고리즘을 이용하면 쉽게 풀 수 있는 문제다.

다만 자료형 종류의 크기를 주의해야 하는데 다른 노드로 이동하는데 드는 최대 가중치가 100000이고 모든 노드를 한번씩 돈다 가정하면 100000번을 도는 것이니 100000 * 100000 이 최대 거리가 된다. 그렇기에 int 자료형으로 거리를 기록하면 문제를 틀리게 될것이다.

소스코드

#include "bits/stdc++.h"
#define ll long long
#define MAX 1000000000000
using namespace std;

int region[100005];
vector<vector<pair<int,int>>> adj(100005);
int n, m;

void Dijkstra(int a) {
	vector<ll> dst(100005, MAX);
	priority_queue<pair<ll, int>> q;
	q.push(make_pair(0, a));
	while (!q.empty()) {
		ll value = -q.top().first;
		int now = q.top().second;
		q.pop();
		if (region[now] == 1) {
			if (now == n - 1) {
				dst[n - 1] = min(dst[n - 1], value);
			}
			else {
				continue;
			}
		}

		if (dst[n - 1] <= value)
			continue;
		if (dst[now] <= value) {
			continue;
		}
		dst[now] = value;
		

		for (int i = 0; i < adj[now].size(); i++) {
			int next = adj[now][i].first;
			ll nValue = adj[now][i].second + value;

			if (nValue < dst[next]) {
				q.push(make_pair(-nValue, next));
			}
		}
	}

	if (dst[n - 1] == MAX) {
		cout << -1;
	}
	else {
		cout << dst[n - 1];
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> region[i];
	}
	int a, b, t;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> t;

		adj[a].push_back(make_pair(b,t));
		adj[b].push_back(make_pair(a, t));
	}
	Dijkstra(0);
}