제출 #1310750

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

commuter_pass

// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
#include <bits/stdc++.h>

#define pb push_back
#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define int long long
#define all(v) v.begin(),v.end()
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 3e5 + 1, inf = 1e18, mod = 998244353;

vector<array<int, 3>> g[N];
int used[N], dv[N], du[N];
vector<vector<int>> p;
vector<array<int, 3>> e(N);
int ans = inf;

void dfs(int v, int mnu, int mnv){
    mnu = min(mnu, du[v]);
    mnv = min(mnv, dv[v]);
    ans = min(ans, mnu + mnv);
    used[v]++;
    for(int to : p[v]){
        if(used[to] > 500) continue;
        dfs(to, mnu, mnv);
    }
}

void solve(){
    int n, m;
    cin >> n >> m;
    p.resize(n + 1);
    int s, t;
    cin >> s >> t;
    int u, v;
    cin >> u >> v;
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {u, v, w};
        g[u].push_back({v, w, i});
        g[v].push_back({u, w, i});
    }
    for(int i = 1; i <= n; i++) du[i] = dv[i] = inf;
    vector<int> dist(n + 1, inf);
    priority_queue<pair<int, int>> q;
    q.push({0, s});
    dist[s] = 0;
    while(q.size()){
        auto [musor, v] = q.top();
        q.pop();
        musor = -musor;
        if(musor != dist[v]) continue;
        for(auto [to, w, id] : g[v]){
            if(dist[to] == dist[v] + w) p[to].push_back(v);
            else if(dist[to] > dist[v] + w){
                p[to].clear();
                p[to].push_back(v);
                dist[to] = dist[v] + w;
                q.push({-dist[to], to});
            }
        }
    }
    q.push({0, u});
    du[u] = 0;
    while(q.size()){
        auto [musor, v] = q.top();
        q.pop();
        musor = -musor;
        if(musor != du[v]) continue;
        for(auto [to, w, id] : g[v]){
            if(du[to] > du[v] + w){
                du[to] = du[v] + w;
                q.push({-du[to], to});
            }
        }
    }
    q.push({0, v});
    dv[v] = 0;
    while(q.size()){
        auto [musor, v] = q.top();
        q.pop();
        musor = -musor;
        if(musor != dv[v]) continue;
        for(auto [to, w, id] : g[v]){
            if(dv[to] > dv[v] + w){
                dv[to] = dv[v] + w;
                q.push({-dv[to], to});
            }
        }
    }
    if(u == v){
        cout << 0;
        return;
    }
    dfs(t, inf, inf);
    cout << min(ans, du[v]);
}

signed main(){
    SS
    // freopen("trains.in", "r", stdin);
    // freopen("trains.out", "w", stdout);

    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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