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;
}
0 Comments