Submission #1158681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158681		Hakuna	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	367 ms	35068 KiB

commuter_pass

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,fma")
using namespace std;

const int N = 1e5 + 10;
multiset< pair<int, long long> > g[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;
    
    for (int i = 1; i <= m; i++) {
        long long u, v, c;
        cin >> u >> v >> c;
        
        g[u].emplace(v, c);
        g[v].emplace(u, c);
    }
    
    long long d[n + 1];
    long long p[n + 1];
    for (int i = 0; i <= n; i++) {
        d[i] = 1e18;
        p[i] = -1;
    }
    d[S] = 0;
    set< pair<long long, int> > q;
    q.emplace(0, S);
    while (!q.empty()) {
        auto [mn, v] = *q.begin();
        q.erase(q.begin());
        
        for (auto [to, w] : g[v]) {
            if (d[to] > d[v] + w) {
                q.erase({d[to], to});
                d[to] = d[v] + w;
                p[to] = v;
                q.emplace(d[to], to);
            }
        }
    }
    
    for (int i = T, j = -1; i != -1; j = i, i = p[i]) {
        auto f = g[i].lower_bound({p[i], 0});
        int Ff = f->first;
        g[i].erase(f);
        g[i].emplace(Ff, 0);
        
        auto s = g[i].lower_bound({j, 0});
        int Ss = s->first;
        g[i].erase(s);
        g[i].emplace(Ss, 0);
    }
    
    for (int i = 0; i <= n; i++) d[i] = 1e18;
    d[U] = 0;
    q.emplace(0, U);
    while (!q.empty()) {
        auto [mn, v] = *q.begin();
        q.erase(q.begin());
        
        for (auto [to, w] : g[v]) {
            if (d[to] > d[v] + w) {
                q.erase({d[to], to});
                d[to] = d[v] + w;
                q.emplace(d[to], to);
            }
        }
    }
    cout << d[V];

    return 0;
}

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