# HackerEarth Find the shortest path problem solution

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.

`#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("%d\n",&n);    for (int i = 1;i < n;++i) {        int u,v,w;        scanf("%d %d %d\n",&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;}`