In this HackerRank Savita And Friends problem solution There are M roads connecting the houses. The road network formed is connected and does not contain self-loops and multiple roads between the same pair of houses. Savita and Friends decide to meet.

Savita wants to choose a point(not necessarily an integer) P on the road numbered K, such that, the maximum of dist(i) for all 1 <= I <= N is minimized.

where dist(i) is the shortest distance between the ith friend and P. If Kth road connects friend A and friend B you should print the distance of a chosen point from A. Also, print the max(dist(i)) for all 1 <= I <= N. If there is more than one solution, print the one in which the point P is closest to A.

HackerRank Savita And Friends problem solution


Problem solution in Python.

from heapq import (
    heapify,
    heappush,
    heappop,
)

from math import inf


def full_dijkstra(nodes, source, type_tag):
    out = [-1 for _ in nodes]
    p_queue = []
    visit_history = []  # little hack
    heappush(p_queue, (0, source))

    while p_queue:
        weight, actual = heappop(p_queue)
        if type_tag in nodes[actual][1]:
            continue
        nodes[actual][1][type_tag] = weight
        out[actual] = weight
        visit_history.append(actual)

        for neighbor, length in nodes[actual][0]:
            if not type_tag in nodes[neighbor][1]:
                heappush(p_queue, (weight+length, neighbor))
    return visit_history, out


lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
    nodes = [([], {}) for _ in range(n+1)]  # indexed from 1 to n
    for a, b, c in edges:
        nodes[a][0].append((b, c))
        nodes[b][0].append((a, c))

    a, b, k_dis = edges[k-1]
    lista5.append(k_dis)

    historyA, distancesA = full_dijkstra(nodes, a, "A")
    historyB, distancesB = full_dijkstra(nodes, b, "B")

    pairs = list(zip(distancesA, distancesB))[1:]

    distB = distancesB
    distA = distancesA
    peaks = []
    C = k_dis
    N = n

    for da, db in zip(distA[1:], distB[1:]):
        point_delta = db-da # desde b hacia a, negativo es bueno
        x = (k_dis + point_delta) / 2 # normalized
        peaks.append((x, da + x))
    peaks.sort()

    pts = []
    for x, y in peaks: # costo1, costo2
        while pts:
            x0, y0 = pts[-1] # tomar el último elemento
            if y0 > y - x + x0: # y0 distancia punto anterior de B con respecto a P
                # (y - x) -> delta distancia actual
                # x0 + delta < y0 -> el punto B está más alejado de P
                break
            pts.pop()
        if pts:
            x0, y0 = pts[-1] # mismo que el del while
            xy = x0 + y0 # (2x + distA[i])
            if y > xy - x: # (dist b) > (2x + distA[i]) - distA
                x1 = (xy - y + x) / 2
                pts.append((x1, xy - x1)) # mori
                pts.append((x, y)) # 
        else:
            if x > 0:
                pts.append((0, y - x)) # (x, y) -> (0, delta), diferencia entre los dos caminos mas largos
            pts.append((x, y)) # agregar el punto actual
    x, y = pts[-1]
    if x < C: 
        pts.append((C, y + x - C))
    print("%.5f %.5f" % min(pts, key=lambda x: x[1]))


def official_run():
    t = int(input())
    for i in range(t):
        n, m, k = map(int, input().split(" "))
        # edge: A, B, C
        edges = [tuple(map(int, input().split(" ")))
                for _ in range(m)] 
        run(n, m, k, edges)

#test_case_run()

official_run()

{"mode":"full","isActive":false}


Problem solution in Java.

import java.io.*;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.*;

public class Solution {

  static class Node {
    int src;
    int weight;

    public Node(int src, int weight) {
      this.src = src;
      this.weight = weight;
    }
  }

  static class Pll implements Comparable<Pll>  {
    long dis0;
    long dis1;

    public Pll(long dis0, long dis1) {
      this.dis0 = dis0;
      this.dis1 = dis1;
    }

    @Override
    public int compareTo(Pll o) {
      if (dis0 != o.dis0) {
        return  dis0 > o.dis0? 1 : -1;
        
      } else {
        if (dis1 == o.dis1) return 0;
        return  dis1 > o.dis1 ? 1 : -1;
      }
    }
  }

  static class NodeQ implements Comparable<NodeQ> {
    long dis;
    int se;

    public NodeQ(long fi, int se) {
      this.dis = fi;
      this.se = se;
    }

    @Override
    public int compareTo(NodeQ o) {
      if (dis == o.dis) return 0;
      return dis > o.dis ? 1 : -1;
    }
  }
  
