Submission #1309766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309766		wojtekmal	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	208 ms	21744 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

struct Edge
{
    int node;
    int64_t len;
};

struct DijkstraEdge
{
    int node;
    int prev;
    int64_t dist;
};

int n, m;
int s, t, u, v;
constexpr int array_size = 100'001;
array<vector<Edge>, array_size> neigh;
array<int64_t, array_size> s_dists;
array<int64_t, array_size> t_dists;
array<int64_t, array_size> u_dists;
array<int64_t, array_size> v_dists;
array<int64_t, array_size> min_dist_u;
array<int64_t, array_size> min_dist_v;
array<bool, array_size> visited;

struct CompareDijkstraEdge
{
    bool operator()(DijkstraEdge a, DijkstraEdge b)
    {
        return a.dist > b.dist;
    }
};

void do_dijkstra(int start_node, array<int64_t, array_size>& dists, bool fill_mins = false)
{
    visited.fill(false);
    priority_queue<DijkstraEdge, vector<DijkstraEdge>, CompareDijkstraEdge> line;
    line.push({start_node, 0, 0});

    while (!line.empty())
    {
        int node = line.top().node;
        int prev = line.top().prev;
        int64_t dist = line.top().dist;
        line.pop();

        if (fill_mins && (!visited[node] || dist == dists[node]))
        {
            min_dist_u[node] = min({min_dist_u[prev], min_dist_u[node], u_dists[node]});
            min_dist_v[node] = min({min_dist_v[prev], min_dist_v[node], v_dists[node]});
        }

        if (visited[node]) continue;
        dists[node] = dist;
        visited[node] = true;

        for (Edge e : neigh[node])
        {
            if (visited[e.node]) continue;
            line.push({e.node, node, dist + e.len});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    for (int i = 0; i < m; i++)
    {
        int a, b;
        int64_t c;
        cin >> a >> b >> c;
        neigh[a].push_back({b, c});
        neigh[b].push_back({a, c});
    }

    min_dist_u.fill(LLONG_MAX);
    min_dist_v.fill(LLONG_MAX);

    do_dijkstra(u, u_dists);
    do_dijkstra(v, v_dists);
    do_dijkstra(s, s_dists, true);
    do_dijkstra(t, t_dists);

    int64_t result = u_dists[v];

    for (int node = 1; node <= n; node++)
    {
        if (s_dists[node] + t_dists[node] != s_dists[t]) continue;
        result = min(result, min_dist_u[node] + v_dists[node]);
        result = min(result, min_dist_v[node] + u_dists[node]);
    }

    cout << result << "\n";
}

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