백준 17396 백도어

BOJ 17396

목표 : 유섭이가 0번 노드에서 N-1까지 최단거리로 갈 수 있는 비용을 구하자. 유섭이는 백도어를 하러가는 것이기 때문에 와드가 있는 지역은 갈 수 없다. 유섭이가 갈 수 없다면 -1을 출력한다.

조건 : 1 <= N <= 100000, 1 <= M <= 300000, 1 <= cost <= 100000

해결방안

유섭이는 넥서스를 제외한 와드가 없는 지역으로 이동할 수 있다. 음수인 간선이 없어 음수 사이클이 없는 그래프이므로 다익스트라를 통해 해결했다. 간선의 비용(cost)이 100000이고 간선의 개수(M)가 300000이므로 300억의 비용이 나올 수 있다. 출발지부터 i번째 노드에 오는데 사용한 비용의 최소값을 저장할 dist배열을 int형 대신 long long형으로 사용하자.

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1e10 * 3;
int N, M;
vector<bool> ward;
vector<pair<ll,int>> V[100001];
vector<ll> dist;

ll dijkstra(){
	dist.resize(N);
	for (int i = 1; i < N; i++){
		dist[i] = INF;
	}
	priority_queue<pair<ll,int>> pq;
	pq.push({0,0});
	while(!pq.empty()){
		int cur = pq.top().second;
		ll val = -pq.top().first;
		pq.pop();
		if (val > dist[cur]){
			continue;
		}
		for (int i = 0; i < V[cur].size(); i++){
			int des = V[cur][i].first;
			ll cost = val + V[cur][i].second;
			if (dist[des] > cost){
				dist[des] = cost;
				pq.push({-cost,des});
			}
		}
	}
	if (dist[N-1] == INF){
		return -1;
	}
	else{
		return dist[N-1];
	}
}

int main(){
	scanf("%d%d",&N,&M);
	ward.resize(N);
	for (int i = 0; i < N; i++){
		int t;
		scanf("%d",&t);
		if (t){
			ward[i] = true;
		}
	}
	ward[N-1] = false;
	for (int i = 0; i < M; i++){
		int from, to;
		ll cost;
		scanf("%d%d%lld",&from,&to,&cost);
        if (ward[from] || ward[to]){continue;} // 와드가 있다면
		V[from].push_back({to,cost});
		V[to].push_back({from,cost});
	}
	printf("%lld",dijkstra());
	return 0;
}

우선 간선을 입력받을 때 간선이 이동하는 거리에 와드가 설치되어 있다면 그래프에 추가하지 않는다. 우선 dist배열을 30억으로 초기화하고 0번부터 출발한다. 우선순위 큐를 사용해 현재까지 소모한 비용이 적은 경우부터 탐색한다.

만약 i번노드에 도착할 때 소모한 비용이 dist[i]보다 크면 이후 경우는 무조건 dist[i]을 사용했을 때보다 크므로 탐색을 생략한다. i번노드로 이동했을 때 dist[i]가 현재 비용보다 크다면 현재비용으로 초기화한 뒤 큐에 넣는다. 만약 dist[N-1]이 INF라면 도착이 불가한 경우이므로 -1를 출력한다.

힙을 사용해 O((N+M)logM)만에 해결할 수 있다.