제출 #1167388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167388		GoBananas69	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	177 ms	25972 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
typedef long long ll;
using namespace std;

const ll inf = 1e18;

vector<vector<pair<ll, ll>>> adj;
vector<ll> du, dv;
vector<ll> p, path;

vector<bool> vis;

void dijkstra(ll s, vector<ll> &dist) {
    fill(vis.begin(), vis.end(), false);
    priority_queue<pair<ll, ll>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        ll u = pq.top().second;
        // ll w = pq.top().first;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto &p: adj[u]) {
            ll v = p.first;
            ll w = p.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }
}

void find(ll s, ll t) {
    vector<ll> dist(adj.size(), inf);
    fill(vis.begin(), vis.end(), false); 
    priority_queue<pair<ll, ll>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        ll u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto &e: adj[u]) {
            ll v = e.first;
            ll w = e.second;
            if (dist[v] > dist[u] + w) {
                p[v] = u;
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }
    for (ll v = t; v != s; v = p[v]) {
        path.push_back(v);
    }
    path.push_back(s);
    reverse(path.begin(), path.end());
}

signed main() {
    //this solution assumes only one unique minimum path from s to t
    cin.tie() -> sync_with_stdio(0);
    ll n, m, s, t, a, b;
    cin >> n >> m >> s >> t >> a >> b;
    adj.resize(n + 1);
    dv.resize(n + 1, inf);
    du.resize(n + 1, inf);
    p.resize(n + 1, -1);
    vis.resize(n + 1);
    for (ll i = 0; i<m; ++i) {
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    find(s, t);
    for (ll i = 1; i<path.size(); ++i) {
        ll u = path[i - 1];
        ll v = path[i];
        adj[u].push_back({v, 0});
        adj[v].push_back({u, 0});
    }
    // cout << '\n';

    dijkstra(a, du);
    dijkstra(b, dv);
    cout << min(du[b], dv[a]) << '\n';
}

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