[백준] 17396번: 백도어 / C++

✏️ 문제 링크

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

17396번: 백도어

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

기본 다익스트라에 아주 약간 조건을 추가해주면 된다. 상대편에 시야가 보이는 경우만 피해가면 되기 때문에 다음과 같은 조건을 추가한다. e-1가 아닌 경우에만 해당하는 이유는 마지막 도착지는 상대편에게 보일 수 밖에 없으며 무조건 1이기 때문에 갈 수 있어야 한다. 

if(sight[nxt] == 1 && nxt!=e-1) continue;

 

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
using pii=pair<long, long>;

#define MAX 1000001
#define INF 9999999999

vector<pii> vec[MAX];
vector<long> dist(MAX, INF);
long sight[MAX];

long dijkstra(long s, long e){
    priority_queue<pii> pq; pq.push({0, s});
    dist[s]=0;
    
    while(!pq.empty()){
        pii t=pq.top(); pq.pop();
        long c=t.second; long d=t.first*-1;
        
        if(dist[c]<d)continue;
        for(int i=0; i<vec[c].size(); i++){
            long nxt=vec[c][i].first;
            long nxt_d=vec[c][i].second+d;
            if(sight[nxt] == 1 && nxt!=e-1) continue;
            if(nxt_d<dist[nxt]){
                dist[nxt]=nxt_d;
                pq.push({nxt_d*-1, nxt});
            }
        }
    }
    
    return dist[e-1];
    
}
int main(){
    
    long N, M; cin>>N>>M;
    for(int i=0; i<N; i++) cin>>sight[i];
    
    while(M--){
        long a, b, t; cin>>a>>b>>t;
        vec[a].push_back({b, t});
        vec[b].push_back({a, t});
    }
    
    long ans=dijkstra(0, N);
    
    if(ans>=INF) cout<<-1;
    else cout<<ans;

    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