제출 #1268027

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

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll INF = 2e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v;
    vector<vector<pll>> g(n + 1);
    while (m--) {
        ll u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<ll> d(n + 1, INF), p(n + 1, -1); d[s] = 0; p[s] = s;
    set<pll> q; for (ll u = 1; u <= n; u++) q.insert({ d[u], u });

    while (!q.empty()) {
        auto [_, u] = *q.begin();
        q.erase(q.begin());

        for (auto [v, w]: g[u]) 
            if (d[u] + w < d[v]) {
                q.erase(q.find({d[v], v}));
                d[v] = d[u] + w;
                p[v] = u;
                q.insert({d[v], v});
            }
    }

    vector<ll> path;

    ll curr = t;
    while (curr != p[curr]) {
        path.push_back(curr);
        curr = p[curr];
    }
    path.push_back(curr);

    reverse(path.begin(), path.end());

    set<pll> zeros;
    for (ll i = 1; i < path.size(); i++)
        zeros.insert({path[i], path[i - 1]}),
        zeros.insert({path[i - 1], path[i]});

    vector<vector<pll>> g2(n + 1);
    for (ll u = 1; u <= n; u++) 
        for (auto [v, w]: g[u])
            if (zeros.count({u, v})) g2[u].push_back({v, 0});
            else g2[u].push_back({v, w});

    vector<ll> d2(n + 1, INF); d2[u] = 0;
    set<pll> q2; for (ll u = 1; u <= n; u++) q2.insert({d2[u], u});

    while (!q2.empty()) {
        auto [_, u] = *q2.begin();
        q2.erase(q2.begin());

        for (auto [v, w]: g2[u])
            if (d2[u] + w < d2[v]) {
                q2.erase(q2.find({d2[v], v}));
                d2[v] = d2[u] + w;
                q2.insert({d2[v], v});
            }
    }

    cout << d2[v];
}

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