제출 #1158265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158265		bbldrizzy	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2094 ms	327680 KiB

commuter_pass

#include <bits/stdc++.h>
#define s second
#define f first
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
vector<vector<P>> adj;
ll ans = 1e18;

void dijkstra(vector<ll> &dist, int node) {
    dist[node] = 0;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.push({0, node});
    while (!pq.empty()) {
        P u = pq.top(); pq.pop();
        if (u.f != dist[u.s]) continue;
        for (P j: adj[u.s]) {
            if (dist[u.s]+j.s < dist[j.f]) {
                pq.push({dist[j.f] = dist[u.s]+j.s, j.f});
            }
        }
    }
}

void BFS(ll t, ll S, vector<ll> &distU, vector<ll> &distV, vector<ll> &diSt) {
    ll sPath = diSt[t];
    //cout << "SPATH: " << sPath;
    queue<pair<P, P>> pq;
    pq.push({{t, sPath}, {distU[t], distV[t]}}); // <node, pathlengthremaining>, <minudist, minvdist>
    while (!pq.empty()) {
        //cout << "HERE";
        pair<P, P> n = pq.front(); pq.pop();
        if (n.f.f == S) {
            //cout << "HERE: " << n.s.f << " " << n.s.s << "\n";
            ans = min(ans, n.s.f + n.s.s); continue;
        }
        for (P u: adj[n.f.f]) {
            if (n.f.s - u.s == diSt[u.f]) {
                ll nu = min(n.s.f, distU[u.f]);
                ll nv = min(n.s.s, distV[u.f]);
                pq.push({{u.f, n.f.s - u.s}, {nu, nv}});
            }
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    ll n,m; cin >> n >> m;
    ll S, t; cin >> S >> t;
    ll u, v; cin >> u >> v;
    adj.resize(n+1);
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    vector<ll> diSt(n+1, 1e18);
    dijkstra(diSt, S);
    vector<ll> distU(n+1, 1e18);
    vector<ll> distV(n+1, 1e18);
    dijkstra(distU, u);
    dijkstra(distV, v);
    //cout << distU[t] << " " << distV[t] << '\n';  
    BFS(t, S, distU, distV, diSt);
    cout << min(ans, distU[v]);
}

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