Submission #1069064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069064		NoLove	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	194 ms	23948 KiB

commuter_pass

/**
 *    author : Lăng Trọng Đạt
 *    created: 2024-08-21
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int long long
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int i = a; (i) <= (b); i++)
void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e18;
const int MOD = 1e9 + 7;

const int N = 1e5 + 5;
vector<pii> adj[N];
int g[N];
int n, m, q, k, a, b;

int p[4]; // {S, T, U, V}

void dij(vector<int>& d, int source) {
    d = vector<int>(n + 1, INF);
    d[source] = 0;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, source});

    while (!pq.empty()) {
        pii tmp = pq.top(); pq.pop();
        int v = tmp.se, w = tmp.f;
        if (d[v] != w) continue;

        for (pii& u : adj[v]) {
            if (d[u.f] > w + u.se) {
                d[u.f] = w + u.se;
                pq.push({d[u.f], u.f});
            }
        }
    }
}

namespace sub1 {
    vector<int> d[4];
    void solve() {
        FOR(i, 0, 3) {
            dij(d[i], p[i]);
        }

        int ans = d[2][p[3]];

        int a = INF, b = INF;
        db(d[1][p[0]], d[0][p[1]])
        FOR(i, 1, n) {
            if ((d[0][i] + d[1][i]) == d[0][p[1]]) {
                if (d[3][i] == 693825709) {
                    db(i, d[0][i], d[0][i] + d[1][i])
                }
                mi(a, d[2][i]);
                mi(b, d[3][i]);
            }
        }
        db(a, b, ans, a + b)
        mi(ans, a + b);
        cout << ans;
    }
}

namespace sub2{
    void solve() {

    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
//    freopen("PathLib.inp", "r", stdin);
//    freopen("PathLib.out", "w", stdout);
//737621047
//693825709

    cin >> n >> m;
    FOR(i, 0, 3) {
        cin >> p[i];
    }
    FOR(i, 1, m) {
        cin >> a >> b >> k;
        adj[a].push_back({b, k});
        adj[b].push_back({a, k});
    }

    sub1::solve();

//    if (n <= 10) {
//    } else {
//        sub2::solve();
//    }
}

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