Submission #676402

#	Time	Username	Problem	Language	Result	Execution time	Memory
676402		borisAngelov	Commuter Pass (JOI18_commuter_pass)	C++11	0 / 100	331 ms	23884 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;

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(ds, ds + maxn, inf);

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

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

        pq.pop();

        if (ds[node] < curr) continue;

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

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

                dp[0][v] = min(du[v], dp[0][node]);
                dp[1][v] = min(dv[v], dp[1][node]);
            }
            else if (ds[v] == path)
            {
                if (min(du[v], dp[0][node]) + min(dv[v], dp[1][node]) <= dp[0][node] + dp[1][node])
                {
                    dp[0][node] = min(du[v], dp[0][node]);
                    dp[1][node] = min(dv[v], dp[1][node]);
                }
            }
        }
    }

    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:38:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         for (auto [v, w] : g[node])
      |                   ^
commuter_pass.cpp: In function 'void dijkstra2(long long int, long long int)':
commuter_pass.cpp:69:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         for (auto [v, w] : g[node])
      |                   ^

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