Submission #676406

#	Time	Username	Problem	Language	Result	Execution time	Memory
676406		borisAngelov	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	357 ms	26612 KiB

commuter_pass

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

const int maxn = 100005;
const long long inf = (1LL << 62);

vector<pair<long long, long long>> g[maxn];

long long du[maxn];
long long dv[maxn];
long long ds[maxn];
long long dp[2][maxn];
long long ans = 0;

bool visited[maxn];

void dijkstra1(long long start_node, long long dist[])
{
    fill(dist, dist + maxn, inf);

    priority_queue<pair<long long, long long>> pq;
    pq.push({0, start_node});

    dist[start_node] = 0;

    while (!pq.empty())
    {
        long long curr = -pq.top().first;
        long long node = pq.top().second;

        pq.pop();

        if (dist[node] < curr) continue;

        for (auto [v, w] : g[node])
        {
            long long path = curr + w;

            if (dist[v] > path)
            {
                dist[v] = path;
                pq.push({-path, v});
            }
        }
    }
}

void dijkstra2(long long beg_node, long long end_node)
{
    fill(dp[0], dp[0] + maxn, inf);
    fill(dp[1], dp[1] + maxn, inf);
    fill(visited, visited + maxn, 0);

    priority_queue<pair<long long, pair<long long, long long>>> pq;
    pq.push({0, {beg_node, 0}});

    dp[0][0] = dp[1][0] = inf;

    while (!pq.empty())
    {
        long long curr = -pq.top().first;
        long long node = pq.top().second.first;
        long long par = pq.top().second.second;

        pq.pop();

        if (!visited[node])
        {
            visited[node] = true;
            ds[node] = curr;

            dp[0][node] = min(du[node], dp[0][par]);
            dp[1][node] = min(dv[node], dp[1][par]);

            for (auto [v, w] : g[node])
            {
                if (!visited[v])
                {
                    pq.push({-curr - w, {v, node}});
                }
            }
        } else if (curr == ds[node])
        {
            if (min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <= dp[0][node] + dp[1][node])
            {
                dp[0][node] = min(du[node], dp[0][par]);
                dp[1][node] = min(dv[node], dp[1][par]);
            }
        }
    }

    ans = min(ans, dp[0][end_node] + dp[1][end_node]);
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    long long n, m, s, t, u, v;

    cin >> n >> m >> s >> t >> u >> v;

    for (int i = 1; i <= m; ++i)
    {
        long long x, y, w;
        cin >> x >> y >> w;

        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }

    dijkstra1(u, du);
    dijkstra1(v, dv);

    ans = du[v];

    dijkstra2(s, t);
    dijkstra2(t, s);

    cout << ans << endl;

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int*)':
commuter_pass.cpp:40:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         for (auto [v, w] : g[node])
      |                   ^
commuter_pass.cpp: In function 'void dijkstra2(long long int, long long int)':
commuter_pass.cpp:80:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |             for (auto [v, w] : g[node])
      |                       ^

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