Submission #915950

#	Time	Username	Problem	Language	Result	Execution time	Memory
915950		Github	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	472 ms	29448 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <climits>
#include <cmath>
#include <set>
#include <algorithm>
#include <stack>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long

vector<ll> distU, distV;
vector<vector<pair<ll, ll>>> graph;
ll n, m;
ll s, t;
ll u, v;

vector<ll> dijstra(ll st){
    vector<ll> dist(n, LLONG_MAX/2);
    dist[st] = 0;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    pq.push({0, st});
    vector<bool> vis(n, false);
    while (!pq.empty()){
        ll c = pq.top().second; pq.pop();
        vis[c] = true;
        for (pair<ll, ll> p: graph[c]){
            if (!vis[p.first] && dist[p.first] > dist[c]+p.second){
                dist[p.first] = dist[c]+p.second;
                pq.push({dist[p.first], p.first});
            }
        }
    }
    return dist;
}


ll dijstra2(ll start, ll end){
    vector<ll> dU(n, LLONG_MAX/2), dV(n, LLONG_MAX/2);
    vector<ll> dist(n, LLONG_MAX/2);
    priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> pq;
    pq.push({0, {start, 0}});
    dist[start] = 0;
    vector<bool> vis(n, false);
    while (!pq.empty()){
        ll cdist = pq.top().first; ll cur = pq.top().second.first, par = pq.top().second.second; pq.pop();
        if (!vis[cur]){
            vis[cur] = true;
            dist[cur] = cdist;
            dU[cur] = min(distU[cur], dU[par]);
            dV[cur] = min(distV[cur], dV[par]);
            for (pair<ll, ll> p: graph[cur]){
                pq.push({cdist+p.second, {p.first, cur}});
            }
        }else if (cdist == dist[cur] && min(dU[par], distU[cur])+min(dV[par], distV[cur]) <= dU[cur]+dV[cur]){
            dU[cur] = min(distU[cur], dU[par]);
            dV[cur] = min(distV[cur], dV[par]);
        }
    }
    return dU[end]+dV[end];
}

int main(){
    speedup
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    graph.resize(n);
    s--, t--, u--, v--;
    for (ll i = 0; i < m; i++){
        ll a, b, w; cin >> a >> b >> w;
        a--, b--;
        graph[a].push_back({b, w});
        graph[b].push_back({a, w});
    }
    distU = dijstra(u);
    distV = dijstra(v);
    ll a1 = dijstra2(s, t);
    ll a2 = dijstra2(t, s);
    cout << min(distU[v], min(a1, a2)) << endl;
    return 0;
}

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