제출 #1082893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1082893		SoobinHoangSon	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	461 ms	95596 KiB

commuter_pass

// author: phucthuhigh
#include <bits/stdc++.h>
#define ll long long
#define ldb long double
#define endl '\n'
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define cint(x) int(x - '0')
#define cchar(x) char(x + '0')
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define llll pair<long long, long long>
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) x/__gcd(x, y)*y
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const long long INFLL = (long long)1e18 + 7;

const int maxn = 1e5 + 5;


vector<ll> dijsktra(vector<tuple<int, int, ll>> &b, int n, int s) {
    vector<vector<llll> > a(n + 1);
    for (auto [u, v, w]: b) {
        a[u].pb({v, w});
    }
    vector<ll> d(n + 1, INFLL);
    priority_queue<llll, vector<llll>, greater<llll> > q;
    d[s] = 0;
    q.push({d[s], s});
    while (sz(q)) {
        auto [dist, u] = q.top(); q.pop();
        if (dist != d[u]) continue;
        for (auto [v, w]: a[u]) {
            if (d[v] > d[u] + w) q.push({d[v] = d[u] + w, v});
        }
    }
    return d;
}

void solve() {
    int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v;
    vector<tuple<int, int, ll>> a, b;
    for (int i = 1; i <= m; i++) {
        int x, y; ll w; cin >> x >> y >> w;
        b.pb({x, y, w});
        b.pb({y, x, w});
    }
    vector<ll> ds = dijsktra(b, n, s);
    vector<ll> dt = dijsktra(b, n, t);
    for (int i = 1; i <= n; i++) {
        a.pb({i, n + i, 0}); // 1 -> 2
        a.pb({i, 2*n + i, 0}); // 1 -> 3
        a.pb({n + i, 3*n + i, 0}); // 2 -> 4
        a.pb({2*n + i, 3*n + i, 0}); // 3 -> 4
    }
    for (auto [u, v, w]: b) {
        a.pb({u, v, w});
        a.pb({3*n + u, 3*n + v, w});
        if (ds[u] + dt[v] + w == ds[t]) {
            a.pb({n + u, n + v, 0});
            a.pb({2*n + v, 2*n + u, 0});
        }
    }
    vector<ll> ans = dijsktra(a, 4*n, u);
    cout << ans[3*n + v] << endl;
}

int main() {
    fastIO
    // freopen("test.inp", "r", stdin);
    // freopen("test.out", "w", stdout);
    int t = 1;
    while (t--) solve();
    cerr << "Times: " << TIME << "s." << endl;
    return 0;
}

/**
  *    {\__/}
  *    (• .•)
  *    / >♥️
**/

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