Submission #1246385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246385		nlsosad	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	196 ms	21400 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll LINF = (ll)4e18;

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

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

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

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

    auto d_s = dijkstra(S);
    auto d_u = dijkstra(U);
    auto d_v = dijkstra(V);

    // Xây DAG của tất cả cạnh (u->v) thỏa d_s[u]+w = d_s[v]
    vector<vector<int>> dag(N+1);
    vector<int> indeg(N+1, 0);
    for(int u=1;u<=N;u++){
        for(auto &e : adj[u]){
            int v = e.to; ll w = e.w;
            if(d_s[u] + w == d_s[v]){
                dag[u].push_back(v);
                indeg[v]++;
            }
        }
    }

    // Topo-sort
    queue<int> q;
    for(int i=1;i<=N;i++) 
        if(indeg[i]==0) q.push(i);

    vector<int> ord;
    while(!q.empty()){
        int u = q.front(); q.pop();
        ord.push_back(u);
        for(int v: dag[u]){
            if(--indeg[v]==0) 
                q.push(v);
        }
    }

    // DP tìm answer
    vector<ll> best_u(N+1, LINF);
    ll answer = d_u[V];  // trường hợp không dùng vé tháng
    for(int v: ord){
        best_u[v] = min(best_u[v], d_u[v]);
        answer = min(answer, best_u[v] + d_v[v]);
        for(int w: dag[v]){
            best_u[w] = min(best_u[w], best_u[v]);
        }
    }

    cout << answer << "\n";
    return 0;
}

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