Submission #1308125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308125		dimitris71	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	180 ms	23064 KiB

commuter_pass

#include <iostream>  
#include <vector>  
#include <queue>  
#include <algorithm>  
  
using namespace std;  
  
typedef long long ll;  
const ll INF = 1e16; // Προσοχή στο INF για να μην έχουμε overflow  
  
struct Edge {  
    int to;  
    ll weight;  
};  
  
struct Node {  
    int id;  
    ll dist;  
    bool operator>(const Node& other) const {  
        return dist > other.dist;  
    }  
};  
  
int N, M;  
vector<Edge> adj[100005];  
  
void dijkstra(int start, vector<ll>& dists) {  
    dists.assign(N + 1, INF);  
    priority_queue<Node, vector<Node>, greater<Node>> pq;  
    dists[start] = 0;  
    pq.push({start, 0});  
    while (!pq.empty()) {  
        Node curr = pq.top(); pq.pop();  
        if (curr.dist > dists[curr.id]) continue;  
        for (auto& e : adj[curr.id]) {  
            if (dists[curr.id] + e.weight < dists[e.to]) {  
                dists[e.to] = dists[curr.id] + e.weight;  
                pq.push({e.to, dists[e.to]});  
            }  
        }  
    }  
}  
  
int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(NULL);  
  
    int s, t, a, b;  
    if (!(cin >> N >> M)) return 0;  
    cin >> s >> t >> a >> b;  
  
    for (int i = 0; i < M; i++) {  
        int u, v; ll c;  
        cin >> u >> v >> c;  
        adj[u].push_back({v, c});  
        adj[v].push_back({u, c});  
    }  
  
    // 4 Dijkstra για να ξέρουμε αποστάσεις από όλα τα κρίσιμα σημεία  
    vector<ll> dS, dT, dA, dB;  
    dijkstra(s, dS);  
    dijkstra(t, dT);  
    dijkstra(a, dA);  
    dijkstra(b, dB);  
  
    ll minST = dS[t];  
    ll result = dA[b]; // Αρχική τιμή: το απλό συντομότερο a-b  
  
    // Δημιουργούμε ένα DAG με τις ακμές που ανήκουν σε συντομότερα s-t μονοπάτια  
    vector<int> dag_adj[100005];  
    vector<int> in_degree(N + 1, 0);  
    for (int u = 1; u <= N; u++) {  
        for (auto& e : adj[u]) {  
            if (dS[u] + e.weight + dT[e.to] == minST) {  
                dag_adj[u].push_back(e.to);  
                in_degree[e.to]++;  
            }  
        }  
    }  
  
    // DP πάνω στο DAG για να βρούμε το μέγιστο "κέρδος" (δωρεάν διαδρομή)  
    // d_overlap[u]: η ελάχιστη απόσταση από το 'a' στο 'u' αν χρησιμοποιήσουμε  
    // ένα τμήμα του s-t μονοπατιού που καταλήγει στο u.  
    vector<ll> dp_a(N + 1, INF), dp_b(N + 1, INF);  
      
    // Τοπική ταξινόμηση (Topological Sort) για το DAG  
    queue<int> q;  
    for (int i = 1; i <= N; i++) if (in_degree[i] == 0) q.push(i);  
  
    while (!q.empty()) {  
        int u = q.front(); q.pop();  
          
        // Η απόσταση στο u μπορεί να είναι η απευθείας από το 'a'  
        // ή να συνεχίζει από έναν προκάτοχο στο DAG με κόστος 0  
        dp_a[u] = min(dp_a[u], dA[u]);  
        dp_b[u] = min(dp_b[u], dB[u]);  
          
        result = min(result, dp_a[u] + dB[u]);  
        result = min(result, dp_b[u] + dA[u]);  
  
        for (int v : dag_adj[u]) {  
            dp_a[v] = min(dp_a[v], dp_a[u]);  
            dp_b[v] = min(dp_b[v], dp_b[u]);  
            if (--in_degree[v] == 0) q.push(v);  
        }  
    }  
  
    cout << result << endl;  
  
    return 0;  
}  

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