백준 17396 백도어

신경 써줘야 할 조건들이 꽤 있었던 dijkstra 문제이다.
1. 거리들의 합이 int 범위를 벗어난다는 점
2. dist[now] < cost인 경우 continue를 해야하는 점
3. 시야에 보이는 분기점에 갈 수 없는 조건을 전처리하는데 도착지점은 예외 처리하는 점
이 세 가지 조건만 신경써주면 무난한 문제이다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<long long, int>;

const ll MAX = 999999999999999;
int n, m;
vector<pii> graph[100000];
ll dijkstra() {
    vector<ll> dist(n, MAX);
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    
    dist[0] = 0;
    pq.push({0, 0});
    
    while (!pq.empty()) {
        ll cost = pq.top().first;
        int now = pq.top().second;
        if (now == n-1) return dist[n-1];
        pq.pop();
        if (dist[now] < cost) continue;
        for (int i = 0; i < graph[now].size(); ++i) {
            int next = graph[now][i].first;
            ll nextCost = cost + graph[now][i].second;
            if (nextCost < dist[next]) {
                dist[next] = nextCost;
                pq.push({nextCost, next});
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    vector<int> cannotMove(n);
    for (int i = 0; i < n; ++i) cin >> cannotMove[i];
    cannotMove[n-1] = 0;
    for (int i = 0; i < m; ++i) {
        int a, b, t;
        cin >> a >> b >> t;
        if (cannotMove[a] || cannotMove[b]) continue;
        graph[a].push_back({b, t});
        graph[b].push_back({a, t});
    }
    cout << dijkstra();
}