Submission #575352

#	Time	Username	Problem	Language	Result	Execution time	Memory
575352		four_specks	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	410 ms	31372 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';

    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(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[b].push_back(a);
                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 (int k : {0, 1})
        {
            vector<int> deg(n);
            for (int i = 0; i < n; i++)
            {
                for (int j : gr[i])
                    deg[j]++;
            }

            vector<long> dp = dist_u;
            queue<int> q;
            for (q.push(s); !q.empty();)
            {
                int a = q.front();
                q.pop();

                res = min(res, dp[a] + dist_v[a]);

                // cerr << a << ' ' << dp[a] << ' ' << dist_v[a] << '\n';

                for (int b : gr[a])
                {
                    dp[b] = min(dp[b], dp[a]);
                    if (--deg[b] == 0)
                        q.push(b);
                }
            }

            // cerr << '\n';

            swap(u, v), swap(dist_u, dist_v);
        }
    }

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

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

    solve();

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:131:18: warning: unused variable 'k' [-Wunused-variable]
  131 |         for (int k : {0, 1})
      |                  ^

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