HackerEarth Find the shortest path problem solution

YASH PAL,
In this HackerEarth Find the shortest path problem solution Given a weighted tree with N vertices and N – 1 edges. Let D(i,j) be the distance of the unique simple path from i to j in this tree (i.e., the path from  to  that will not visit any node more than once).
We construct a new directed graph with N vertices, for each pair of vertices (i,j) if i < j we add an edge from i to j with weight D(i,j).
Find the shortest path from 1 to all other vertices in the newly constructed graph.
HackerEarth Find the shortest path problem solution

HackerEarth Find the shortest path problem solution.

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = (int)(1e6) + 5;
const ll oo = 1e18;
const int SQ = 300;
const int LG = 17;
vector < pii > g[N];
vi Lg[N];
ll D[N];
int h[N];
ll H[N];
int F[20][N];
void dfs1(int node,int prev) {
    F[0][node] = prev;
    h[node] = h[prev] + 1;
    for (auto it : g[node])
        if (prev != it.fi)
            H[it.fi] = H[node] + it.se,dfs1(it.fi,node);
}
int lca(int u,int v) {
    if (h[u] < h[v])
        swap(u,v);
    int sh = h[u] - h[v];
    for (int t = 0;t < LG;++t)
        if ((sh >> t) & 1)
            u = F[t][u];
    for (int t = LG - 1;t + 1;--t)
        if (F[t][u] != F[t][v])
            u = F[t][u],v = F[t][v];
    if (u == v)
        return u;
    return F[0][u];
}
ll dist(int u,int v) {
    return H[u] + H[v] - 2 * H[lca(u,v)];
}
int was[N];
ll dp[N];
int last;
void dfs2(int node,int prev) {
    if (was[node])
        dp[node] = D[node];
    for (auto it : g[node])
        if (it.fi != prev) {
            dfs2(it.fi,node);
            smin(dp[node],dp[it.fi] + it.se);
        }
}
void dfs3(int node,int prev,ll bst) {
    const ll tt = D[node];
    if (last + SQ <= node)
        smin(D[node],min(bst,dp[node]));
    pair < ll , ll > mn = mp(2 * oo,2 * oo);
    for (auto it : g[node])
        if (it.fi != prev)
            smin(mn,min(mp(mn.fi,dp[it.fi] + it.se),mp(dp[it.fi] + it.se,mn.fi)));
    if (was[node])
        smin(bst,tt);
    for (auto it : g[node]) 
        if (it.fi != prev) {
            const ll nxt = min(bst,mn.fi == dp[it.fi] + it.se ? mn.se : mn.fi);
            dfs3(it.fi,node,nxt + it.se);
        }
}
int main(void) {
    int n;
    scanf("%dn",&n);
    for (int i = 1;i < n;++i) {
        int u,v,w;
        scanf("%d %d %dn",&u,&v,&w);
        g[u].pb(mp(v,w));
        g[v].pb(mp(u,w));
    }
    dfs1(1,1);
    for (int k = 1;k < LG;++k)
        for (int i = 1;i <= n;++i)
            F[k][i] = F[k - 1][F[k - 1][i]];
    for (int i = 1;i <= n;++i)
        D[i] = oo,was[i] = 0;
    D[1] = 0;
    was[1] = 1;
    last = 1;
    for (int i = 2;i <= n;++i) {
        if (last + SQ == i) {
            for (int j = 1;j <= n;++j)
                dp[j] = 2 * oo;
            dfs2(1,0);
            dfs3(1,0,2 * oo);
            for (int j = last;j < i;++j)
                was[j] = 0;
            last = i;
        } else {
            for (int j = last;j < i;++j)
                smin(D[i],D[j] + dist(i,j));
        }
        was[i] = 1;
    }
    for (int i = 1;i <= n;++i)
        if (D[i] == oo)
            D[i] = 0;
    for (int i = 1;i <= n;++i)
         cout << D[i] << " n"[i == n];
    cerr << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << 'n';
    return 0;
}

