Submission #854331

#	Time	Username	Problem	Language	Result	Execution time	Memory
854331		asdasdqwer	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	686 ms	69924 KiB

commuter_pass

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

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

int dijsktra(int source, int dest, vector<set<pii>> &g) {
    int n = g.size();
    priority_queue<pii> pq;
    vector<int> d(n, 1e16);
    d[source] = 0;
    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});
            }
        }
    }

    return d[dest];
}

vector<int> dijsktra(int source, vector<set<pii>> &g) {
    int n = g.size();
    priority_queue<pii> pq;
    vector<int> d(g.size(), 1e16);
    d[source] = 0;
    for (int i=0;i<g.size();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});
            }
        }
    }

    return d;
}

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 = dijsktra(s, g);
    vector<bool> proc(n, false);

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

    vector<set<pii>> cp = g;

    // all edges going away from 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 p
                temp.erase(temp.find(x));
                temp.insert({x.first, 0});

                q.push(x.first);
            }
        }

        g[p] = temp;
    }

    int val = dijsktra(u, v, g);
    g = cp;
    q.push(t);
    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) {
                // edges going towards the sink
                g[x.first].erase(g[x.first].find({p, x.second}));
                g[x.first].insert({p, 0});

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

    cout << min(dijsktra(u, v, g), val) << "\n";
}

Compilation message (stderr)

commuter_pass.cpp: In function 'std::vector<long int> dijsktra(int64_t, std::vector<std::set<std::pair<long int, long int> > >&)':
commuter_pass.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::set<std::pair<long int, long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i=0;i<g.size();i++) {
      |                  ~^~~~~~~~~

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