Submission #20099855

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using Pair = pair<int64_t, int>;
using Graph = vector<vector<int>>;
using PQueue = priority_queue<Pair, vector<Pair>, greater<Pair>>;

vector<int> calc_safety(int N, int S, const Graph &graph, vector<int> &C_vec)
{
    vector<int> safety(N, S + 1);
    queue<int> que;
    for (int C : C_vec) {
        safety.at(C) = 0;
        que.push(C);
    }
    while (!que.empty()) {
        int s = que.front(); que.pop();
        int safety_s = safety.at(s);
        for (int d : graph.at(s)) {
            int safety_d = safety_s + 1;
            if (safety.at(d) <= safety_d)
                continue;
            safety.at(d) = safety_d;
            que.push(d);
        }
    }
    return safety;
}

vector<int64_t> calc_fee(const int64_t INF, int N, int S,
                    int64_t P, int64_t Q, const vector<int> &safety)
{
    vector<int64_t> fee(N, 0);
    for (int i = 1; i < N - 1; ++i) {
        if (safety.at(i) == 0)
            fee.at(i) = INF;
        else if (safety.at(i) <= S)
            fee.at(i) = Q;
        else
            fee.at(i) = P;
    }
    return fee;
}

int main()
{
    constexpr int64_t INF = 1e+11;
    int N, M, K, S;
    cin >> N >> M >> K >> S;
    int64_t P, Q;
    cin >> P >> Q;
    vector<int> C_vec(K);
    for (auto &C : C_vec) {
        cin >> C;
        --C;
    }
    Graph graph(N);
    for (int j = 0; j < M; ++j) {
        int A, B;
        cin >> A >> B;
        --A; --B;
        graph.at(A).push_back(B);
        graph.at(B).push_back(A);
    }
    auto safety = calc_safety(N, S, graph, C_vec);
    auto fee = calc_fee(INF, N, S, P, Q, safety);
    vector<int64_t> cost(N, INF);
    PQueue pq;
    cost.at(0) = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto top = pq.top(); pq.pop();
        auto s = top.second;
        auto cost_s = top.first;
        if (cost.at(s) < cost_s)
            continue;
        for (auto d : graph.at(s)) {
            auto cost_d = cost_s + fee.at(d);
            if (cost.at(d) <= cost_d)
                continue;
            cost.at(d) = cost_d;
            pq.push({cost_d, d});
        }
    }
    cout << cost.at(N - 1) << endl;
}

Submission Info

Judge Result