제출 #680347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680347		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	296 ms	18664 KiB

commuter_pass

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

#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define getBit(x, i) ((x) >> (i) & 1)
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i--)

typedef long long ll;
typedef pair<ll, ll> ii;

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 1e5 + 7;

int n, m, s, t, x, y;
ll d[N][3];
vector<ii> adj[N];

void dijk(int s, int i) {
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    pq.push(ii(0, s)); d[s][i] = 0;

    while (sz(pq)) {
        ii u = pq.top(); pq.pop();
        if (u.fi != d[u.se][i]) continue;
        for (auto [v, w]: adj[u.se]) {
            if (minimize(d[v][i], d[u.se][i] + w)) {
                pq.push(ii(d[v][i], v));
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> s >> t >> x >> y;
    rep(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w));
    }

    memset(d, 0x3f, sizeof d);
    dijk(s, 0); dijk(t, 1);
    rep(u, 1, n) {
        for (auto &[v, w]: adj[u]) {
            if (d[u][0] + d[v][1] + w == d[t][0] || d[v][0] + d[u][1] + w == d[t][0]) {
                w = 0;
            }
        }
    }
    dijk(x, 2);
    cout << d[y][2];
}

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