[백준]백도어(17396)

문제 링크 : [백준]백도어(17396)

문제 설명

N개의 노드와 M개의 비용을 포함한 엣지 정보가 주어집니다.
또한 각 노드를 경우할 수 있는지 여부도 주어집니다.(N-1번 노드는 1이어도 방문 가능합니다.)
0번 노드에서 시작하여 N-1번 노드까지 가는 최단 경로를 구하세요.

입력

N(노드의 갯수, 1 <= N <= 100,000)
M(간선의 갯수, 1 <= M <= 300,000)
V_i(노드 방문 가능 여부)
S_i E_i T_i(출발 노드, 도착 노드, 걸리는 시간, 1 <= 100,000)

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

출력

12

카테고리

#다익스트라

시간 복잡도 상한

O(N * logN) 혹은 O(M * logM)

해결 방법

1. 0번에서 출발하여 N-1번 노드까지 최단 거리를 구하는 문제입니다.
2. 거기에 방문 가능 여부만 체크하여 우선순위 큐에 넣을때 걸러주면 됩니다.
3. 나머지는 다익스트라와 동일합니다.

시간복잡도

O(M * logM)

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define N 100000
using namespace std;
typedef long long L;
typedef pair<L,int>P;
int n,m,d[N],e[N],i,a,b,c;
vector<P>v[N];
priority_queue<P,vector<P>,greater<P>>q;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(i=0;i<n;i++)cin>>d[i];
    d[n-1]=0;
    while(m--){
        cin>>a>>b>>c;
        v[a].push_back({c,b});
        v[b].push_back({c,a});
    }
    q.push({0,0});
    while(!q.empty()){
        P x=q.top();q.pop();
        if(e[x.second])continue;
        e[x.second]=1;
        if(x.second==n-1){
            cout<<x.first;
            return 0;
        }
        for(P y:v[x.second])if(!e[y.second]&&!d[y.second])q.push({x.first+y.first,y.second});
    }
    cout<<-1;
}