[BOJ]백준 17396번: 백도어(C++)/Dijkstra

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

17396번: 백도어

다익스트라 기본 문제

요즘 다익스트라가 어렵게 나오는 것 같아서 다익스트라 심화 문제를 얼른 많이 풀어보고 싶다

어제 카카오 기출 훑어봤을 때에는 트리에서의 다이나믹프로그래밍 문제도 있더라 ....

저번 주에 너무 놀아서 다시 문제 많이많이 풀어야겠다

문제에서 주어진 시야에 보이는 노드들을 disable하고 dijkstra로 탐색하는 과정에서 도착 노드가 아닌 disable node들은 패스하도록 구현해주었다

 

주의해야할 것은 문제의 answer 범위가 int값을 넘어간다는 점

#include <cstdio>
#include <vector>
#include <queue>
#define INF 10000000001
#define ll long long
using namespace std;

int n, m;
vector<int> disable;
vector<vector<pair<int,int>>> g;

int main() {
	scanf("%d%d", &n, &m);
	disable = vector<int>(n);
	g = vector<vector<pair<int,int>>>(n);
	
	for (int i = 0; i < n; i++)scanf("%d",&disable[i]);
	for (int i = 0,a,b,t; i < m; i++) {
		scanf("%d%d%d", &a, &b, &t);
		g[a].push_back(make_pair(t, b));
		g[b].push_back(make_pair(t, a));
	}


	vector<bool> visit(n,false);
	vector<ll> dist(n,INF);
	priority_queue<pair<ll, int>> pq;

	dist[0] = 0;
	pq.push(make_pair(0, 0));

	while (!pq.empty()) {
		auto cur = pq.top(); pq.pop();
		if (visit[cur.second])continue;

		visit[cur.second] = true;
		for (auto x : g[cur.second]) {
			if (!(disable[x.second]&&x.second!=n-1) && (dist[x.second] > dist[cur.second] + x.first)) {
				dist[x.second] = x.first + dist[cur.second];
				pq.push(make_pair(-dist[x.second], x.second));
			}
		}
	}

	printf("%lld", dist[n - 1] == INF ? -1 : dist[n - 1]);

	return 0;
}