Submission #698441

#	Time	Username	Problem	Language	Result	Execution time	Memory
698441		vjudge1	Evacuation plan (IZhO18_plan)	C++17	0 / 100	337 ms	24164 KiB

plan

#include<bits/stdc++.h>   

using i64 = long long; 

const i64 inf = 1e18;

class DSU {
    public:
    std::vector<int> dsu, len;
    int n;
    DSU(int _n) : n(_n) {
        dsu.resize(n);
        len.resize(n, 1);
        std::iota(begin(dsu), end(dsu), 0);
    }  
    int get(int u) {
        if (dsu[u] == u) return u;
        dsu[u] = get(dsu[u]);
        return dsu[u];
    }
    bool same(int u, int v) {
        return get(u) == get(v);
    }
    void merge(int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) return;
        if (len[u] > len[v]) std::swap(u, v);
        dsu[u] = v;
        len[v] += len[u];
    }         
};

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

    int n, m;
    std::cin >> n >> m;
    std::vector<std::pair<int, std::pair<int, int>>> edges(m);
    std::vector<std::pair<int, int>> g[n];

    for (int i = 0; i < m; i++) {
        int a, b, w;
        std::cin >> a >> b >> w;
        a--, b--;

        edges[i] = {w, {a, b}};

        g[a].push_back({w, b});
        g[b].push_back({w, a});
    }

    int k;
    std::cin >> k;
    std::vector<int> npp(k);

    for (int i = 0; i < k; i++) {
        std::cin >> npp[i];
        npp[i]--;
    }

    std::vector<i64> dp(n, inf);
    std::set<std::pair<i64, int>> q;

    for (int i = 0; i < k; i++) {
        q.insert({0, npp[i]});
        dp[npp[i]] = 0;
    }

    while (q.empty() == false) {
        int u = q.begin() -> second;
        dp[u] = q.begin() -> first;
        q.erase(q.begin());
        
        for (auto [w, v] : g[u]) {
            if (dp[u] + w < dp[v]) {
                q.erase({dp[v], v});

                q.insert({dp[u] + w, v});
            }
        }
    }

    for (int i = 0; i < n; i++) {
        std::cout << dp[i] << ' ';
    }
    std::cout << '\n';

    int Q;
    std::cin >> Q;

    for (int i = 0; i < Q; i++) {
        int s, t;
        std::cin >> s >> t;
        

    }

    return 0;                           
}                                           

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46