제출 #1316504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316504		Zone_zonee	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	175 ms	23492 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+10;

int n, m, st, en, U, V;
ll dist1[N], dist2[N], dist3[2][N];
vector<pair<int, int>> adj[N];
inline void dijsktra(){
    priority_queue<pair<ll, int>, vector<pair<ll, int>>,greater<pair<ll, int>>> pq;
    memset(dist1, 0x3f, sizeof dist1);
    memset(dist2, 0x3f, sizeof dist2);
    pq.push({dist1[st] = 0, st});
    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(dist1[u] < d) continue;
        for(auto [v, w] : adj[u]){
            if(dist1[v] > d+w){
                pq.push({dist1[v] = d+w, v});
            }
        }
    }
    pq.push({dist2[en] = 0, en});
    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(dist2[u] < d) continue;
        for(auto [v, w] : adj[u]){
            if(dist2[v] > d+w){
                pq.push({dist2[v] = d+w, v});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> st >> en >> U >> V;
    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dijsktra();

    const ll mn = dist1[en];

    memset(dist3, 0x3f, sizeof dist3);
    //cost, node, in_node, in(bool), dist, prev
    priority_queue<tuple<ll, int, int, bool, ll, int>, vector<tuple<ll, int, int, bool, ll, int>>, greater<tuple<ll, int, int, bool, ll, int>>> pq;
    pq.push({dist3[0][U] = 0, U, -1, false, 0, -1});
    if(dist1[U] + dist2[U] == mn) pq.push({dist3[1][U] = 0, U, U, true, 0, -1});
    // cerr << "dbg : c u in_node in, d\n";
    while(!pq.empty()){
        auto [c, u, in_node, in, d, prev] = pq.top(); pq.pop();
        if(dist3[in][u] < c) continue;
        // cerr << "dbg : " << c << ' ' << u << ' ' << in_node << ' ' << in << ' ' << d << '\n';
        if(in){
            for(auto [v, w] : adj[u]){
                if(v == prev) continue;
                // v is on the same SP as in_node
                // cerr << "dbg case in : " << d+w << " " << dist1[v] << ' ' << dist1[in_node] << '\n';
                if(d+w == mn - dist1[v] - dist2[in_node] || d+w == mn - dist1[in_node] - dist2[v]){
                    if(dist3[in][v] > c)
                        pq.push({dist3[in][v] = c, v, in_node, in, d+w, u});
                }
                if(dist3[0][v] > c+w)
                    pq.push({dist3[0][v] = c+w, v, -1, 0, 0, u});
                
            }
        }else{
            for(auto [v, w] : adj[u]){
                if(v == prev) continue;
                if(dist1[v]+dist2[v] == mn){
                    if(dist3[in][v] > c+w)
                        pq.push({dist3[in][v] = c+w, v, v, 1, 0, u});
                }
                if(dist3[0][v] > c+w)
                    pq.push({dist3[0][v] = c+w, v, in_node, in, d, u});
            }
        }
    }
    cout << min(dist3[0][V], dist3[1][V]) << '\n';
}

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