Submission #1042721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042721		DeathIsAwe	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	317 ms	28660 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long

void dijkstra(ll n, ll a, vector<vector<pair<ll,ll>>> &graph, vector<ll> &from) {
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    vector<bool> solved(n);
    for (int i=0;i<n;i++) {
        if (i == a) {
            pq.push(make_pair(0, i));
        } else {
            pq.push(make_pair(INT64_MAX, i));
        }
        solved[i] = false;
        from[i] = INT64_MAX;
    }
    from[a] = 0;

    pair<ll,ll> node;
    while (pq.size() > 0) {
        node = pq.top(); pq.pop();
        if (solved[node.second]) {
            continue;
        }
        solved[node.second] = true;
        for (pair<ll,ll> i: graph[node.second]) {
            if (!solved[i.first]) {
                if (from[i.first] > from[node.second] + i.second) {
                    from[i.first] = from[node.second] + i.second;
                    pq.push(make_pair(from[i.first], i.first));
                }
            }
        }
    }
}



int32_t main() {
    ll n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v;
    ll a, b, c;
    s--; t-- ; u--; v--;
    vector<ll> froms(n), fromt(n), fromu(n), fromv(n);
    priority_queue<pair<ll,ll>> pq;
    vector<vector<pair<ll,ll>>> graph(n);
    for (int i=0;i<m;i++) {
        cin >> a >> b >> c;
        graph[a-1].push_back(make_pair(b-1, c));
        graph[b-1].push_back(make_pair(a-1, c));
    }


    
    dijkstra(n, s, graph, froms);
    dijkstra(n, t, graph, fromt);
    dijkstra(n, u, graph, fromu);
    dijkstra(n, v, graph, fromv);



    ll mindis = froms[t];
    vector<pair<ll,ll>> goodnodes;
    vector<bool> visitedfor(n), visitedret(n);
    for (int i=0;i<n;i++) {
        if (froms[i] + fromt[i] == mindis) {
            goodnodes.push_back(make_pair(fromu[i], i));
        }
        visitedfor[i] = false;
        visitedret[i] = false;
    }
    sort(goodnodes.begin(),goodnodes.end());
    vector<pair<ll,ll>> stac;
    vector<ll> dpuforward(n, INT64_MAX), dpureturn(n, INT64_MAX);
    pair<ll,ll> node;
    for (pair<ll,ll> i: goodnodes) {
        stac.clear();
        if (!visitedfor[i.second]) {
            stac.push_back(make_pair(i.second, 1));
            dpuforward[i.second] = i.first;
            visitedfor[i.second] = true;
        } if (!visitedret[i.second]) {
            stac.push_back(make_pair(i.second, -1));
            dpureturn[i.second] = i.first;
            visitedret[i.second] = true;
        }
        while (stac.size() > 0) {
            node = stac.back(); stac.pop_back();
            //cout << node.first << ' ' << node.second << ' ' << i.first << '\n';
            for (pair<ll,ll> j: graph[node.first]) {
                if (froms[j.first] + j.second + fromt[node.first] == mindis) {
                    if (node.second < 1 && !visitedret[j.first]) {
                        stac.push_back(make_pair(j.first, -1));
                        dpureturn[j.first] = i.first;
                        visitedret[j.first] = true;
                    }
                } if (fromt[j.first] + j.second + froms[node.first] == mindis) {
                    if (node.second > -1 && !visitedfor[j.first]) {
                        stac.push_back(make_pair(j.first, 1));
                        dpuforward[j.first] = i.first;
                        visitedfor[j.first] = true;
                    }
                }
            }
        }
    }
    ll ans = fromv[u];
    for (pair<ll,ll> i: goodnodes) {
        ans = min(ans, fromv[i.second] + min(dpuforward[i.second], dpureturn[i.second]));
    }
    if (mindis == 0) {
        cout << 1/0;
    }
    cout << ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:112:18: warning: division by zero [-Wdiv-by-zero]
  112 |         cout << 1/0;
      |                 ~^~

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