제출 #1369991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369991		norrawichzzz	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	168 ms	24464 KiB

commuter_pass

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

#define tup tuple<long long,int,int>

const long long INF = 1e18;
const int N = 1e5+5;

int n,m,s,t,U,V;
vector<pair<int, int>> adj[N];
vector<tuple<int,int,int>> edge;
vector<int> dag[N];

long long sd[N], td[N], ud[N], vd[N], mnx[N], mny[N];

void prepare() {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    fill(sd, sd+N, INF);
    sd[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();

        if (d > sd[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (sd[v] > sd[u] + w) {
                sd[v] = sd[u]+w;
                pq.push({sd[v],v});
            }
        }
    }

    fill(td, td+N, INF);
    td[t] = 0;
    pq.push({0, t});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();

        if (d > td[u]) continue;

        for (auto [v,w] : adj[u]) {
            if (td[v] > td[u] + w) {
                td[v] = td[u] + w;
                pq.push({td[v], v});
            }
        }
    }

    fill(ud, ud+N, INF);
    ud[U] = 0;
    pq.push({0, U});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();

        if (d > ud[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (ud[v] > ud[u] + w) {
                ud[v] = ud[u]+w;
                pq.push({ud[v],v});
            }
        }
    }

    fill(vd, vd+N, INF);
    vd[V] = 0;
    pq.push({0, V});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();

        if (d > vd[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (vd[v] > vd[u] + w) {
                vd[v] = vd[u]+w;
                pq.push({vd[v],v});
            }
        }
    }
}

void getdag() {
    for (auto [u,v,w] : edge) {
        if (sd[u] + w + td[v] == sd[t]) {
            dag[u].push_back(v);
        }
        if (sd[v] + w + td[u] == sd[t]) {
            dag[v].push_back(u);
        }
    }
}


void dfs(int u) {
    mnx[u] = min(mnx[u], ud[u]);
    mny[u] = min(mny[u], vd[u]);

    //cout<< u<< '\n';
    for (auto &v : dag[u]) {
        if (mnx[v] == INF) dfs(v);
        mnx[u] = min(mnx[u], mnx[v]);
        mny[u] = min(mny[u], mny[v]);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin>> n>> m>> s>> t>> U>> V;

   
    for (int i=0; i<m; i++) {
        int u,v,w;
        cin>> u>> v>> w;
        edge.push_back({u,v,w});
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    prepare();

    getdag();

    fill(mnx, mnx+N, INF);
    fill(mny, mny+N, INF);
    dfs(s);

    long long ans = INF;
    for (int i=1; i<=n; i++) ans = min({ans, ud[i] + mny[i], vd[i] + mnx[i]});
    cout<< ans;
}

• 서브태스크 1: 16 / 16
• 서브태스크 2: 0 / 15
• 서브태스크 3: 0 / 24
• 서브태스크 4: 0 / 45