Submission #1267217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267217		goppamach	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	245 ms	19640 KiB

commuter_pass

// #pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define sqr(x) ((x) * (x))
#define FOR(i, l, r) for (int i = l; i <= (r); i++)
#define FOD(i, l, r) for (int i = l; i >= (r); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);

using db = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vbool = vector<bool>;
using vvbool = vector<vbool>;

template<class T> inline bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); }
template<class T> inline bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); }

// #define DEBUG
#ifdef DEBUG
#include "D:\cpp\debug.h"
#else
#define debug(...)
#define debug_arr(...)
#endif

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 1E5 + 5;
constexpr int INF = 1E9 + 7;
constexpr ll INFLL = 1E18;
constexpr int MOD = 1E9 + 7; // 998244353
constexpr double EPS = 1E-10;

vpii adj[N];
ll d_u[N], d_v[N], d[N];
ll dp_u[N], dp_v[N];
int n, m, s, t, u, v;
ll res = INFLL;

void dijkstra1(int s, ll d[]) {
    using T = pair<ll, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    fill(d, d + n + 1, INFLL);
    pq.emplace(0, s);
    d[s] = 0;
    while (!pq.empty()) {
        auto [dist, u] = pq.top();
        pq.pop();
        if (dist != d[u]) continue;
        for (auto &[v, cost] : adj[u]) {
            if (chmin(d[v], d[u] + cost)) {
                pq.emplace(d[v], v);
            }
        }
    }
}

void dijkstra2(int s, int t) {
    using T = tuple<ll, int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    fill(d + 1, d + n + 1, INFLL);
    fill(dp_u, dp_u + n + 1, INFLL);
    fill(dp_v, dp_v + n + 1, INFLL);
    pq.emplace(0, s, 0);
    while (!pq.empty()) {
        auto [dist, x, p] = pq.top();
        pq.pop();
        if (d[x] == INFLL) {
            d[x] = dist;
            dp_u[x] = min(d_u[x], dp_u[p]);
            dp_v[x] = min(d_v[x], dp_v[p]);
            for (auto &[y, cost] : adj[x]) {
                pq.emplace(d[x] + cost, y, x);
            }
        } else if (dist == d[x]) {
            ll cand_u = min(d_u[x], dp_u[p]);
            ll cand_v = min(d_v[x], dp_v[p]);
            if (cand_u + cand_v < dp_u[x] + dp_v[x]) {
                dp_u[x] = cand_u;
                dp_v[x] = cand_v;
            }
        }
    }
    chmin(res, dp_u[t] + dp_v[t]);
}

void solve() {
    cin >> n >> m >> s >> t >> u >> v;

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    dijkstra1(u, d_u);
    dijkstra1(v, d_v);

    res = d_u[v];
    dijkstra2(s, t);
    dijkstra2(t, s);

    cout << res << el;
}

int main() {
    fast_io
    #define LOCAL
    #ifndef LOCAL
    #define PROBLEM ""
    freopen(PROBLEM ".INP", "r", stdin);
    freopen(PROBLEM ".OUT", "w", stdout);
    #endif

    int t = 1;
    // cin >> t;
    while (t--) solve();
}

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