Submission #1218031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218031		teslerpham	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	174 ms	33988 KiB

commuter_pass

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

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define el '\n'

using ll = long long;
using pii = pair<int,int>;
using vi  = vector<int>;
using vll = vector<ll>;

const ll INF = (ll)4e18;

void fastIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main(){
    fastIO();

    int N, M;
    cin >> N >> M;
    int S, T, U, V;
    cin >> S >> T >> U >> V;

    struct E{int u,v; ll w;};
    vector<E> edges(M);
    vector<vector<pair<int,ll>>> adj(N+1);
    for(int i=0;i<M;i++){
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        adj[edges[i].u].eb(edges[i].v, edges[i].w);
        adj[edges[i].v].eb(edges[i].u, edges[i].w);
    }

    auto dijkstra = [&](int src){
        vll dist(N+1, INF);
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
        dist[src] = 0;
        pq.emplace(0, src);
        while(!pq.empty()){
            auto [d,u] = pq.top(); pq.pop();
            if(d > dist[u]) continue;
            for(auto &pr : adj[u]){
                int v = pr.fi; ll w = pr.se;
                if(dist[v] > d + w){
                    dist[v] = d + w;
                    pq.emplace(dist[v], v);
                }
            }
        }
        return dist;
    };

    // 1) Dijkstra từ S, T
    vll distS = dijkstra(S);
    vll distT = dijkstra(T);
    ll bestST = distS[T];

    // 2) Build graph with free edges weight=0
    vector<vector<pair<int,ll>>> adj2(N+1);
    for(auto &e : edges){
        bool free_edge =
            (distS[e.u] + e.w + distT[e.v] == bestST) ||
            (distS[e.v] + e.w + distT[e.u] == bestST);
        ll w2 = free_edge ? 0 : e.w;
        adj2[e.u].eb(e.v, w2);
        adj2[e.v].eb(e.u, w2);
    }

    // 3) Dijkstra từ U trên adj2
    vll distU(N+1, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    distU[U] = 0;
    pq.emplace(0, U);
    while(!pq.empty()){
        auto [d,u] = pq.top(); pq.pop();
        if(d > distU[u]) continue;
        for(auto &pr : adj2[u]){
            int v = pr.fi; ll w = pr.se;
            if(distU[v] > d + w){
                distU[v] = d + w;
                pq.emplace(distU[v], v);
            }
        }
    }

    cout << distU[V] << el;
    return 0;
}

/*
⢀⡴⠑⡄⠀⠀⠀⠀⠀⠀⠀⣀⣀⣤⣤⣤⣀⡀      Monkey D. LUFFY
⠸⡇⠀⠿⡀⠀⣀⡴⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀   "I’m gonna be..."
⠀⠀⠀⠀⠑⢄⣾⣷⣶⣶⣶⣶⣶⣶⣶⣶⣶⣶⣶⣯⣍⠻⣷⡄   ...King of the Pirates!
⠀⠀⠀⠀⢀⡀⠁⠈⠙⠻⠿⠿⠿⠿⠿⠿⠿⠿⠿⠿⠿⠟⠋   ⠀
⠀⠀⠀⢀⡾⣁⣀⠀⠴⠂⠙⣗⡀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⣴⣷⠘⠿⠛⠃⠀⠀⠀⠉⠳⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣴⣿⠙⣆⠀⠀⠀⠀⠀⠀⠀⠈⠙⠒⠊⠁⠀⠀⠀⠀⠀
⢀⣼⣿⠀⣇⣀⠀⠀⣠⣤⣶⣾⣿⣶⣶⣶⣶⠆⠀⠀⠀⠀

*/

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