HackerEarth Find the shortest path problem solution YASH PAL, 31 July 2024 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("%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