Second solution

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 80000;
const int MAXD = 20;
const int BLOCK = (int)sqrt(MAXN * MAXD);
const int INF = 1000000000;
const long long LONGLONGINF = 2000000000000000000LL;

vector<pair<int, int>> adj[MAXN];
long long prefix[MAXN], d[MAXN];
int depth[MAXN], jump[MAXN][MAXD];

void dfs(int u, int fa, long long dist = 0, int dep = 0)
{
    jump[u][0] = fa;
    for (int i = 0; jump[u][i] != -1; ++ i) {
        jump[u][i + 1] = jump[jump[u][i]][i];
    }
    prefix[u] = dist;
    depth[u] = dep;
    for (const pair<int, int>& edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v == fa) {
            continue;
        }
        dfs(v, u, dist + w, dep + 1);
    }
}

int getLCA(int u, int v)
{
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    for (int i = MAXD - 1; i >= 0 && depth[u] != depth[v]; -- i) {
        int x = jump[u][i];
        if (x != -1 && depth[x] >= depth[v]) {
            u = x;
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = MAXD - 1; i >= 0; -- i) {
        int x = jump[u][i], y = jump[v][i];
        if (x != y) {
            u = x;
            v = y;
        }
    }
    return jump[u][0];
}

long long getDist(int u, int v)
{
    return prefix[u] + prefix[v] - 2 * prefix[getLCA(u, v)];
}

bool inblock[MAXN];
long long dp[MAXN];
int last;

void dfs2(int u, int fa)
{
    if (inblock[u]) {
        dp[u] = d[u];
    }
    for (const pair<int, int>& edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v == fa) {
            continue;
        }
        dfs2(v, u);
        dp[u] = min(dp[u], dp[v] + w);
    }
}

void dfs3(int u, int fa, long long mini)
{
    long long current = d[u];
    if (u >= last + BLOCK) {
        d[u] = min(d[u], mini);
        d[u] = min(d[u], dp[u]);
    }
    pair<long long, long long> top2 = {LONGLONGINF, LONGLONGINF};
    for (const pair<int, int>& edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v == fa) {
            continue;
        }
        long long x = dp[v] + w;
        if (x < top2.first) {
            top2.second = top2.first;
            top2.first = x;
        } else {
            top2.second = min(top2.second, x);
        }
    }
    if (inblock[u]) {
        mini = min(mini, current);
    }
    for (const pair<int, int>& edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v == fa) {
            continue;
        }
        long long next = mini;
        if (top2.first == dp[v] + w) {
            next = min(next, top2.second);
        } else {
            next = min(next, top2.first);
        }
        dfs3(v, u, next + w);
    }
}

int main()
{
    int n;
    assert(scanf("%d", &n) == 1 && 1 <= n && n <= MAXN);
    for (int i = 1; i < n; ++ i) {
        int u, v, w;
        assert(scanf("%d%d%d", &u, &v, &w) == 3);
        assert(1 <= u && u <= n);
        assert(1 <= v && v <= n);
        assert(-INF <= w && w <= INF);
        -- u; -- v;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
    memset(jump, -1, sizeof(jump));
    dfs(0, -1);
    for (int i = 0; i < n; ++ i) {
        d[i] = prefix[i];
    }

    // for (int i = 1; i < n; ++ i) {
    //     for (int j = 0; j < i; ++ j) {
    //         d[i] = min(d[i], d[j] + getDist(i, j));
    //     }
    // }

    last = 0;
    inblock[0] = true;
    for (int i = 1; i < n; ++ i) {
        if (last + BLOCK == i) {
            for (int j = 0; j < n; ++ j) {
                dp[j] = LONGLONGINF;
            }
            dfs2(1, 0);
            dfs3(1, 0, LONGLONGINF);
            for (int j = last; j < i; ++ j) {
                inblock[j] = false;
            }
            last = i;
        } else {
            for (int j = last; j < i; ++ j) {
                d[i] = min(d[i], d[j] + getDist(i,j));
            }
        }
        inblock[i] = true;
    }
    for (int i = 0; i < n; ++ i) {
        printf("%lld ", d[i]);
    }
    puts("");

    return 0;

}
coding problems solutions