Submission #1218027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218027		teslerpham	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	239 ms	35600 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'
#define int long long
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vll = vector<ll>;

const int INF = 1e18 + 7;
const int MOD = 1e9 + 7;

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

struct Edge { int v; ll w; };

signed main(){
    fastIO();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

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

    vector<tuple<int,int,ll>> edges;
    edges.reserve(M);
    vector<vector<Edge>> adj(N+1);
    for(int i = 0; i < M; i++){
        int A, B; ll C;
        cin >> A >> B >> C;
        edges.emplace_back(A,B,C);
        adj[A].push_back({B,C});
        adj[B].push_back({A,C});
    }

    auto dijkstra = [&](int src){
        vector<ll> 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 [du,u] = pq.top(); pq.pop();
            if(du > dist[u]) continue;
            for(auto &e: adj[u]){
                int v = e.v; ll w = e.w;
                if(dist[v] > du + w){
                    dist[v] = du + w;
                    pq.emplace(dist[v], v);
                }
            }
        }
        return dist;
    };

    // 1) Dijkstra từ S và T
    auto distS = dijkstra(S);
    auto distT = dijkstra(T);
    ll D = distS[T];

    // 2) đánh dấu “free” cạnh
    // build new graph with cost'=0 for free, else original
    vector<vector<Edge>> adj2(N+1);
    for(auto &ed: edges){
        int u,v; ll w;
        tie(u,v,w) = ed;
        bool free_edge = 
           (distS[u] + w + distT[v] == D) ||
           (distS[v] + w + distT[u] == D);
        ll w2 = free_edge ? 0 : w;
        adj2[u].push_back({v,w2});
        adj2[v].push_back({u,w2});
    }

    // 3) Dijkstra từ U trên đồ thị mới
    vector<ll> 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 [du,u] = pq.top(); pq.pop();
        if(du > distU[u]) continue;
        for(auto &e: adj2[u]){
            int v = e.v; ll w = e.w;
            if(distU[v] > du + w){
                distU[v] = du + w;
                pq.emplace(distU[v], v);
            }
        }
    }

    ll ans = distU[V];
    cout << ans << el;
    return 0;
}

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