Submission #915936

#	Time	Username	Problem	Language	Result	Execution time	Memory
915936		Github	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	306 ms	20864 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<int, int>>> graph;
int n, m;
int s, t;
int u, v;

vector<ll> dijstra(int st){
    vector<ll> dist(n, LLONG_MAX);
    dist[st] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, st});
    while (!pq.empty()){
        int c = pq.top().second; pq.pop();
        for (pair<int, int> p: graph[c]){
            if (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(int start, int end){
    vector<ll> dU(n, LLONG_MAX), dV(n, LLONG_MAX);
    vector<ll> dist(n, LLONG_MAX);
    priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
    pq.push({0, {start, 0}});
    dist[start] = 0;
    vector<bool> vis(n, false);
    while (!pq.empty()){
        int cdist = pq.top().first, cur = pq.top().second.first, par = pq.top().second.second; pq.pop();
        if (!vis[cur]){
            vis[cur] = true;
            dU[cur] = min(distU[cur], dU[par]);
            dV[cur] = min(distV[cur], dV[par]);
            for (pair<int, int> 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(dU[cur], dU[par]);
            dV[cur] = min(dV[cur], dV[par]);
            for (pair<int, int> p: graph[cur]){
                pq.push({cdist+p.second, {p.first, cur}});
            }
        }
    }
    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 (int i = 0; i < m; i++){
        int 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(a1, a2) << endl;
    return 0;
}

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