Submission #676117

#	Time	Username	Problem	Language	Result	Execution time	Memory
676117		cristi_a	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	371 ms	29892 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e15;
const int nmax = 1e5;

vector<vector<pair<ll, int>>> dx(nmax+5);
vector<vector<int>> dag(nmax+5);
int n, m, s, t, u, v;
ll dist_s[nmax+5], dist_u[nmax+5], dist_v[nmax+5], ans, dpu[nmax+5], dpv[nmax+5];
bool viz[nmax+5];

void dij(int start, ll dist[]) {
    for(int i=1; i<=n; i++) {
        dist[i] = inf;
        dag[i].clear();
        viz[i] = false;
    }

    dist[start] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.emplace(0, start);

    while(pq.empty() == false) {
        pair<ll, int> now = pq.top(); pq.pop();

        if(viz[now.second]) continue;
        viz[now.second] = true;

        for(auto i : dx[now.second]) 
            if(now.first + i.first < dist[i.second]) {
                dag[i.second] = {now.second};
                dist[i.second] = now.first + i.first;
                pq.emplace(now.first + i.first, i.second);
            }
            else if(dist[i.second] == now.first + i.first) 
                dag[i.second].emplace_back(now.second);
    }
}

void dfs(int node) {
    viz[node] = true;
    dpu[node] = min(dpu[node], dist_u[node]);
    dpv[node] = min(dpv[node], dist_v[node]);
    for(auto i : dag[node]) {
        if(!viz[i])
            dfs(i);
        dpu[node] = min(dpu[node], dpu[i]);
        dpv[node] = min(dpv[node], dpv[i]);
    }
    ans = min(ans, dist_u[node] + dpv[node]);
    ans = min(ans, dist_v[node] + dpu[node]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m >> s >> t >> u >> v;
    for(int i=1; i<=m; i++) {
        int a, b; ll c; cin >> a >> b >> c;
        dx[a].emplace_back(c, b);
        dx[b].emplace_back(c, a);
    }

    dij(u, dist_u);
    dij(v, dist_v);
    dij(s, dist_s);

    for(int i=1; i<=n; i++) viz[i] = false;
    for(int i=1; i<=n; i++) {
        dpu[i] = inf;
        dpv[i] = inf;
    }

    ans = dist_v[u];
    dfs(t);
    cout << ans;
    return 0;
}

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