[알고리즘] 백준 17396번: 백도어 (C++)

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

17396번: 백도어

다익스트라 문제였으나 조금 더 디테일한 조건 분기가 필요했다.

if(canHide[next] && next != n - 1) continue;

적에게 들킬 경우 가지 말고, 하지만 넥서스라면 갈 수 있게끔 조건이 필요했다.

그리고, 최댓값의 경우 10,000,000,000가 나오니까 INF를 987654321이 아닌 더 큰 수가 필요하고, int 형의 범위를 넘어서기 때문에 unsigned long long을 사용해서 풀었다.

+ 궁금한 점
다익스트라를 돌리다가 중간에 필요한 값을 리턴 시키니까 오류가 나왔었다.
>> 시간 초과가 떠서 시간을 줄여보려 했었음

if(cost + nextCost < dist[next]){
    dist[next] = cost + nextCost;
    pq.push({next, dist[next]});
                
    //if(next == n - 1) return dist[next];
    //이걸 넣으면 틀리는 이유가 뭐지
    //거리를 최초로 갱신한다는 건 최솟값(비용)이라는 뜻 아닌가?
}

이 부분은 조금 더 공부해서 추가로 글을 써봐야겠다.

+22.02.20
다익스트라는 포함된 노드들 중 최단 거리를 우선적으로 선택하는 특성이 있어서 다음과 같은 반례가 존재한다.
e에 도착하자마자 리턴 할 경우 경로 값이 9가 되지만 실제적으로 최단 경로 값은 7-1에 의한 8이기 때문에 즉각적으로 리턴하면 안 된다.

---

[AC 코드]

#include <iostream>
#include <queue>
#include <vector>
#define MAX 100000
#define INF (10000000000 + 1) // N * t의 최댓값 == 10000000000
#define ull unsigned long long
#define piu pair<int, ull>
using namespace std;

int n, m;
bool canHide[MAX];
vector<piu> graph[MAX];
vector<ull> dist(MAX, INF);

struct cmp{
    bool operator()(piu &a, piu &b){
        return a.second > b.second;
    }  
};

ull dijkstra(){
    priority_queue<piu, vector<piu>, cmp> pq;
    pq.push({0, 0});
    dist[0] = 0;
    while(!pq.empty()){
        int now = pq.top().first;
        ull cost = pq.top().second;
        
        pq.pop();
        if(dist[now] < cost) continue;
        
        for(int i = 0; i < graph[now].size(); i++){
            int next = graph[now][i].first;
            ull nextCost = graph[now][i].second;
            
            if(canHide[next] && next != n - 1) continue;
            if(cost + nextCost < dist[next]){
                dist[next] = cost + nextCost;
                pq.push({next, dist[next]});
                
                //if(next == n - 1) return dist[next];
                //이걸 넣으면 틀리는 이유가 뭐지
                //거리를 최초로 갱신한다는 건 최솟값(비용)이라는 뜻 아닌가?
            }
        }
    }
    return dist[n - 1];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> canHide[i];
    }
    
    for(int i = 0; i < m; i++){
        int a, b;
        ull w;
        cin >> a >> b >> w;
        graph[a].push_back({b, w});
        graph[b].push_back({a, w});
    }
    
    ull result = dijkstra();
    
    if(result == INF) cout << -1;
    else cout << result;
    
    return 0;
}