제출 #851871

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

commuter_pass

// author: phucthuhigh
#include <bits/stdc++.h>
#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<ll, 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;
typedef long long ll;
typedef long double ldb;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const long long INFLL = (long long)1e18 + 7;

const int maxn = 1e5 + 5;
vector<pii> a[maxn];
ll d[4][maxn], n, m;

void dijkstra(int id, int s) {
    for (int i = 1; i <= n; i++) d[id][i] = INFLL;
    priority_queue<pii, vector<pii>, greater<pii> > q;
    d[id][s] = 0;
    q.push({d[id][s], s});
    while (sz(q)) {
        ll dist; int u; tie(dist, u) = q.top(); q.pop();
        if (dist != d[id][u]) continue;
        for (auto [w, v]: a[u]) {
            if (d[id][v] > w + dist) q.push({d[id][v] = w + dist, v});
        }
    }
}

void solve() {
    cin >> n >> m;
    ll s, t, u, v; cin >> s >> t >> u >> v;
    for (int i = 1; i <= m; i++) {
        int x, y; ll w; cin >> x >> y >> w;
        a[x].pb({w, y});
        a[y].pb({w, x});
    }
    dijkstra(0, s);
    dijkstra(1, t);
    dijkstra(2, u);
    dijkstra(3, v);
    ll ans = INFLL;
    for (int i = 1; i <= n; i++) {
        if (d[0][i] + d[1][i] == d[0][t]) ans = min(ans, d[3][i]);
    }
    cout << ans;
}

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: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45