Submission #711991

#	Time	Username	Problem	Language	Result	Execution time	Memory
711991		Macker	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	489 ms	24088 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <math.h>
#include <tuple>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>
#include <climits>
#include <fstream>

using namespace std;
typedef long long ll;
#define all(v) v.begin(). v.end()

vector < vector<tuple<ll, ll>>> adj; // [node from], [i] -> {node to, cost}
ll du[100001], dv[100001], ds[100001], dpU[100001], dpV[100001];
ll ans;

void dijkstra1(ll s, ll dist[]) {
    priority_queue<tuple<ll, ll>, vector<tuple<ll, ll>>, greater<tuple<ll, ll>>> pq;
    fill(dist, dist + 100001, LLONG_MAX);
    pq.push({ 0, s });
    dist[s] = 0;
    while (!pq.empty()) {
        ll a, d; tie(d, a) = pq.top(); pq.pop();
        if (dist[a] != d) continue;
        for (auto i : adj[a]) {
            ll b, c; tie(b, c) = i;
            if (dist[b] > dist[a] + c) {
                dist[b] = dist[a] + c;
                pq.push({ dist[b], b });
            }
        }
    }
}

void dijkstra2(ll s, ll e) {
    priority_queue<tuple<ll, ll>, vector<tuple<ll, ll>>, greater<tuple<ll, ll>>> pq;
    fill(dpV, dpV + 100001, LLONG_MAX);
    fill(dpU, dpU + 100001, LLONG_MAX);
    fill(ds, ds + 100001, LLONG_MAX);
    pq.push({ 0, s });
    ds[s] = 0;
    dpV[s] = dv[s];
    dpU[s] = du[s];
    while (!pq.empty()) {
        ll d, a; tie(d, a) = pq.top(); pq.pop();
        if (ds[a] != d) continue;
        for (auto i : adj[a]) {
            ll b, c; tie(b, c) = i;
            if (ds[b] > ds[a] + c) {
                dpV[b] = min(dpV[a], dv[b]);
                dpU[b] = min(dpU[a], du[b]);
                ds[b] = ds[a] + c;
                pq.push({ ds[b], b });
            }
            else if (ds[b] == ds[a] + c && min(dpU[a], du[b]) + min(dpV[a], dv[b]) <= dpV[b] + dpU[b]) {
                dpV[b] = min(dpV[a], dv[b]);
                dpU[b] = min(dpU[a], du[b]);
            }
        }
    }

    ans = min(ans, dpV[e] + dpU[e]);
}

int main()
{
    ll n, m; cin >> n >> m;
    ll s, t; cin >> s >> t;
    ll u, v; cin >> u >> v;
    adj.resize(n+1);
    for (ll i = 0; i < m; i++)
    {
        ll a, b, c; cin >> a >> b >> c;
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }

    dijkstra1(u, du);
    dijkstra1(v, dv);

    ans = du[v];

    dijkstra2(s, t);
    dijkstra2(t, s);

    cout << ans << endl;
}

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