백준 17396 백도어

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

숭고한 공식 풀이는 여기서 보실 수 있습니다.

간단한 다익스트라 문제입니다. 상대 진영의 넥서스를 제외하고는 시야가 보이는 곳은 가서는 안 되므로 아예 그래프에서 제거해버려도 됩니다.

새로 만들어진 그래프에서 0부터 시작하는 다익스트라를 돌려 최단거리를 찾으면 끝납니다.

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int SZ=100005;
typedef long long ll;
vector<pair<int,ll>> graph[SZ];
const ll INF = (1LL<<60);
priority_queue<pair<ll,int>> pq;
int go[SZ];
ll dst[SZ];
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n,m; cin>>n>>m;
	for(int i=0;i<n;i++) cin>>go[i];
	go[n-1]=0;
	for(int i=0;i<m;i++){
		int x,y; ll z; cin>>x>>y>>z;
		if(go[x]==1 || go[y]==1) continue;
		graph[x].push_back({y,z});
		graph[y].push_back({x,z});		
	}
	for(int i=0;i<n;i++) dst[i]=INF;
	dst[0]=0;
	pq.push({-dst[0],0});
	while(!pq.empty()){
		auto t=pq.top(); pq.pop();
		if(dst[t.ss]!=-t.ff) continue;
		for(auto nxt:graph[t.ss]){
			if(dst[t.ss]!=INF && dst[nxt.ff]>dst[t.ss]+nxt.ss){
				dst[nxt.ff]=dst[t.ss]+nxt.ss;
				pq.push({-dst[nxt.ff],nxt.ff});
			}
		}
	}
	if(dst[n-1]==INF) cout<<-1;
	else cout<<dst[n-1];
	return 0;
}