Submission #705341

#	Time	Username	Problem	Language	Result	Execution time	Memory
705341		GrandTiger1729	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	299 ms	27936 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const long long INF = 1e18;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    int S, T, U, V; cin >> S >> T >> U >> V;
    S--, T--, U--, V--;
    vector<vector<pair<int, long long>>> g(n);
    for (int i = 0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    auto dijkstra = [&](int s){
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        pq.emplace(0, s);
        vector<long long> dis(n, INF);
        dis[s] = 0;
        vector<bool> vis(n);
        while (pq.size()){
            auto [d, u] = pq.top();
            pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (auto &[v, w]: g[u]){
                if (dis[v] > dis[u] + w){
                    dis[v] = dis[u] + w;
                    pq.emplace(dis[v], v);
                }
            }
        }
        return dis;
    };
    auto disU = dijkstra(U), disV = dijkstra(V);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.emplace(0, S);
    vector<long long> dis(n, INF);
    dis[S] = 0;
    vector<bool> vis(n);
    vector<vector<int>> stk(n);
    vector<long long> ans(n, INF), minU(n, INF), minV(n, INF);
    while (pq.size()){
        auto [d, u] = pq.top();
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        minU[u] = disU[u], minV[u] = disV[u];
        for (auto &v: stk[u]){
            ans[u] = min(ans[u], ans[v]);
            minU[u] = min(minU[u], minU[v]);
            minV[u] = min(minV[u], minV[v]);
        }
        ans[u] = min({ans[u], minU[u] + disV[u], minV[u] + disU[u]});
        for (auto &[v, w]: g[u]){
            if (dis[v] > dis[u] + w){
                stk[v].clear();
                stk[v].push_back(u);
                dis[v] = dis[u] + w;
                pq.emplace(dis[v], v);
            }else if (dis[v] == dis[u] + w){
                stk[v].push_back(u);
            }
        }
    }
    cout << min(ans[T], disU[V]) << '\n';
    return 0;
}

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