Submission #793574

#	Time	Username	Problem	Language	Result	Execution time	Memory
793574		sharawang	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	300 ms	24688 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <climits>
#include <map>
#include <algorithm>    
#include <cmath>
#include <set>
 
using namespace std; // have to put this before can define
 
#define ll long long
#define arr array
 
const int mxN=1e5, mxM=2e5;

vector<arr<ll, 2> > adj [mxN];
vector<int> parents [mxN];
set<ll> sp_st;
ll dist [mxN], dist2[mxN];
int n, m, s, t, u, v;

int main () {
    cin >> n >> m >> s >> t >> u >> v;
    s--; t--; u--; v--;

    for (int i=0,a,b,c; i<m; i++) {
        cin >> a >> b >> c;
        adj[a-1].push_back({b-1,c});
        adj[b-1].push_back({a-1,c});
    }

    for (int i=0; i<n; i++) {
        dist[i] = LLONG_MAX;
        dist2[i] = LLONG_MAX;
    }

    // dijkstra's
    using T = arr<ll, 2>;
    priority_queue <T, vector<T>, greater<T> > pq;

    pq.push({0, s});
    dist[s] = 0;

    while (pq.size()) {
        auto a = pq.top();
        ll cdist = a[0]; int node = a[1];
        pq.pop(); // you've forgotten so many times now

        if (cdist != dist[node]) { // don't think we need to worry about duplicates
            // cout << ("this happen" ) << cdist << " " << node << endl;
            continue;
        }

        for (auto neighbor : adj[node]) {
            if (cdist + neighbor[1] < dist[neighbor[0]]) {
                pq.push({dist[neighbor[0]] = cdist + neighbor[1], neighbor[0]});
                parents[neighbor[0]].push_back(node); // don't think we have to worry about duplicates
            }
            else if (cdist + neighbor[1] == dist[neighbor[0]]) {
                parents[neighbor[0]].push_back(node);
            }
        }
    }

    // print out the parents
    // for (int i=0; i<n; i++) {
    //     auto v = parents[i];

    //     cout << i << ": " << endl;
    //     for (auto a : v) {
    //         cout << a << " ";
    //     }
    //     cout << endl;
    // }

    // dfs from T node
    set <int> sp_nodes;
    vector <bool> vis (n, false);

    queue<int> agenda;
    sp_nodes.insert(t); // dont' need 
    agenda.push(t);
    vis[t] = true;

    while (agenda.size()) {
        int node = agenda.front();
        agenda.pop();

        if (node==s) continue;

        for (auto a : parents[node]) {
            if (!vis[a]) {
                agenda.push(a);
                sp_nodes.insert(a);
                vis[a] = true;
            }
        }
    }

    if (vis[u] && vis[v]) {
        cout << 0; 
        return 0;
    }

    // dijkstra's, again
    bool both_not = false;
    if (!vis[u] && !vis[v]) {
        both_not = true;
    }

    int start, other;
    if (vis[u]) {
        start = v;
        other = u;
    }
    else {
        start = u;
        other = v;
    }

    dist2[start] = 0;
    pq.push({0, start});
    
    while (pq.size()) {
        auto a = pq.top();
        ll cdist = a[0]; int node = a[1];
        pq.pop(); // you've forgotten so many times now

        if (cdist != dist2[node]) { // don't think we need to worry about duplicates
            // cout << ("this happen" ) << cdist << " " << node << endl;
            continue;
        }

        if (node == other) {
            cout << cdist;
            return 0;
        }

        if (vis[node] && !both_not) {
            cout << cdist;
            return 0;
        }

        for (auto neighbor : adj[node]) {
            if (cdist + neighbor[1] < dist2[neighbor[0]]) {
                pq.push({dist2[neighbor[0]] = cdist + neighbor[1], neighbor[0]});
                parents[neighbor[0]].push_back(node); // don't think we have to worry about duplicates
            }
            else if (cdist + neighbor[1] == dist2[neighbor[0]]) {
                parents[neighbor[0]].push_back(node);
            }
        }
    }
   
}

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