제출 #654604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654604		leroycut	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2087 ms	160704 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


const ll INF = 1e18 + 3;
const int N = 1e5 + 3;

class cmt
{
    public:
        bool operator() (pair<int, ll> a, pair<int, ll> b){
            return a.second > b.second;
        }
};

int s, t, v, u, n, m;
vector<pair<int, ll>> g[N];
vector<int> dag1[N], dag2[N];
ll dpv[N], dpu[N];
vector<ll> ds, dv, du;


vector<ll> djikstra(int S){
    vector<ll> d(N, INF);
    d[S] = 0;
    priority_queue<pair<int, ll>, vector<pair<int, ll>>, cmt> q;
    q.push({S, 0});

    while(!q.empty()){
        auto cur = q.top();
        q.pop();
        int node = cur.first;
        ll dist = cur.second;
        if(dist != d[node]) continue;

        for(auto i : g[node]){
            if(dist + i.second < d[i.first]){
                d[i.first] = dist + i.second;
                q.push({i.first, dist + i.second});
            }
        }
    }

    return d;
}

void dfs(int S){
    for(auto i : g[S]){
        if(ds[i.first] < ds[S]){
            if(ds[S] - i.second == ds[i.first]){
                dag1[S].push_back(i.first);
                dag2[i.first].push_back(S);
                dfs(i.first);
            }
        }
    }
}

ll ans = INF;

void dfsp1(int S){
    dpu[S] = min(dpu[S], du[S]);
    dpv[S] = min(dpv[S], dv[S]);
    for(auto i : dag1[S]){
        dfsp1(i);
        dpu[S] = min(dpu[i], dpu[S]);
        dpv[S] = min(dpv[i], dpv[S]);
    }

    ans = min(ans, dv[S] + dpu[S]);
    ans = min(ans, du[S] + dpv[S]);
}

void dfsp2(int S){
    dpu[S] = min(dpu[S], du[S]);
    dpv[S] = min(dpv[S], dv[S]);
    for(auto i : dag2[S]){
        dfsp2(i);
        dpu[S] = min(dpu[i], dpu[S]);
        dpv[S] = min(dpv[i], dpv[S]);
    }

    ans = min(ans, dv[S] + dpu[S]);
    ans = min(ans, du[S] + dpv[S]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for(int i = 0; i < N; ++i){
        dpu[i] = dpv[i] = INF;
    }

    cin >> n >> m >> s >> t >> v >> u;

    for(int i = 0; i < m; ++i){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    ds = djikstra(s);
    du = djikstra(u);
    dv = djikstra(v);
    dfs(t);
    dfsp1(t);
    for(int i = 0; i < N; ++i){
        dpu[i] = dpv[i] = INF;
    }
    dfsp2(s);

    cout << min(ans, dv[u]);
}

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