제출 #833457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833457		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	485 ms	27704 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>

const ll inf = 1e18;
const int maxn = 100005;
// const int maxn = 50;
int n, m, s, t, u, v;

pll dist[maxn]; // <parent, dist>
priority_queue<pll, vector<pll>, greater<pll>> pq;
map<int, int> adj[maxn];

int main() {
    for (int i = 0; i < maxn; i++) {
        dist[i] = {-1, inf};
    }

    cin >> n >> m >> s >> t >> u >> v;

    for (int i = 0; i < m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        adj[a][b] = c;
        adj[b][a] = c;
    }

    pq.push({0, s});
    dist[s] = {s, 0};

    while (!pq.empty()) {
        auto [currdist, idx] = pq.top();

        for (auto [b, c] : adj[idx]) {
            if (currdist + c < dist[b].second) { // potential?
                dist[b] = {idx, currdist + c};
                pq.push({currdist+c, b});
            } 
        }

        pq.pop(); 
    }

    int x = t;
    while (x != s) {
        adj[x][dist[x].first] = 0;
        adj[dist[x].first][x] = 0;
        x = dist[x].first;
    }

    for (int i = 0; i < maxn; i++) {
        dist[i] = {-1, inf};
    }

    pq.push({0, u});
    dist[u] = {u, 0};

    while (!pq.empty()) {
        auto [currdist, idx] = pq.top();

        for (auto [b, c] : adj[idx]) {
            if (currdist + c < dist[b].second) { // potential?
                dist[b] = {idx, currdist + c};
                pq.push({currdist+c, b});
            } 
        }

        pq.pop(); 
    }

    cout << dist[v].second << endl;

    return 0;
}

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