Submission #704539

#	Time	Username	Problem	Language	Result	Execution time	Memory
704539		KenIsGenius	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	373 ms	32100 KiB

commuter_pass

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define int long long
using namespace std;

#ifdef LOCAL
#define WOSAOJI freopen("in.txt", "r", stdin);
#else
#define WOSAOJI ios_base::sync_with_stdio(0), cin.tie(0);
#endif

#define chmax(a, b) (a) = (a) > (b) ? (a) : (b)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)

const int MAXN = 2e5 + 5; 

int n;
vector<pair<int, int>> adj[MAXN];
vector<int> dag[MAXN];
void dijkstra(int s, int *mn) {
    fill(mn + 1, mn + 1 + n, 1ll << 60);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({mn[s] = 0, s});
    while (pq.size()) {
        auto [cost, x] = pq.top(); pq.pop();
        if (cost > mn[x]) continue;
        for (auto [i, w] : adj[x]) {
            if (mn[i] > mn[x] + w) {
                dag[i].clear();
                pq.push({mn[i] = mn[x] + w, i});
            }
            if (mn[i] == mn[x] + w) {
                dag[i].pb(x);
            }
        }
    }
}
int m, s, t, u, v;
int ondag[MAXN], mn[MAXN], mnu[MAXN], mnv[MAXN];
void solve() {
    dijkstra(u, mnu);
    dijkstra(v, mnv);
    int ans = mnu[v];
    int m1 = 1ll << 60, m2 = 1ll << 60;
    for (int i = 1; i <= n; i++) {
        if (ondag[i]) {
            chmin(m1, mnu[i]);
            chmin(m2, mnv[i]);
        }
    }
    chmin(ans, m1 + m2);
    cout << ans << '\n';
}

void work() {
    dijkstra(s, mn);
    queue<int> q; q.push(t);
    while (q.size()) {
        int x = q.front(); q.pop();
        ondag[x] = 1;
        for (int i : dag[x]) {
            if (!ondag[i]) q.push(i);
        }
    }
}

void input() {
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    for (int i = 0, x, y, w; i < m; i++) {
        cin >> x >> y >> w;
        adj[x].pb({y, w});
        adj[y].pb({x, w});
    }
}

signed main() {
    WOSAOJI
    input();
    work();
    solve();
}

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