Submission #1295725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295725		ionut27	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	522 ms	20392 KiB

commuter_pass

#include "bits/stdc++.h"
#include <type_traits>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

// ============ Macros starts here ============
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif // DEBUG
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(Ostream& os, const Cont& v) {
    os << "{";
    for (auto& x : v) { os << x << ", "; }
    return os << "}";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
    return os << "{" << p.first << ", " << p.second << "}";
}

#define readFast                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#ifdef LOCAL
#define read() ifstream fin("date.in.txt")
#else
#define read() readFast
#endif // LOCAL
// ============ Macros ends here ============

#define fin cin
#define ll long long
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define output(x) (((int)(x) && cout << "YES\n") || cout << "NO\n")
#define LSB(x) (x & (-x))
#define test cout << "WORKS\n";

const int N = 1e5 + 15;
const int MOD = 1e9 + 7;

vector<pair<int, int>> graf[N];
vector<int> from[N];
int n, m, S, T, U, V;
vector<ll> dU, dV;

vector<ll> djk(vector<int> start) {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> que;
    vector<ll> dist(n, LLONG_MAX);

    for (int node : start) {
        que.push({ 0, node });
        dist[node] = 0;
    }
    while (!que.empty()) {
        ll cost = que.top().first;
        int node = que.top().second;
        que.pop();

        if (cost != dist[node]) {
            continue;
        }

        for (auto [to, w] : graf[node]) {
            if (dist[to] > cost + w) {
                dist[to] = cost + w;
                que.push({ dist[to], to });
            }
        }
    }
    return dist;
}

ll djk2(int start, int stop) {
    priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> que;
    vector<ll> dist(n, LLONG_MAX);
    vector<ll> distForUV(n, LLONG_MAX);
    vector<vector<ll>> dp(2, vector<ll>(n, LLONG_MAX));

    que.push({ 0, start });
    dist[start] = 0;
    dp[0][start] = dU[start];
    dp[1][start] = dV[start];

    while (!que.empty()) {
        dbg(que.top());
        ll cost = que.top()[0];
        int node = que.top()[1];
        que.pop();

        if (dist[node] != cost) {
            continue;
        }

        for (auto [to, w] : graf[node]) {
            ll minSumUV = min(dp[0][node], dU[to]) + min(dp[1][node], dV[to]);

            if (dist[to] > dist[node] + w) {
                dist[to] = dist[node] + w;

                dp[0][to] = min(dp[0][node], dU[to]);
                dp[1][to] = min(dp[1][node], dV[to]);
                que.push({ dist[to], to });
            } else if (dist[to] == dist[node] + w) {
                if (dp[0][to] + dp[1][to] > minSumUV) {
                    dp[0][to] = min(dp[0][node], dU[to]);
                    dp[1][to] = min(dp[1][node], dV[to]);
                }
            }
        }
    }
    return dp[0][stop] + dp[1][stop];
}


int main() {
    read();
    fin >> n >> m;
    fin >> S >> T;
    fin >> U >> V;
    --S, --T, --U, --V;

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        --a, --b;
        graf[a].push_back({ b, c });
        graf[b].push_back({ a, c });
    }
    dU = djk({ U });
    dV = djk({ V });
    dbg(dU);
    dbg(dV);

    cout << min({ dU[V], djk2(S, T), djk2(T, S) }) << '\n';

    return 0;
} /*stuff you should look for !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   * test the solution with the given example
   * int overflow, array bounds, matrix bounds
   * special cases (n=1?)
   * do smth instead of nothing and stay organized
   * WRITE STUFF DOWN
   * DON'T GET STUCK ON ONE APPROACH
~Benq~*/

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