Submission #260598

#	Time	Username	Problem	Language	Result	Execution time	Memory
260598		Toirov_Sadi	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	447 ms	33384 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 7;

int n;
int m;
int s;
int t;
int u;
int v;
int used[N];
long long res;
long long ds[N];
long long dt[N];
long long du[N];
long long dv[N];
long long dp[N];
vector<int> g1[N];
vector<pair<int, int>> g[N];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
void dij(int s, long long *d){
    memset(d, 31, sizeof ds);
    memset(used, 0, sizeof used);

    d[s] = 0;
    q.push({d[s], s});
    while(!q.empty()){
        int v = q.top().second;
        q.pop();
        if(used[v] == 1) continue;

        used[v] = 1;
        for(auto to: g[v]){
            if(d[to.first] > d[v] + to.second){
                d[to.first] = d[v] + to.second;
                q.push({d[to.first], to.first});
            }
        }
    }
}
void dfs(int x){
    used[x] = 1;
    dp[x] = dv[x];
    for(auto to: g1[x]){
        if(used[to] == 0) dfs(to);

        dp[x] = min(dp[x], dp[to]);
    }
    res = min(res, du[x] + dp[x]);
}
int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    cin >> s >> t >> u >> v;

    for(int i = 1; i <= m; i ++){
        int x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }
    dij(s, ds);
    dij(t, dt);
    dij(u, du);
    dij(v, dv);

    for(int x = 1; x <= n; x ++){
        for(auto to: g[x]){
            if(ds[x] + to.second + dt[to.first] == ds[t]){
                g1[x].push_back(to.first);
            }
        }
    }

    res = du[v];
    for(int i = 1; i <= 2; i ++){
        memset(used, 0, sizeof used);
        dfs(s);
        swap(du, dv);
    }
    cout << res << "\n";
}

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