Submission #1308456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308456		pobe	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	529 ms	30720 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
#define int long long
vector <int> get(int start, vector <vector <pair <int, int>>> & gr) {
    set <pair <int, int>> cur;
    int n = gr.size();
    vector <int> dist(n, 2e18);
    dist[start] = 0;
    cur.insert({0, start});
    while (!cur.empty()) {
        int d, num;
        tie(d, num) = *cur.begin();
        cur.erase(cur.begin());
        for (auto &[next, w] : gr[num]) {
            if (dist[next] > d + w) {
                cur.erase({dist[next], next});
                dist[next] = d + w;
                cur.emplace(dist[next], next);
            }
        }
    }
    return dist;
}
vector <int> dists, distt, distv, distu;
int ans = 2e18;
void dfs(int num, int d, vector <vector <pair <int, int>>> &gr, vector <int> &vis, vector <int> &mx1, vector <int>& mx2) {
    vis[num] = 1;
    mx1[num] = distu[num];
    mx2[num] = distv[num];
    for (auto &[next, w] : gr[num]) {
        if (!vis[next]) {
            if (d == w + dists[num] + distt[next]) {
                dfs(next, d, gr, vis, mx1, mx2);
                mx1[num] = min(mx1[num], mx1[next]);
                mx2[num] = min(mx2[num], mx2[next]);
            }
        } else {
            if (d == w + dists[num] + distt[next]) {
                mx1[num] = min(mx1[num], mx1[next]);
                mx2[num] = min(mx2[num], mx2[next]);
            }
        }
    }
    ans = min(ans, mx1[num] + distv[num]);
    ans = min(ans, mx2[num] + distu[num]);
}
ostream & operator << (ostream &out, vector <int> val) {
    for (auto v : val) {
        out << v << ' ';
    }
    return out;
}
void solve() {
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    --s;
    --t;
    --u;
    --v;
    vector <vector <pair <int, int>>> gr(n);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        gr[a].emplace_back(b, c);
        gr[b].emplace_back(a, c);
    }
    dists = get(s, gr);
    distt = get(t, gr);
    distu = get(u, gr);
    distv = get(v, gr);
//    cout << distu << '\n' << distv << '\n';
    vector <int> vis(n, 0);
    vector <int> mx1(n, 2e18), mx2(n, 2e18);
    dfs(s, dists[t], gr, vis, mx1, mx2);
    cout << min(ans, distu[v]) << '\n';
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    solve();
}

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