[Codeforces] F. Cheap Robot

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : F. Cheap Robot
Source            : Codeforces
Category          : Meet In The Middle
Algorithm         : Bi-Directional Search
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 2e5 + 5;  
static const int logn = 19;  
static const long long inf = 1e18;  
  
struct Node  
{  
      int v;  
      long long w;  
      Node(int v, long long w) : v(v), w(w) {}  
      bool operator < (const Node &other) const  
      {  
            return w > other.w;  
      }  
};  
  
struct Edge  
{  
      int u, v;  
      long long w;  
      Edge(int u, int v, long long w) : u(u), v(v), w(w) {}  
      bool operator < (const Edge &other) const  
      {  
            return w < other.w;  
      }  
};  
  
int tnode;  
int tedge;  
int tcenter;  
int tquery;  
  
vector < vector <Node> > graph;  
vector <Edge> Edges;  
int mostparent[maxn];  
long long dist[maxn];  
  
void dijkstra()  
{  
      for (int i = 1; i < maxn; i++) dist[i] = inf;  
      priority_queue <Node> pq;  
      for (int i = 1; i <= tcenter; i++)  
      {  
            pq.emplace(i, 0LL);  
            mostparent[i] = i;  
            dist[i] = 0LL;  
      }  
      while (pq.empty() == false)  
      {  
            int u = pq.top().v; pq.pop();  
            for (Node g : graph[u])  
            {  
                  int v = g.v;  
                  long long w = g.w;  
                  long long cost = dist[u] + w;  
                  if (dist[v] > cost)  
                  {  
                        dist[v] = cost;  
                        mostparent[v] = mostparent[u];  
                        pq.emplace(v, cost);  
                  }  
            }  
      }  
}  
  
vector <Node> Tree[maxn];  
int par[maxn];  
  
void makeSet()  
{  
      for (int i = 1; i < maxn; i++) par[i] = i;  
}  
  
int findRep(int r)  
{  
      if (r == par[r]) return r;  
      return par[r] = findRep(par[r]);  
}  
  
int depth[maxn];  
int father[maxn][logn];  
long long cost[maxn][logn];  
  
void dfs(int u, int p = -1)  
{  
      for (int i = 1; i < logn; i++)  
      {  
            father[u][i] = father[ father[u][i - 1] ][i - 1];  
            cost[u][i] = max(cost[ father[u][i - 1] ][i - 1], cost[u][i - 1]);  
      }  
      for (Node g : Tree[u])  
      {  
            int v = g.v;  
            long long w = g.w;  
            if (v == p) continue;  
            depth[v] = depth[u] + 1;  
            father[v][0] = u;  
            cost[v][0] = w;  
            dfs(v, u);  
      }  
}  
  
int findlca(int u, int v, long long &maxi)  
{  
      if (depth[u] < depth[v]) swap(u, v);  
      maxi = 0;  
      for (int i = logn - 1; i >= 0; i--)  
      {  
            if (depth[ father[u][i] ] >= depth[v])  
            {  
                  maxi = max(maxi, cost[u][i]);  
                  u = father[u][i];  
            }  
      }  
      if (u == v) return u;  
      for (int i = logn - 1; i >= 0; i--)  
      {  
            if (father[u][i] != father[v][i])  
            {  
                  maxi = max(maxi, cost[u][i]);  
                  maxi = max(maxi, cost[v][i]);  
                  u = father[u][i];  
                  v = father[v][i];  
            }  
      }  
      maxi = max(maxi, cost[u][0]);  
      maxi = max(maxi, cost[v][0]);  
      return father[u][0];  
}  
  
long long get(int u, int v)  
{  
      long long maxi;  
      int lca = findlca(u, v, maxi);  
      return maxi;  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> tnode >> tedge >> tcenter >> tquery;  
      graph.resize(tnode + 1);  
      vector <Edge> allEdges;  
      for (int e = 1; e <= tedge; e++)  
      {  
            int u, v;  
            long long w;  
            cin >> u >> v >> w;  
            graph[u].emplace_back(v, w);  
            graph[v].emplace_back(u, w);  
            allEdges.push_back({u, v, w});  
      }  
      dijkstra();  
      for (Edge E : allEdges)  
      {  
            int u = E.u;  
            int v = E.v;  
            long long w = E.w;  
            if (mostparent[u] == mostparent[v]) continue;  
            long long cost = dist[u] + dist[v] + w;  
            Edges.push_back({mostparent[u], mostparent[v], cost});  
      }  
      makeSet();  
      sort(Edges.begin(), Edges.end());  
      int root;  
      for (Edge E : Edges)  
      {  
            int u = E.u;  
            int v = E.v;  
            long long w = E.w;  
            int p = findRep(u);  
            int q = findRep(v);  
            if (p == q) continue;  
            root = u;  
            Tree[u].emplace_back(v, w);  
            Tree[v].emplace_back(u, w);  
            par[q] = p;  
      }  
      depth[root] = 1;  
      dfs(root);  
      while (tquery--)  
      {  
            int u, v;  
            cin >> u >> v;  
            long long ans = get(u, v);  
            cout << ans << '\n';  
      }  
}