Submission #633211

#	Time	Username	Problem	Language	Result	Execution time	Memory
633211		Blossomstream	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	486 ms	24148 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, s, t, u, v;
vector<pair<int, int> > adj[100000];
vector<ll> ds;
vector<ll> du;
vector<ll> dv;
vector<bool> visited;
vector<ll> mu;
vector<ll> mv;
vector<int> p[100000];
ll ans = LONG_LONG_MAX;
void dijkstra(int i, vector<ll> & d) {
    d.assign(n, LONG_LONG_MAX);
    visited.assign(n, false);
    d[i] = 0;
    priority_queue<pair<ll, int> > q;
    q.push(make_pair(0, i));
    while(!q.empty()) {
        int j = q.top().second;
        q.pop();
        if(visited[j]) continue;
        visited[j] = true;
        for(auto k : adj[j]) {
            d[k.first] = min(d[k.first], d[j] + ((ll) k.second));
            q.push(make_pair(-d[k.first], k.first));
        }
    }
}
void dfs(int node) {
    visited[node] = true;
    ans = min(ans, dv[node] + mu[node]);
    ans = min(ans, du[node] + mv[node]);
    for(int next : p[node]) {
        if(!visited[next]) {
            dfs(next);
        }
    }
}
int main() {
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    s--; t--; u--; v--;
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        adj[a].push_back(make_pair(b, c));
        adj[b].push_back(make_pair(a, c));
    }
    dijkstra(u, du);
    dijkstra(v, dv);
    ds.assign(n, LONG_LONG_MAX);
    ds[s] = 0;
    priority_queue<pair<ll, int> > q;
    q.push(make_pair(0, s));
    visited.assign(n, false);
    mu.assign(n, LONG_LONG_MAX);
    mv.assign(n, LONG_LONG_MAX);
    mu[s] = du[s];
    mv[s] = dv[s];
    while(!q.empty()) {
        int i = q.top().second;
        q.pop();
        if(visited[i]) continue;
        visited[i] = true;
        for(auto j : adj[i]) {
            if(ds[j.first] > ds[i] + ((ll) j.second)) {
                ds[j.first] = ds[i] + ((ll) j.second);
                q.push(make_pair(-ds[j.first], j.first));
                mu[j.first] = min(mu[i], du[j.first]);
                mv[j.first] = min(mv[i], dv[j.first]);
                while(p[j.first].size() > 0) p[j.first].erase(p[j.first].end() - 1);
                p[j.first].push_back(i);
            } else if(ds[j.first] == ds[i] + ((ll) j.second)) {
                mu[j.first] = min(mu[j.first], mu[i]);
                mv[j.first] = min(mv[j.first], mv[i]);
                p[j.first].push_back(i);
            }
        }
    }
    visited.assign(n, false);
    dfs(t);
    cout << min(ans, dv[u]) << endl;
}

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