제출 #377218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377218		smjleo	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	409 ms	24156 KiB

commuter_pass

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int long long
#define nl '\n'
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int mod = 1000000007, mod2 = 998244353;
 
// change this
const int N = 100005;
 
int n, m, s, t, u, v, du[N], dv[N], ds[N], dt[N], b1[N], b2[N];
vector< pair<int, int> > g[N];
 
signed main() {
    io;
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
 
    for (int i=0; i<m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
 
    // distance from u
    priority_queue< pair<int, int>, vector<pair<int, int> >, greater<> > pq;
    for (int i=1; i<=n; i++) du[i] = dv[i] = ds[i] = dt[i] = b1[i] = b2[i] = LLONG_MAX;
 
    du[u] = 0;
    pq.push({0, u});
 
    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();
        int x = cur.second, d = cur.first;
 
        if (d > du[x]) continue;
 
        for (auto i : g[x]) {
            int nx = i.first, nd = d + i.second;
            // cout << "AA " << x << ' ' <<  nx << ' ' << nd << nl;
            if (du[nx] <= nd) continue;
            du[nx] = nd;
            pq.push({nd, nx});
        }
    }
 
    // distance from v
    dv[v] = 0;
    pq.push({0, v});
 
    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();
 
        int x = cur.second, d = cur.first;
        if (d > dv[x]) continue;
 
        for (auto i : g[x]) {
            int nx = i.first, nd = d + i.second;
            if (dv[nx] <= nd) continue;
            dv[nx] = nd;
            pq.push({nd, nx});
        }
    }
 
    // distance from s, update b1[N] also
    ds[s] = 0;
    // b1[s] = dv[s];
    pq.push({0, s});
 
    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();
 
        int x = cur.second, d = cur.first;
        if (d > ds[x]) continue; 
        b1[x] = min(b1[x], dv[x]);
 
        for (auto i : g[x]) {
            int nx = i.first, nd = d + i.second;
            if (ds[nx] < nd) continue;
            if (ds[nx] == nd) {
                b1[nx] = min(b1[nx], b1[x]);
                continue;
            }
            ds[nx] = nd;
            b1[nx] = b1[x];
            pq.push({nd, nx});
        }
    }
 
    // distance from t, update b2[N] also
    dt[t] = 0;
    // b2[t] = dv[t];
    pq.push({0, t});
 
    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();
 
        int x = cur.second, d = cur.first;
        if (d > dt[x]) continue;
        b2[x] = min(b2[x], dv[x]);
 
        for (auto i : g[x]) {
            int nx = i.first, nd = d + i.second;
            if (dt[nx] < nd) continue;
            if (dt[nx] == nd) {
                b2[nx] = min(b2[nx], b2[x]);
                continue;
            }
            dt[nx] = nd;
            b2[nx] = b2[x]; 
            pq.push({nd, nx});
        }
    }
 
    int ans = du[v];
 
    // for (int i=1; i<=n; i++) cout << du[i] << ' ';
    // cout << nl;
 
    for (int i=1; i<=n; i++) {
        // is it on the shortest path?
        if (ds[i] + dt[i] != ds[t]) continue;   // no!
        ans = min(ans, 
            du[i] +     // go here first
            min(b1[i], b2[i])  // go to destination
        );
    }
 
    cout << ans << nl;
}

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