the shortest statement

Problem Link

Algorithms Used: Kruskal's algorithm, LCA, Dijkstra's

In this problem, we are given a graph consisting of N nodes and M edges where there will be a maximum of 20 more edges than nodes (M - N <= 20). We need to answer Q queries where we need to find the minimum distance between nodes u and v in the graph.

Observe the constraint on M carefully. This constraint implies that if we were to create a tree from the edges, there would be a maximum of 21 edges left over. Why should we create a tree? Because finding the distance between two nodes in a tree is easy using the LCA. However, this distance may not be the smallest. In this case, we would need to use at least 1 of the 21 extra edges. We know that the minimum distance would then look like this: dis[x][u] + dis[x][v] where dis[x][a] is the distance from node x to node a and x is the endpoint of the extra edge in use. since there are 21 extra edges, there will be a maximum of 42 'x' nodes. We can run Dijkstra's algorithm to calculate dis[x][a] for each of the 42 nodes. The answer for a query will be the minimum between the length of the path that goes solely through the tree and the length of the path that uses the extra edge.

How do we decide which nodes become part of the tree? We can use Kruskal's algorithm to generate an MST from the graph. Whichever edges are not part of the MST become the extra edges. The MST will ensure that if a path the goes solely through the tree is the answer, then the length of that path will be minimal.

Overall, the time complexity of the is NlogN due to the MST generation and the LCA algorithm.

Code

#include <iostream>

#include <algorithm>

#include <array>

#include <vector>

#include <queue>

using namespace std;

using ll = long long;

struct DSU {

    vector <int> link, sz;

    DSU (int s) {

        link = sz = vector <int> (s+1);

        for (int i = 1; i <= s; i++) {

            link[i] = i;

            sz[i] = 1;

        }

    }

    int head(int x) {

        while (x != link[x])

            x = link[x];

        return x;

    }

    bool same(int a, int b) {

        return head(a) == head(b);

    }

    void unite(int a, int b) {

        a = head(a);

        b = head(b);

        if (same(a, b))

            return;

        if (sz[a] < sz[b])

            swap(a, b);

        sz[a] += sz[b];

        link[b] = a;

    }

};

int n, m;

bool comp(array <int, 3> a, array <int, 3> b) {

    return a[2] < b[2];

}

vector <vector <pair <int, int>>> adj;

void dijkstra(int s, vector <ll> &dis) {

    priority_queue <pair <ll, int>> pq;

    fill(dis.begin(), dis.end(), 1e15);

    dis[s] = 0;

    pq.push({0, s});

    vector <bool> processed(n+1);

    while (!pq.empty()) {

        s = pq.top().second;

        pq.pop();

        if (processed[s])

            continue;

        processed[s] = true;

        for (auto i : adj[s]) {

            if (dis[s] + i.second < dis[i.first]) {

                dis[i.first] = dis[s] + i.second;

                pq.push({-dis[i.first], i.first});

            }

        }

    }

}

const int maxn = 1e5 + 1;

const int max_anc = 20;

ll tree_dis[maxn];

int visit[maxn], finish[maxn];

int anc[maxn][max_anc];

int t = 0;

void dfs(int s, int p, ll d) {

    tree_dis[s] = d;

    anc[s][0] = p;

    for (int i = 1; i < 20; i++)

        anc[s][i] = anc[anc[s][i-1]][i-1];

    visit[s] = t++;

    for (auto i : adj[s]) {

        if (i.first == p)

            continue;

        dfs(i.first, s, i.second + d);

    }

    finish[s] = t++;

}

bool is_ancestor(int a, int b) {

    return visit[a] <= visit[b] && finish[a] >= finish[b];

}

int get_lca(int a, int b) {

    if (is_ancestor(a, b))

        return a;

    if (is_ancestor(b, a))

        return b;

    int lca = a;

    for (int i = max_anc - 1; i >= 0; i--) {

        if (!is_ancestor(anc[lca][i], b))

            lca = anc[lca][i];

    }

    return anc[lca][0];

}

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    cin >> n >> m;

    adj.resize(n+1);

    vector <array <int, 3>> edges(m);

    for (int i = 0; i < m; i++)

        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];

    sort(edges.begin(), edges.end(), comp);

    DSU dsu(n+1);

    vector <int> unused_nodes;

    vector <int> unused_edges;

    for (int i = 0; i < m; i++) {

        int a = edges[i][0], b = edges[i][1], w = edges[i][2];

        if (!dsu.same(a, b)) {

            dsu.unite(a, b);

            adj[a].push_back({b, w});

            adj[b].push_back({a, w});

        } else {

            unused_edges.push_back(i);

            unused_nodes.push_back(a);

            unused_nodes.push_back(b);

        }

    }

    dfs(1, 1, 0);

    for (auto i : unused_edges) {

        int a = edges[i][0], b = edges[i][1], w = edges[i][2];

        adj[a].push_back({b, w});

        adj[b].push_back({a, w});

    }

    sort(unused_nodes.begin(), unused_nodes.end());

    unused_nodes.erase(unique(unused_nodes.begin(), unused_nodes.end()), unused_nodes.end());

    int p = 0;

    vector <vector <ll>> dis(unused_nodes.size(), vector <ll> (n+1));

    for (auto i : unused_nodes) {

        dijkstra(i, dis[p++]);

    }

    int q;

    cin >> q;

    while (q--) {

        int a, b;

        cin >> a >> b;

        int lca = get_lca(a, b);

        ll ans = tree_dis[a] + tree_dis[b] - tree_dis[lca] * 2;

        for (int i = 0; i < unused_nodes.size(); i++) {

            ans = min(ans, dis[i][a] + dis[i][b]);

        }

        cout << ans << '\n';

    }

}