  static final int N = 100000;
  static final NumberFormat FORMATTER = new DecimalFormat("#0.00000");
  static boolean[] vis = new boolean[N];
  static long[] d0 = new long[N];
  static long[] d1 = new long[N];
  static List<Node>[] nodes = new List[N];

  static void dijkstra(int n, int src, long d[]) {
    for (int i=0; i <n; i++) {
      vis[i] = false;
      d[i] = Long.MAX_VALUE/3;
    }
    d[src] = 0;
    PriorityQueue<NodeQ> queue = new PriorityQueue<>();
    queue.add(new NodeQ(0, src));
    while (!queue.isEmpty()) {
      NodeQ x = queue.poll();
      if (vis[x.se]) {
        continue;
      }
      vis[x.se] = true;
      for (Node e: nodes[x.se]) {
        if (x.dis+e.weight < d[e.src]) {
          queue.add(new NodeQ(d[e.src] = x.dis+e.weight, e.src));
        }
      }
    }
  }
  
  static double[] solve(int n, int k, int x, int y, int z) {
    dijkstra(n, x, d0);
    dijkstra(n, y, d1);
    Pll[] a = new Pll[n];
    for (int i = 0; i < n; i++) {
      a[i] = new Pll(d0[i], d1[i]);
    }
    Arrays.sort(a);
    long result0 = 0;
    long result1 = 2*a[n-1].dis0;
    int p = n-1;
    for (int i = n-1; --i >= 0; )
      if (a[i].dis1 > a[p].dis1) {
        long t = a[i].dis0+a[p].dis1+z;
        if (t < result1) {
          result0 = a[p].dis1+z-a[i].dis0;
          result1 = t;
        }
        p = i;
      }
    long t = 2*a[p].dis1;
    if (t < result1) {
      result1 = t;
      result0 = 2*z;
    }
    return new double[] { result0*.5, result1*.5};
  }
  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int t = Integer.parseInt(st.nextToken());

    for (int tItr = 0; tItr < t; tItr++) {
      st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      int k = Integer.parseInt(st.nextToken())-1;

      for (int i=0; i< n; i++) {
        if (nodes[i] == null) {
          nodes[i] = new LinkedList<>();
        } else {
          nodes[i].clear();
        }
      }
      
      int x = 0;
      int y = 0;
      int z = 0;
      for (int i = 0; i < m; i++) {
        st = new StringTokenizer(br.readLine());
        int u = Integer.parseInt(st.nextToken())-1;
        int v = Integer.parseInt(st.nextToken())-1;
        int w = Integer.parseInt(st.nextToken());
        if (i == k) {
          x = u;
          y = v;
          z = w;
        }
        nodes[u].add(new Node(v, w));
        nodes[v].add(new Node(u, w));

      }

      double[] result = solve(n, k, x, y, z);
      bw.write(FORMATTER.format(result[0]));
      bw.write(" ");
      bw.write(FORMATTER.format(result[1]));

      bw.newLine();
    }

    bw.close();
    br.close();
  }
}

{"mode":"full","isActive":false}


Problem solution in C++.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXM = MAXN * 2;
const long long INF = 100000000000000000LL;

int N, M, K;
int A, B, C;
struct Edge
{
    int v, w, next;
} edge[MAXM];
int head[MAXN], edgeNum;

void clearEdge()
{
    edgeNum = 0;
    memset(head, -1, sizeof(head));
}

void addEdgeSub(int u, int v, int w)
{
    edge[edgeNum].v = v;
    edge[edgeNum].w = w;
    edge[edgeNum].next = head[u];
    head[u] = edgeNum++;
}

void addEdge(int u, int v, int w)
{
    addEdgeSub(u, v, w);
    addEdgeSub(v, u, w);
}

long long distA[MAXN];
long long distB[MAXN];
int queue[MAXN];
bool visit[MAXN];

void spfa(int start, long long dist[MAXN])
{
    for (int i = 1; i <= N; ++i)
    {
        dist[i] = INF;
        visit[i] = false;
    }
    dist[start] = 0;
    visit[start] = true;
    int front = 0, rear = 1;
    queue[front] = start;
    while (front != rear)
    {
        int u = queue[front];
        for (int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if (!visit[v])
                {
                    visit[v] = true;
                    queue[rear] = v;
                    if (++rear >= MAXN)
                    {
                        rear = 0;
                    }
                }
            }
        }
        visit[u] = false;
        if (++front >= MAXN)
        {
            front = 0;
        }
    }
}

struct Node
{
    long long u, v;
    bool operator <(const Node &node) const
    {
        if (u == node.u)
        {
            return v < node.v;
        }
        return u < node.u;
    }
} node[MAXN];

