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

백준

---

🤔문제 이해

말은 거창하지만 전형적인 다익스트라 문제에 방문할 수 없는 구간이 존재한다는 것만 추가된 문제이다.

---

🔥풀이🔥

다익스트라로 구현을 하고 상대의 시야에 보이는 분기점은 방문하지 않도록 해주기만 하면 된다. 넥서스의 경우는 시야가 보이지만 갈 수 있어야 하므로 따로 0으로 처리해주었다. 

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define INF 10000000000

int n, m, a, b, t;
bool sight[100001];
vector<vector<pair<int, int>>> edge(100001);
long long dist[100001];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> sight[i];
        if (i == n - 1) sight[i] = false;
    }
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> t;
        edge[a].push_back({b, t});
        edge[b].push_back({a, t});
    }
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
    }
    dist[0] = 0;
    priority_queue<pair<long long, int>> pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        int now = pq.top().second;
        long long time = -pq.top().first;
        pq.pop();

        if (dist[now] < time) continue;
        dist[now] = time;

        for (auto x: edge[now]) {
            long long next_time = time + x.second;
            int next = x.first;
            if (sight[next]) continue;
            if (dist[next] <= next_time) continue;
            dist[next] = next_time;
            pq.push({-next_time, next});
        }
    }
    if (dist[n - 1] == INF) cout << -1 << "\n";
    else cout << dist[n - 1] << "\n";

}