Submission #1110059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110059		sunboi	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	328 ms	22460 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
#define int long long

vector<vector<pair<int, int>>> g;
vector<int> dist, dist2, travelling;

const int INF = 1e18 + 7;


signed main(){
    int n, m; cin >> n >> m;
    int s, t; cin >> s >> t;
    int u, v; cin >> u >> v;
    
    g.resize(n + 1);
    dist.resize(n + 1, INF);
    dist2.resize(n + 1, INF);
    travelling.resize(n + 1, INF);
    for (int i = 0; i < m; i++){
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    
    priority_queue<pair<int, int>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while(!pq.empty()){
        int d = pq.top().first;
        int v = pq.top().second;
        
        pq.pop();
        
        if (dist[v] != -d) continue;
        
        for (auto [u, c] : g[v]){
            if (-d + c < dist[u]){
                pq.push({d - c, u});
                dist[u] = -d + c;
            }
        }
    }
    
    dist2[t] = 0;
    pq.push({0, t});
    while(!pq.empty()){
        int d = pq.top().first;
        int v = pq.top().second;
        
        pq.pop();
        
        if (dist2[v] != -d) continue;
        
        for (auto [u, c] : g[v]){
            if (-d + c < dist2[u]){
                pq.push({d - c, u});
                dist2[u] = -d + c;
            }
        }
    }
    
    travelling[u] = 0;
    pq.push({0, u});
    while(!pq.empty()){
        int d = pq.top().first;
        int v = pq.top().second;
        
        pq.pop();
        
        if (travelling[v] != -d) continue;
        
        for (auto [u, c] : g[v]){
            if (dist[u] + dist2[v] + c == dist[t]){
                
                if (-d < travelling[u]){
                    pq.push({d, u});
                    travelling[u] = -d;
                }
                
            }else if (dist[v] + dist2[u] + c == dist[t]){
                
                if (-d < travelling[u]){
                    pq.push({d, u});
                    travelling[u] = -d;
                }
                
            }else{
                if (-d + c < travelling[u]){
                    pq.push({d - c, u});
                    travelling[u] = -d + c;
                }
            }
        }
    }
    /*for (int i = 1; i <= n; i++){
        cout << dist[i] << ' ';
    }
    cout << endl;
    for (int i = 1; i <= n; i++){
        cout << dist2[i] << ' ';
    }
    cout << endl;*/
    cout << travelling[v] << endl;
    
    
    
    
    
}

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