Submission #1308124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308124		dimitris71	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	351 ms	27580 KiB

commuter_pass

#include <bits/stdc++.h>  
using namespace std;  
  
using ll = long long;  
const ll INF = (1LL<<62);  
  
struct EdgeIn { int u, v, w; };  
  
static vector<pair<int,int>> g[1000000];       
static vector<int> dag[1000000];               
static vector<int> rdag[1000000];              
  
vector<ll> dijkstra(int N, int src) {  
    vector<ll> dist(N+1, INF);  
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;  
    dist[src] = 0;  
    pq.push({0, src});  
  
    while (!pq.empty()) {  
        pair<ll,int> top = pq.top(); pq.pop();  
        ll d = top.first;  
        int u = top.second;  
        if (d != dist[u]) continue;  
        for (size_t i = 0; i < g[u].size(); i++) {  
            int v = g[u][i].first;  
            int w = g[u][i].second;  
            ll nd = d + w;  
            if (nd < dist[v]) {  
                dist[v] = nd;  
                pq.push({nd, v});  
            }  
        }  
    }  
    return dist;  
}  
  
void bfs_reach(int N, int start, vector<char>& vis, vector<int> adj[]) {  
    deque<int> dq;  
    vis.assign(N+1, 0);  
    vis[start] = 1;  
    dq.push_back(start);  
    while (!dq.empty()) {  
        int u = dq.front(); dq.pop_front();  
        for (int v : adj[u]) {  
            if (!vis[v]) {  
                vis[v] = 1;  
                dq.push_back(v);  
            }  
        }  
    }  
}  
  
int main() {  
  
    int N, M;  
    cin >> N >> M;  
    int s, t; cin >> s >> t;  
    int a, b; cin >> a >> b;  
  
    vector<EdgeIn> edges;  
    edges.reserve(M);  
  
    for (int i = 0; i < M; i++) {  
        int u, v, w;  
        cin >> u >> v >> w;  
        edges.push_back({u, v, w});  
        g[u].push_back({v, w});  
        g[v].push_back({u, w});  
    }  
  
    vector<ll> distS = dijkstra(N, s);  
    vector<ll> distT = dijkstra(N, t);  
    vector<ll> distA = dijkstra(N, a);  
    vector<ll> distB = dijkstra(N, b);  
  
    ll D = distS[t];  
  
    vector<char> candidate(N+1, 0);  
    for (int v = 1; v <= N; v++) {  
        if (distS[v] != INF && distT[v] != INF && distS[v] + distT[v] == D)  
            candidate[v] = 1;  
    }  
  
    for (int i = 1; i <= N; i++) { dag[i].clear(); rdag[i].clear(); }  
  
    for (auto &e : edges) {  
        int u = e.u, v = e.v, w = e.w;  
        if (!candidate[u] || !candidate[v]) continue;  
  
        if (distS[u] + (ll)w == distS[v]) {  
            dag[u].push_back(v);  
            rdag[v].push_back(u);  
        }  
        if (distS[v] + (ll)w == distS[u]) {  
            dag[v].push_back(u);  
            rdag[u].push_back(v);  
        }  
    }  
  
    vector<char> reachFromS, reachToT;  
    bfs_reach(N, s, reachFromS, dag);  
    bfs_reach(N, t, reachToT, rdag);  
  
    vector<char> good(N+1, 0);  
    for (int v = 1; v <= N; v++) {  
        if (candidate[v] && reachFromS[v] && reachToT[v]) good[v] = 1;  
    }  
  
    vector<int> nodes;  
    nodes.reserve(N);  
    for (int v = 1; v <= N; v++) if (good[v]) nodes.push_back(v);  
  
    sort(nodes.begin(), nodes.end(), [&](int x, int y){  
        if (distS[x] != distS[y]) return distS[x] < distS[y];  
        return x < y;  
    });  
  
    vector<ll> bestA(N+1, INF), bestB(N+1, INF);  
  
    for (int v : nodes) {  
        bestA[v] = distA[v];  
        bestB[v] = distB[v];  
    }  
  
    for (int u : nodes) {  
        if (bestA[u] < INF) {  
            for (int v : dag[u]) if (good[v]) {  
                if (bestA[u] < bestA[v]) bestA[v] = bestA[u];  
            }  
        }  
        if (bestB[u] < INF) {  
            for (int v : dag[u]) if (good[v]) {  
                if (bestB[u] < bestB[v]) bestB[v] = bestB[u];  
            }  
        }  
    }  
  
    ll ans = INF;  
    for (int v : nodes) {  
        if (bestA[v] < INF && distB[v] < INF) ans = min(ans, bestA[v] + distB[v]);  
        if (bestB[v] < INF && distA[v] < INF) ans = min(ans, bestB[v] + distA[v]);  
    }  
      
    ans = min(ans, distA[b]);  
    cout << ans << "\n";  
    return 0;  
}  

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