Submission #714164

#	Time	Username	Problem	Language	Result	Execution time	Memory
714164		gaga999	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	333 ms	24164 KiB

commuter_pass

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

const long long INF = 1ll << 60;
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