Submission #1069599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069599		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++11	0 / 100	139 ms	262144 KiB

commuter_pass

#include <iostream>
#include <climits>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;

int main() {
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    ll w[n+1][n+1];

    vector<ll> adj[n+1];
    while (m--) {
        ll a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back(b);
        adj[b].push_back(a);
        w[a][b] = c;
        w[b][a] = c;
    }

    ll d[n+1], p[n+1];
    bool c[n+1];
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> heap;
    for (ll i=1; i<=n; i++) {
        d[i] = LLONG_MAX;
        c[i] = false;
        p[i] = -1;
    }

    d[s] = 0;
    heap.push({0, s});
    while (!heap.empty()) {
        pair<ll, ll> t = heap.top();
        heap.pop();
        if (!c[t.second]) {
            c[t.second] = true;
            for (ll x : adj[t.second]) {
                if (d[x] > d[t.second]+w[t.second][x]) {
                    d[x] = d[t.second]+w[t.second][x];
                    p[x] = t.second;
                    heap.push({d[x], x});
                }
            }
        }
    }

    ll temp = t;
    while (p[temp] != -1) {
        w[temp][p[temp]] = 0;
        w[p[temp]][temp] = 0;
        temp = p[temp];
    }
    
    for (ll i=1; i<=n; i++) {
        d[i] = LLONG_MAX;
        c[i] = false;
        p[i] = -1;
    }

    d[u] = 0;
    heap.push({0, u});
    while (!heap.empty()) {
        pair<ll, ll> t = heap.top();
        heap.pop();
        if (!c[t.second]) {
            c[t.second] = true;
            for (ll x : adj[t.second]) {
                if (d[x] > d[t.second]+w[t.second][x]) {
                    d[x] = d[t.second]+w[t.second][x];
                    p[x] = t.second;
                    heap.push({d[x], x});
                }
            }
        }
    }

    cout << d[v];
}

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