제출 #854324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
854324		asdasdqwer	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	623 ms	66932 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define pii pair<int, int>

signed main() {
    // freopen("in.txt", "r", stdin);
    int n, m;cin>>n>>m;

    int s, t;cin>>s>>t;
    int u, v;cin>>u>>v;

    vector<set<pii>> g(n);
    for (int i=0;i<m;i++) {
        int a, b, c;cin>>a>>b>>c;
        a--;b--;
        g[a].insert({b, c});
        g[b].insert({a, c});
    }

    s--;t--;u--;v--;

    // dijsktra
    vector<int> d(n, 1e16);
    d[s] = 0;

    priority_queue<pii> pq;
    for (int i=0;i<n;i++) {
        pq.push({-d[i], i});
    }

    vector<bool> proc(n, false);

    while (!pq.empty()) {
        pii p=pq.top();pq.pop();
        if (proc[p.second]) continue;
        proc[p.second] = true;

        for (pii x : g[p.second]) {
            if (d[p.second] + x.second < d[x.first]) {
                d[x.first] = d[p.second] + x.second;
                pq.push({-d[x.first], x.first});
            }
        }
    }

    proc = vector<bool>(n, false);

    queue<int> q;
    q.push(t);

    vector<set<pii>> cp = g;

    // all edges going towards the sink
    while (!q.empty()) {
        int p=q.front();q.pop();
        if (proc[p]) continue;
        proc[p] = true;
        
        set<pii> temp = g[p];

        for (auto x : g[p]) {
            if (d[p] == d[x.first] + x.second) {
                // set edge weight to zero of node t
                temp.erase(temp.find({x.first, x.second}));
                temp.insert({x.first, 0});

                q.push(x.first);
            }
        }

        g[p] = temp;
    }


    d = vector<int>(n, 1e16);
    d[u] = 0;
    for (int i=0;i<n;i++) {
        pq.push({-d[i], i});
    }

    proc = vector<bool>(n, false);

    while (!pq.empty()) {
        pii p=pq.top();pq.pop();
        if (proc[p.second]) continue;
        proc[p.second] = true;

        for (pii x : g[p.second]) {
            if (d[p.second] + x.second < d[x.first]) {
                d[x.first] = d[p.second] + x.second;
                pq.push({-d[x.first], x.first});
            }
        }
    }

    int val = d[v];
    g = cp;
    proc = vector<bool>(n, false);

    while (!q.empty()) {
        int p=q.front();q.pop();
        if (proc[p]) continue;
        proc[p] = true;

        for (auto x : g[p]) {
            if (d[p] == d[x.first] + x.second) {
                g[x.first].erase(g[x.first].find({p, x.second}));
                g[x.first].insert({p, 0});

                q.push(x.first);
            }
        }
    }

    d = vector<int>(n, 1e16);
    d[u] = 0;
    for (int i=0;i<n;i++) {
        pq.push({-d[i], i});
    }

    proc = vector<bool>(n, false);

    while (!pq.empty()) {
        pii p=pq.top();pq.pop();
        if (proc[p.second]) continue;
        proc[p.second] = true;

        for (pii x : g[p.second]) {
            if (d[p.second] + x.second < d[x.first]) {
                d[x.first] = d[p.second] + x.second;
                pq.push({-d[x.first], x.first});
            }
        }
    }

    cout << min(d[v], val) << "\n";
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45