백준 17396번 백도어 C++

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

 

다익스트라

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

#include <bitset>

using namespace std;
using int64 = long long;

int n, m;

struct VertexCost {
    int64 vertex;
    int64 cost;

    bool operator<(const VertexCost& other) const{
        return cost < other.cost;
    }
    bool operator>(const VertexCost& other) const{
        return cost > other.cost;
    }
};

vector<vector<pair<int64, int64>>> graph;
vector<bool> CanGo;

int64 Dijikstra() {
    priority_queue<VertexCost, vector<VertexCost>, greater<VertexCost>> pq;

    vector<int64> best(n, INT64_MAX);
    pq.push({ 0,0 });
    best[0] = 0;

    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();

        if (best[curr.vertex] < curr.cost) continue;

        for (auto a : graph[curr.vertex]) {

            int64 nextVertex = a.first;
            int64 nextCost = curr.cost + a.second;

            if (!CanGo[nextVertex]) continue;
            if (best[nextVertex] <= nextCost) continue;

            pq.push({ nextVertex,nextCost });
            best[nextVertex] = nextCost;
        }
    }

    if (best[n - 1] == INT64_MAX) return -1;
    return best[n - 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);

    cin >> n >> m;
    graph = vector<vector<pair<int64, int64>>>(n, vector<pair<int64, int64>>());
    CanGo = vector<bool>(n);
    for (int i = 0; i < n; i++) {
        int canGo;
        cin >> canGo;
        if (canGo == 0) CanGo[i] = true;
        else CanGo[i] = false;
    }
    CanGo[n - 1] = true;

    for (int i = 0; i < m; i++) {
        int64 a, b, t;
        cin >> a >> b >> t;
        graph[a].push_back({ b,t });
        graph[b].push_back({ a,t });
    }

    int64 ans = Dijikstra();
    cout << ans;
}