제출 #1158697

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

commuter_pass

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

const int N = 1e5 + 10;
vector< pair<int, int> > g[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;
    
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    
    long long d[n + 1];
    long long p[n + 1];
    for (int i = 0; i <= n; i++) {
        d[i] = 1e18;
        p[i] = -1;
    }
    d[S] = 0;
    set< pair<long long, int> > q;
    q.emplace(0, S);
    while (!q.empty()) {
        auto [mn, v] = *q.begin();
        q.erase(q.begin());
        
        for (auto [to, w] : g[v]) {
            if (d[to] > d[v] + w) {
                q.erase({d[to], to});
                d[to] = d[v] + w;
                p[to] = v;
                q.emplace(d[to], to);
            }
        }
    }
    
    for (int i = T, j = -1; i != -1; j = i, i = p[i]) {
        for (auto &to : g[i]) {
            if (to.first == p[i]) {
                to.second = 0;
            }
            if (to.first == j) {
                to.second = 0;
            }
        }
    }
    
    for (int i = 0; i <= n; i++) d[i] = 1e18;
    d[U] = 0;
    q.emplace(0, U);
    while (!q.empty()) {
        auto [mn, v] = *q.begin();
        q.erase(q.begin());
        
        for (auto [to, w] : g[v]) {
            if (d[to] > d[v] + w) {
                q.erase({d[to], to});
                d[to] = d[v] + w;
                q.emplace(d[to], to);
            }
        }
    }
    cout << d[V];

    return 0;
}

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