Submission #482068

#	Time	Username	Problem	Language	Result	Execution time	Memory
482068		bill_lin	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	227 ms	19372 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
 
const ll INF = 1e15;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;
    
    vector<vector<pii>> adj(n + 1);
    
    for (int i = 0; i < m; i++) {
        int u, v, cost;
        cin >> u >> v >> cost;
        adj[u].push_back({v, cost});
        adj[v].push_back({u, cost});
    }
    
    priority_queue<pll, vector<pll>, greater<pll>> q;
    
    vector<ll> dist(n + 1, INF);
    vector<int> par(n + 1, -1);
    dist[S] = 0;
    q.push({0, S});
    
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        
        ll curr_cost = p.first, node = p.second;
        for (pii &edge : adj[node]) {
            int dest = edge.first, edge_cost = edge.second;
            if (dist[dest] > curr_cost + edge_cost) {
                par[dest] = node;
                dist[dest] = curr_cost + edge_cost;
                q.push({dist[dest], dest});
            }
        }
    }
    
    // find the edges included in the shortest path
    int curr = T;
    while (curr != S) {
        adj[curr].push_back({par[curr], 0});
        adj[par[curr]].push_back({curr, 0});
        curr = par[curr];
    }
    
    // run dijkstra again
    dist = vector<ll>(n + 1, INF);
    dist[U] = 0;
    q.push({0, U});
    
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        
        ll curr_cost = p.first, node = p.second;
        for (pii &edge : adj[node]) {
            int dest = edge.first, edge_cost = edge.second;
            if (dist[dest] > curr_cost + edge_cost) {
                dist[dest] = curr_cost + edge_cost;
                q.push({dist[dest], dest});
            }
        }
    }
    
    cout << dist[V] << '\n';
}

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