[Gym] G. Short Path

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : G. Short Path
Source            : Gym
Category          : Meet In The Middle
Algorithm         : Bidirectional Search
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll            long long
#define inf           1e18
 
static const int maxn = 1e5 + 5;
 
struct node
{
       int v;
       ll w;
       node(int v = 0, ll w = 0) : v(v), w(w) {}
       friend bool operator < (node A, node B)
       {
              return A.w > B.w;
       }
};
 
vector <node> graph[maxn];
vector < tuple <int, int, ll> > edgeList;
int tnode, tedge;
ll dist[maxn];
int mostParrent[maxn];
int isControl[maxn];
 
inline void dijkstra()
{
       priority_queue <node> PQ;
       for (int i = 1; i <= tnode; i++)
       {
              dist[i] = inf;
              if (isControl[i])
              {
                     PQ.emplace(i, 0);
                     dist[i] = 0;
                     mostParrent[i] = i;
              }
       }
       while (!PQ.empty())
       {
              node u = PQ.top(); PQ.pop();
              for (node v : graph[u.v])
              {
                     if (dist[v.v] > dist[u.v] + v.w)
                     {
                            dist[v.v] = dist[u.v] + v.w;
                            mostParrent[v.v] = mostParrent[u.v];
                            PQ.emplace(v.v, dist[v.v]);
                     }
              }
       }
}
 
int main()
{
       //freopen("in.txt", "r", stdin);
 
       scanf("%d %d", &tnode, &tedge);
       for (int i = 1; i <= tnode; i++) scanf("%d", isControl+i);
       for (int e = 0; e < tedge; e++)
       {
              int u, v;
              ll w;
              scanf("%d %d %lld", &u, &v, &w);
              edgeList.emplace_back(u, v, w);
              graph[u].emplace_back(v, w);
              graph[v].emplace_back(u, w);
       }
       dijkstra();
       ll ans = inf;
       int ansu = -1, ansv = -1;
       for (int e = 0; e < tedge; e++)
       {
              int u = get <0> (edgeList[e]);
              int v = get <1> (edgeList[e]);
              ll w = get <2> (edgeList[e]);
              if (mostParrent[u] == mostParrent[v]) continue;
              ll tdist = dist[u] + w + dist[v];
              if (tdist < ans) ans = tdist, ansu = mostParrent[u], ansv = mostParrent[v];
       }
       if (ansu == -1) puts("No luck at all");
       else printf("%lld\n%d %d\n", ans, ansu, ansv);
}