Submission #575199

#	Time	Username	Problem	Language	Result	Execution time	Memory
575199		four_specks	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	443 ms	47028 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

inline namespace
{
} // namespace

void solve()
{
    int n, m;
    cin >> n >> m;

    int s, t, u, v;
    cin >> s >> t >> u >> v, --s, --t, --u, --v;

    // cerr << s << ' ' << t << '\n';
    // cerr << u << ' ' << v << '\n';
    // swap(u, v);

    vector<vector<pair<int, long>>> adj(n);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        long c;
        cin >> a >> b >> c, --a, --b;

        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    vector<vector<int>> gr_fw(n), gr_bk(n);
    {
        vector<long> dist(n, LONG_MAX);
        priority_queue<pair<long, int>> pq;
        vector<vector<int>> gr1(n);
        vector<vector<int>> todo(n);
        dist[s] = 0;
        for (pq.emplace(-dist[s], s); !pq.empty();)
        {
            auto [d, a] = pq.top();
            pq.pop();

            if (d != -dist[a])
                continue;

            for (int b : todo[a])
                gr1[a].push_back(b);

            for (auto [b, c] : adj[a])
            {
                if (dist[a] + c < dist[b])
                {
                    todo[b].clear(),
                    todo[b].push_back(a);

                    dist[b] = dist[a] + c;
                    pq.emplace(-dist[b], b);
                }
                else if (dist[a] + c == dist[b])
                    todo[b].push_back(a);
            }
        }

        queue<int> q;
        vector<bool> done(n, 0);
        for (q.push(t); !q.empty();)
        {
            int a = q.front();
            q.pop();

            if (done[a])
                continue;

            done[a] = 1;

            for (int b : gr1[a])
            {
                gr_fw[b].push_back(a), gr_bk[a].push_back(b);
                q.push(b);
            }
        }
    }
    long res = LONG_MAX;
    {
        vector<long> dist_u(n, LONG_MAX), dist_v(n, LONG_MAX);
        {
            priority_queue<pair<long, int>> pq;
            dist_u[u] = 0;
            for (pq.emplace(-dist_u[u], u); !pq.empty();)
            {
                auto [d, a] = pq.top();
                pq.pop();

                if (d != -dist_u[a])
                    continue;

                for (auto [b, c] : adj[a])
                {
                    if (dist_u[a] + c < dist_u[b])
                    {
                        dist_u[b] = dist_u[a] + c;
                        pq.emplace(-dist_u[b], b);
                    }
                }
            }
        }
        {
            priority_queue<pair<long, int>> pq;
            dist_v[v] = 0;
            for (pq.emplace(-dist_v[v], v); !pq.empty();)
            {
                auto [d, a] = pq.top();
                pq.pop();

                if (d != -dist_v[a])
                    continue;

                for (auto [b, c] : adj[a])
                {
                    if (dist_v[a] + c < dist_v[b])
                    {
                        dist_v[b] = dist_v[a] + c;
                        pq.emplace(-dist_v[b], b);
                    }
                }
            }
        }

        res = dist_u[v];

        for (auto [gr, k] : {pair(gr_fw, s), pair(gr_bk, t)})
        {
            vector<int> deg(n);
            for (int i = 0; i < n; i++)
            {
                for (int j : gr[i])
                    deg[j]++;
            }

            queue<int> q;
            vector<long> dp_u = dist_u, dp_v = dist_v;
            for (q.push(k); !q.empty();)
            {
                int a = q.front();
                q.pop();

                // cerr << a << ' ' << dist_u[a] << '\n';

                for (int b : gr[a])
                {
                    dp_u[b] = min(dist_u[b], dp_u[a]),
                    dp_v[b] = min(dist_v[b], dp_v[a]);
                    res = min(res, dp_u[b] + dp_v[b]);
                    if (--deg[b] == 0)
                        q.push(b);
                }
            }
        }

        // cerr << dp_u[v] << '\n';

        // res = min(res, dp_u[t] + dp_v[t]);
    }

    cout << res << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

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