제출 #1181306

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181306		peteza	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	141 ms	19100 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
const ll inf = 1e18;

int n, m, s, t, u, v, a, b, c;
vector<pair<int, int>> adj[100005];

bool vis[100005];
ll dtos[100005];
ll dtou[100005], dtov[100005];
priority_queue<pli, vector<pli>, greater<pli>> pq;
pair<ll, ll> minuv[100005];
ll ans = inf;

void dijk(ll *distarr, int st) {
    for(int i=0;i<=n;i++) distarr[i] = inf;
    distarr[st] = 0;
    memset(vis, 0, sizeof vis);
    pq.emplace(0, st);
    while(!pq.empty()) {
        auto e = pq.top(); pq.pop();
        if(vis[e.second]) continue;
        vis[e.second] = 1;
        for(auto &E:adj[e.second]) {
            if(distarr[E.first] > e.first + E.second) {
                distarr[E.first] = e.first + E.second;
                pq.emplace(distarr[E.first], E.first);
            }
        }
    }
    //yay dijkstra done
}

pair<ll, ll> dfsrev(int x) {
    //returns dtou, dtov minimum of this subgraph
    if(vis[x]) return minuv[x];
    vis[x] = 1;
    pair<ll, ll> toret = {dtou[x], dtov[x]};
    for(auto &e:adj[x]) {
        if(dtos[x] <= dtos[e.first]) {
            //definitely not part of the shortest path, gtfo
        } else {
            //check if possible to be a shortest path mmhmmh
            if(dtos[e.first] + e.second == dtos[x]) {
                auto res = dfsrev(e.first);
                ans = min(ans, res.first + dtov[x]);
                ans = min(ans, res.second + dtou[x]);
                toret.first = min(toret.first, res.first);
                toret.second = min(toret.second, res.second);
            }
        }
    }
    return minuv[x] = toret;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    while(m--) {
        cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }
    dijk(dtos, s); dijk(dtou, u); dijk(dtov, v);
    //now on dtos, do the thingy thing thing
    //start from t then reverse back back back then back again
    memset(vis, 0, sizeof vis);
    auto bruhwhybruhbruhbruh = dfsrev(t);
    cout << min({ans, dtov[u], dtou[v]});
}

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