int main()
{
    int T, a, b, c;
    scanf("%d", &T);
    while (T--)
    {
        clearEdge();
        scanf("%d%d%d", &N, &M, &K);
        for (int i = 1; i <= M; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            if (i == K)
            {
                A = a;
                B = b;
                C = c;
            }
            addEdge(a, b, c);
        }
        spfa(A, distA);
        spfa(B, distB);
        for (int i = 1; i <= N; ++i)
        {
            node[i].u = distA[i];
            node[i].v = distB[i];
        }
        sort(node + 1, node + N + 1);
        double x, ans = 1e100;
        double maxV = 0.0;
        int m = 0;
        node[0].u = -1;
        node[0].v = INF;
        for (int i = 1; i <= N; ++i)
        {
            if (node[i].v > maxV)
            {
                maxV = node[i].v;
            }
            while (node[i].u >= node[m].u && node[i].v >= node[m].v)
            {
                --m;
            }
            node[++m] = node[i];
        }
        if (maxV < ans)
        {
            x = C;
            ans = maxV;
        }
        if (node[m].u < ans)
        {
            x = 0;
            ans = node[m].u;
        }
        for (int i = 1; i < m; ++i)
        {
            double tx = (C + node[i + 1].v - node[i].u) * 0.5;
            double tAns = node[i].u + tx;
            if (tAns < ans)
            {
                ans = tAns;
                x = tx;
            }
        }
        printf("%.5f %.5f\n", x, ans);
    }
    return 0;
}

{"mode":"full","isActive":false}


Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
typedef struct{
  int u;
  long long w;
} node;
void heap_insert(node *heap,node *elem,int *size,int *heap_list);
void heap_update(node *heap,node *elem,int *heap_list);
void heap_read(node *heap,int *size,int *heap_list,node *ans);
void DJ(int N,int M,int*u,int*v,int*w,int*v_right,int*list_index,int*left_index,int*right_index,int S,long long*d);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size);

int main(){
  int T,N,M,K,A,B,C,f,i;
  int *u,*v,*w,*v_right,*list_index,*left_index,*right_index;
  long long max1,max2,maxa,maxb,min;
  long long *d_a,*d_b;
  u=(int*)malloc(100000*sizeof(int));
  v=(int*)malloc(100000*sizeof(int));
  w=(int*)malloc(100000*sizeof(int));
  v_right=(int*)malloc(100000*sizeof(int));
  list_index=(int*)malloc(100000*sizeof(int));
  left_index=(int*)malloc(100000*sizeof(int));
  right_index=(int*)malloc(100000*sizeof(int));
  d_a=(long long*)malloc(100000*sizeof(long long));
  d_b=(long long*)malloc(100000*sizeof(long long));
  scanf("%d",&T);
  while(T--){
    scanf("%d%d%d",&N,&M,&K);
    for(i=0;i<M;i++){
      scanf("%d%d%d",u+i,v+i,w+i);
      u[i]--;
      v[i]--;
      list_index[i]=i;
    }
    A=u[K-1];
    B=v[K-1];
    C=w[K-1];
    for(i=0;i<N;i++)
      d_a[i]=d_b[i]=-1;
    sort_a3(u,v,w,M);
    for(i=0;i<M;i++)
      v_right[i]=v[i];
    sort_a2(v_right,list_index,M);
    for(i=0;i<M;i++){
      if(i==0 || u[i]!=u[i-1])
        left_index[u[i]]=i;
      if(i==0 || v_right[i]!=v_right[i-1])
        right_index[v_right[i]]=i;
    }
    DJ(N,M,u,v,w,v_right,list_index,left_index,right_index,A,d_a);
    DJ(N,M,u,v,w,v_right,list_index,left_index,right_index,B,d_b);
    max1=max2=maxa=maxb=-1;
    for(i=0;i<N;i++){
      if(d_a[i]>maxa)
        maxa=d_a[i];
      if(d_b[i]>maxb)
        maxb=d_b[i];
      min=(d_a[i]>d_b[i])?d_b[i]:d_a[i];
      if(min>max1){
        max1=min;
        if(min==d_a[i])
          f=0;
        else
          f=1;
      }
      else if(min==max1 && f && min==d_a[i])
        f=0;
    }
    if(f){
      for(i=0;i<N;i++){
        min=(d_a[i]>d_b[i])?d_b[i]:d_a[i];
        if(min>max2 && min!=d_b[i] && d_b[i]>max1 && d_b[i]>=(double)min+((double)C+max1-min)/2)
          max2=min;
      }
      if((max2==-1 || max1-max2>=C) && maxa>maxb)
        printf("%.5lf %.5lf\n",(double)C,(double)maxb);
      else if(maxa<=(double)max2+((double)C+max1-max2)/2)
        printf("%.5lf %.5lf\n",0.0,(double)maxa);
      else
        printf("%.5lf %.5lf\n",((double)C+max1-max2)/2,(double)max2+((double)C+max1-max2)/2);
    }
    else{
      for(i=0;i<N;i++){
        min=(d_a[i]>d_b[i])?d_b[i]:d_a[i];
        if(min>max2 && min!=d_a[i] && d_a[i]>max1 && d_a[i]>(double)max1+((double)C-max1+min)/2)
          max2=min;
      }
      if((max2==-1 || max1-max2>=C) && maxb>=maxa)
        printf("%.5lf %.5lf\n",0.0,(double)maxa);
      else if(maxb<(double)max1+((double)C-max1+max2)/2)
        printf("%.5lf %.5lf\n",(double)C,(double)maxb);
      else
        printf("%.5lf %.5lf\n",((double)C-max1+max2)/2,(double)max1+((double)C-max1+max2)/2);
    }
  }
  return 0;
}
void heap_insert(node *heap,node *elem,int *size,int *heap_list){
  (*size)++;
  int index=(*size);
  while(index>1 && elem->w<heap[index/2].w){
    heap[index]=heap[index/2];
    heap_list[heap[index].u]=index;
    index/=2;
  }
  heap[index]=(*elem);
  heap_list[elem->u]=index;
  return;
}
void heap_update(node *heap,node *elem,int *heap_list){
  int index=heap_list[elem->u];
  while(index>1 && elem->w<heap[index/2].w){
    heap[index]=heap[index/2];
    heap_list[heap[index].u]=index;
    index/=2;
  }
  heap[index]=(*elem);
  heap_list[elem->u]=index;
  return;
}
void heap_read(node *heap,int *size,int *heap_list,node *ans){
  (*ans)=heap[1];
  int index=1;
  while(index*2<*size && heap[*size].w>heap[index*2].w || index*2+1<*size && heap[*size].w>heap[index*2+1].w){
    index=(heap[index*2].w>heap[index*2+1].w)?index*2+1:index*2;
    heap[index/2]=heap[index];
    heap_list[heap[index].u]=index/2;
  }
  heap[index]=heap[*size];
  heap_list[heap[index].u]=index;
  (*size)--;
  return;
}
void DJ(int N,int M,int*u,int*v,int*w,int*v_right,int*list_index,int*left_index,int*right_index,int S,long long*d){
  int i,next_solve,heap_size=0,*heap_list;
  node elem,*heap;
  heap=(node*)malloc(N*sizeof(node));
  heap_list=(int*)malloc(N*sizeof(int));
  d[S]=0;
  next_solve=S;
  while(1){
    for(i=left_index[next_solve];i>=0 && i<M && u[i]==next_solve;i++)
      if(d[v[i]]==-1 || d[v[i]]>d[next_solve]+w[i]){
        elem.u=v[i];
        elem.w=d[next_solve]+w[i];
        if(d[v[i]]==-1)
          heap_insert(heap,&elem,&heap_size,heap_list);
        else
          heap_update(heap,&elem,heap_list);
        d[v[i]]=d[next_solve]+w[i];
      }
    for(i=right_index[next_solve];i>=0 && i<M && v_right[i]==next_solve;i++)
      if(d[u[list_index[i]]]==-1 || d[u[list_index[i]]]>d[next_solve]+w[list_index[i]]){
        elem.u=u[list_index[i]];
        elem.w=d[next_solve]+w[list_index[i]];
        if(d[u[list_index[i]]]==-1)
          heap_insert(heap,&elem,&heap_size,heap_list);
        else
          heap_update(heap,&elem,heap_list);
        d[u[list_index[i]]]=d[next_solve]+w[list_index[i]];
      }
    if(heap_size==0)
      break;
    heap_read(heap,&heap_size,heap_list,&elem);
    next_solve=elem.u;
  }
  free(heap);
  free(heap_list);
  return;
}
void sort_a2(int*a,int*b,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}
void sort_a3(int*a,int*b,int*c,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  left_c=(int*)malloc(m*sizeof(int));
  right_c=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
    left_c[i]=c[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
    right_c[i]=c[i+m];
  }
  sort_a3(left_a,left_b,left_c,m);
  sort_a3(right_a,right_b,right_c,size-m);
  merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  free(left_c);
  free(right_c);
  return;
}
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
    }
  }
  return;
}

{"mode":"full","isActive":false}