HackerRank Savita And Friends Problem Solution

HackerRank Savita And Friends Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Savita And Friends Problem Solution.

After completing her final semester. Savita is back home. She is excited to meet all her friends. Her N friends live in different houses spread across the city.
There are M roads connecting the houses. The road network formed is connected and does not contain self loops and multiple roads between 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 minimised, where dist(i) is the shortest distance between the ith friend and P.
If K’th road connects friend A and friend B you should print distance of 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. Note:

  • Use scanf/printf instead of cin/cout. Large input files.
  • Order of A and B as given in the input must be maintained. If P is at a distance of 8 from A and 2 from B. you should print 8 and not 2.

Input Format
First line contain T, the number of testcases.
T testcases follow.
First Line of each testcase contains 3 space separated integers N, M, K.
Next M lines contain description of the ith road: three space separated integers A, B, C, where C is the length of road connecting A and B.

Output Format
For each testcase, print two space separated values in one line. The first value is the distance of P from the point A and the second value is the maximum of all the possible shortest paths between P and all of Savita’s and her friends’ houses. Round both answers to 5 decimal digits and print exactly 5 digits after the decimal point

Sample Input

2
2 1 1
1 2 10
4 4 1
1 2 10
2 3 10
3 4 1
4 1 5

Sample Output

5.00000 5.00000
2.00000 8.00000

Explanation
First testcase:
As K = 1, they will meet at the point P on the road that connects friend 1 with friend 2. If we choose mid point then distance for both of them will be 5. In any other position the maximum of distance will be more than 5.
Second testcase:
As K = 1, they will meet at a point P on the road connecting friend 1 and friend 2. If we choose point at a distance of 2 from friend 1: Friend 1 will have to travel distance 2.
Friend 2 will have to travel distance 8.
Friend 3 will have to travel distance 8.
Friend 4 will have to travel distance 7.
So, the maximum will be 8.
In any other position of point choosen, the maximum distance will be more than 8.
Timelimits
Timelimits for this problem is 2 times the environment limit.

HackerRank Savita And Friends Problem Solution
HackerRank Savita And Friends Problem Solution

Savita And Friends C Solution

#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;
}

Savita And Friends C++ Solution

#include <queue>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define X first
#define Y second
typedef long long LL;
typedef pair<LL , LL> pii;
const LL INF = 1e18;
const int MAX_N = 100050;
vector<pii> G[MAX_N];
LL d1[MAX_N], d2[MAX_N];
bool done[MAX_N];
int n, m;

void dijkstra(int s, LL *d) {
    memset(done, false, sizeof(done));
    priority_queue<pii, vector<pii>, greater<pii> > Q;
    for (int i = 1; i <= n; i++) d[i] = INF;
    Q.push(pii(0, s));
    d[s] = 0;

    while (!Q.empty()) {
        int u = Q.top().Y; Q.pop();
        done[u] = true;

        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].X, w = G[u][i].Y;
            if (d[v] > d[u] + w) {
                d[v]  = d[u] + w;
                Q.push(pii(d[v], v));
            }
        }
    }
}

int main(void) {
    //ios::sync_with_stdio(false);
    int T;
    scanf("%d", &T);
    //cin >> T;
    while (T--) {
        int k, kth, s1, s2;
        //cin >> n >> m >> k;
        scanf("%d %d %d", &n, &m, &k);
        for (int i = 1; i <= n; i++) G[i].clear();
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            //cin >> a >> b >> c;
            G[a].push_back(pii(b, c));
            G[b].push_back(pii(a, c));
            if (i == k) s1 = a, s2 = b, kth = c;
        }
        dijkstra(s1, d1);
        dijkstra(s2, d2);
        //for (int i = 1; i <= n; i++) cerr << d1[i] << endl;

        vector<pii> A;
        for (int i = 1; i <= n; i++) A.push_back(pii(d1[i], d2[i]));
        sort(A.begin(), A.end());
        vector<pii> B;
        LL fst = -1, snd = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (A[i].X <= fst && A[i].Y <= snd) continue;
            fst = A[i].X, snd = A[i].Y;
            B.push_back(A[i]);
        }
        double ans, p;
        int kk = B.size();
        if (B[0].X < B[kk - 1].Y) ans = B[0].X, p = 0.0;
        else ans = B[kk - 1].Y, p = kth + 0.0;
        for (int i = 0; i < kk - 1; i++) {
            double tmp = (B[i].Y - B[i + 1].X + kth) * 0.5;
            double val = B[i + 1].X + tmp;
            if (ans > val) ans = val, p = tmp;
            else if (ans == val && p > tmp) p = tmp;
        }
        printf("%.5f %.5f\n", p, ans);
    }
    return 0;
}

Savita And Friends C Sharp Solution

using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace CSharpParser
{
    public class Solution : SolutionBase
    {
        protected override void Solve()
        {
            int T;
            Next(out T);
            const long infinity = 10000000000000000L;
            while (T-- > 0)
            {
                int n, m, k;
                Next(out n);
                Next(out m);
                Next(out k);
                k--;
                var v = new List<Tuple<int, long>>[n];
                for (var i = 0; i < n; i++)
                    v[i] = new List<Tuple<int, long>>();
                var w = new int[2];
                long dist = 0;
                for (var l = 0; l < m; l++)
                {
                    int i, j;
                    long c;
                    Next(out i);
                    Next(out j);
                    i--;
                    j--;
                    Next(out c);
                    if (l == k)
                    {
                        w[0] = i;
                        w[1] = j;
                        dist = c;
                    }
                    else
                    {
                        v[i].Add(new Tuple<int, long>(j, c));
                        v[j].Add(new Tuple<int, long>(i, c));
                    }
                }
                var d = new long[2, n];

                var q = new PriorityQueue<Tuple<int, long>>((x, y) => Math.Sign(y.Item2 - x.Item2));
                for (var i = 0; i < 2; i++)
                {
                    for (var j = 0; j < n; j++)
                        d[i, j] = infinity;
                    d[i, w[i]] = 0;
                    q.Push(new Tuple<int, long>(w[i], 0));
                    while (!q.Empty())
                    {
                        var t = q.Top();
                        q.Pop();
                        for (var j = 0; j < v[t.Item1].Count; j++)
                        {
                            var tt = new Tuple<int, long>(v[t.Item1][j].Item1, v[t.Item1][j].Item2 + t.Item2);
                            if (d[i, tt.Item1] > tt.Item2)
                            {
                                d[i, tt.Item1] = tt.Item2;
                                q.Push(tt);
                            }
                        }
                    }
                }
                var a = new Tuple<long, long>[n];
                for (var i = 0; i < n; i++)
                    a[i] = new Tuple<long, long>(d[0, i], d[1, i]);
                Array.Sort(a, (x, y) => Math.Sign(x.Item2 - x.Item1 - y.Item2 + y.Item1));
                var mi = new long[n + 1];
                mi[n] = -infinity;
                for (var i = n - 1; i >= 0; i--)
                    mi[i] = Math.Max(mi[i + 1], a[i].Item1);
                var left = -infinity;
                var xx = -1L;
                var ans = infinity;
                for (var i = 0; i <= n; i++)
                {
                    var up = i == n ? 2 * dist : dist + a[i].Item2 - a[i].Item1;
                    if (up < 0) { left = Math.Max(left, a[i].Item2); continue; }
                    if (up > 2 * dist) up = 2 * dist;
                    var x = Math.Max(Math.Min(left + dist - mi[i], up), 0);
                    if (ans > Math.Max(x + 2 * mi[i], 2 * dist - x + 2 * left))
                    {
                        ans = Math.Max(x + 2 * mi[i], 2 * dist - x + 2 * left);
                        xx = x;
                    }
                    if (i != n) left = Math.Max(left, a[i].Item2);
                }
                PrintLine("{0:0.00000} {1:0.00000}", xx / 2.0, ans / 2.0);
            }
        }
    }

    public static class Algorithm
    {
        public static void Swap<T>(ref T a, ref T b)
        {
            var temp = a;
            a = b;
            b = temp;
        }

        public static T Max<T>(params T[] a)
        {
            var ans = a[0];
            var comp = Comparer<T>.Default;
            for (var i = 1; i < a.Length; i++) ans = comp.Compare(ans, a[i]) >= 0 ? ans : a[i];
            return ans;
        }

        public static T Min<T>(params T[] a)
        {
            var ans = a[0];
            var comp = Comparer<T>.Default;
            for (var i = 1; i < a.Length; i++) ans = comp.Compare(ans, a[i]) <= 0 ? ans : a[i];
            return ans;
        }

        public static void RandomShuffle<T>(T[] a, int index, int length)
        {
            if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
            var last = index + length;
            if (last > a.Length) throw new ArgumentException();
            var rnd = new Random(DateTime.Now.Millisecond);
            for (var i = index + 1; i < last; i++) Swap(ref a[i], ref a[rnd.Next(index, i + 1)]);
        }

        public static void RandomShuffle<T>(T[] a)
        {
            RandomShuffle(a, 0, a.Length);
        }

        public static bool NextPermutation<T>(T[] a, int index, int length, Comparison<T> compare = null)
        {
            compare = compare ?? Comparer<T>.Default.Compare;
            if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
            var last = index + length;
            if (last > a.Length) throw new ArgumentException();
            for (var i = last - 1; i > index; i--)
                if (compare(a[i], a[i - 1]) > 0)
                {
                    var j = i + 1;
                    for (; j < last; j++) if (compare(a[j], a[i - 1]) <= 0) break;
                    Swap(ref a[i - 1], ref a[j - 1]);
                    Array.Reverse(a, i, last - i);
                    return true;
                }
            Array.Reverse(a, index, length);
            return false;
        }

        public static bool NextPermutation<T>(T[] a, Comparison<T> compare = null)
        {
            return NextPermutation(a, 0, a.Length, compare);
        }

        public static bool PrevPermutation<T>(T[] a, int index, int length, Comparison<T> compare = null)
        {
            compare = compare ?? Comparer<T>.Default.Compare;
            if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
            var last = index + length;
            if (last > a.Length) throw new ArgumentException();
            for (var i = last - 1; i > index; i--)
                if (compare(a[i], a[i - 1]) < 0)
                {
                    var j = i + 1;
                    for (; j < last; j++) if (compare(a[j], a[i - 1]) >= 0) break;
                    Swap(ref a[i - 1], ref a[j - 1]);
                    Array.Reverse(a, i, last - i);
                    return true;
                }
            Array.Reverse(a, index, length);
            return false;
        }

        public static bool PrevPermutation<T>(T[] a, Comparison<T> compare = null)
        {
            return PrevPermutation(a, 0, a.Length, compare);
        }

        public static int LowerBound<T>(IList<T> a, int index, int length, T value, Comparison<T> compare = null)
        {
            compare = compare ?? Comparer<T>.Default.Compare;
            if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
            if (index + length > a.Count) throw new ArgumentException();
            var ans = index;
            var last = index + length;
            var p2 = 1;
            while (p2 <= length) p2 *= 2;
            for (p2 /= 2; p2 > 0; p2 /= 2) if (ans + p2 <= last && compare(a[ans + p2 - 1], value) < 0) ans += p2;
            return ans;
        }

        public static int LowerBound<T>(IList<T> a, T value, Comparison<T> compare = null)
        {
            return LowerBound(a, 0, a.Count, value, compare);
        }

        public static int UpperBound<T>(IList<T> a, int index, int length, T value, Comparison<T> compare = null)
        {
            compare = compare ?? Comparer<T>.Default.Compare;
            if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
            if (index + length > a.Count) throw new ArgumentException();
            var ans = index;
            var last = index + length;
            var p2 = 1;
            while (p2 <= length) p2 *= 2;
            for (p2 /= 2; p2 > 0; p2 /= 2) if (ans + p2 <= last && compare(a[ans + p2 - 1], value) <= 0) ans += p2;
            return ans;
        }

        public static int UpperBound<T>(IList<T> a, T value, Comparison<T> compare = null)
        {
            return UpperBound(a, 0, a.Count, value, compare);
        }
    }

    public class InStream : IDisposable
    {
        protected readonly TextReader InputStream;
        private string[] _tokens;
        private int _pointer;

        private InStream(TextReader inputStream)
        {
            InputStream = inputStream;
        }

        public static InStream FromString(string str)
        {
            return new InStream(new StringReader(str));
        }

        public static InStream FromFile(string str)
        {
            return new InStream(new StreamReader(str));
        }

        public static InStream FromConsole()
        {
            return new InStream(Console.In);
        }

        public string NextLine()
        {
            try
            {
                return InputStream.ReadLine();
            }
            catch (Exception)
            {
                return null;
            }
        }

        private string NextString()
        {
            try
            {
                while (_tokens == null || _pointer >= _tokens.Length)
                {
                    _tokens = NextLine().Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
                    _pointer = 0;
                }
                return _tokens[_pointer++];
            }
            catch (Exception)
            {
                return null;
            }
        }

        public bool Next<T>(out T ans)
        {
            var str = NextString();
            if (str == null)
            {
                ans = default(T);
                return false;
            }
            ans = (T)Convert.ChangeType(str, typeof(T));
            return true;
        }

        public T[] NextArray<T>(int length)
        {
            var array = new T[length];
            for (var i = 0; i < length; i++)
                if (!Next(out array[i]))
                    return null;
            return array;
        }

        public T[,] NextArray<T>(int length, int width)
        {
            var array = new T[length, width];
            for (var i = 0; i < length; i++)
                for (var j = 0; j < width; j++)
                    if (!Next(out array[i, j]))
                        return null;
            return array;
        }

        public void Dispose()
        {
            InputStream.Close();
        }
    }

    public class OutStream : IDisposable
    {
        protected readonly TextWriter OutputStream;

        private OutStream(TextWriter outputStream)
        {
            OutputStream = outputStream;
        }

        public static OutStream FromString(System.Text.StringBuilder strB)
        {
            return new OutStream(new StringWriter(strB));
        }

        public static OutStream FromFile(string str)
        {
            return new OutStream(new StreamWriter(str));
        }

        public static OutStream FromConsole()
        {
            return new OutStream(Console.Out);
        }

        public void Print(string format, params object[] args)
        {
            OutputStream.Write(format, args);
        }

        public void PrintLine(string format, params object[] args)
        {
            Print(format, args);
            OutputStream.WriteLine();
        }

        public void PrintLine()
        {
            OutputStream.WriteLine();
        }

        public void Print<T>(T o)
        {
            OutputStream.Write(o);
        }

        public void PrintLine<T>(T o)
        {
            OutputStream.WriteLine(o);
        }

        public void PrintArray<T>(IList<T> a, string between = " ", string after = "\n", bool printCount = false)
        {
            if (printCount)
                PrintLine(a.Count);
            for (var i = 0; i < a.Count; i++)
                Print("{0}{1}", a[i], i == a.Count - 1 ? after : between);
        }

        public void Dispose()
        {
            OutputStream.Close();
        }
    }

    public abstract class SolutionBase : IDisposable
    {
        private readonly InStream _in;
        private readonly OutStream _out;

        protected SolutionBase()
        {
            //System.Threading.Thread.CurrentThread.CurrentCulture = System.Globalization.CultureInfo.InvariantCulture;
            _in = InStream.FromConsole();
            _out = OutStream.FromConsole();
        }

        protected string NextLine()
        {
            return _in.NextLine();
        }

        protected bool Next<T>(out T ans)
        {
            return _in.Next(out ans);
        }

        protected T[] NextArray<T>(int length)
        {
            return _in.NextArray<T>(length);
        }

        protected T[,] NextArray<T>(int length, int width)
        {
            return _in.NextArray<T>(length, width);
        }

        protected void PrintArray<T>(IList<T> a, string between = " ", string after = "\n", bool printCount = false)
        {
            _out.PrintArray(a, between, after, printCount);
        }

        public void Print(string format, params object[] args)
        {
            _out.Print(format, args);
        }

        public void PrintLine(string format, params object[] args)
        {
            _out.PrintLine(format, args);
        }

        public void PrintLine()
        {
            _out.PrintLine();
        }

        public void Print<T>(T o)
        {
            _out.Print(o);
        }

        public void PrintLine<T>(T o)
        {
            _out.PrintLine(o);
        }

        public void Dispose()
        {
            _out.Dispose();
        }

        protected abstract void Solve();

        public static void Main()
        {
            using (var p = new Solution()) p.Solve();
        }
    }

    public class PriorityQueue<T>
    {
        private readonly List<T> _data;
        private readonly Comparison<T> _compare;

        public PriorityQueue()
            : this(Comparer<T>.Default.Compare)
        {
        }

        public PriorityQueue(Comparison<T> compare)
        {
            _compare = compare;
            _data = new List<T> { default(T) };
        }

        public int Count
        {
            get { return _data.Count - 1; }
        }

        public bool Empty()
        {
            return Count == 0;
        }

        public T Top()
        {
            return _data[1];
        }

        public void Push(T item)
        {
            _data.Add(item);
            var curPlace = Count;
            while (curPlace > 1 && _compare(item, _data[curPlace / 2]) > 0)
            {
                _data[curPlace] = _data[curPlace / 2];
                _data[curPlace / 2] = item;
                curPlace /= 2;
            }
        }

        public void Pop()
        {
            _data[1] = _data[Count];
            _data.RemoveAt(Count);
            var curPlace = 1;
            while (true)
            {
                var max = curPlace;
                if (Count >= curPlace * 2 && _compare(_data[max], _data[2 * curPlace]) < 0) max = 2 * curPlace;
                if (Count >= curPlace * 2 + 1 && _compare(_data[max], _data[2 * curPlace + 1]) < 0) max = 2 * curPlace + 1;
                if (max == curPlace) break;
                var item = _data[max];
                _data[max] = _data[curPlace];
                _data[curPlace] = item;
                curPlace = max;
            }
        }
    }
}

Savita And Friends Java Solution

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();
  }
}

Savita And Friends JavaScript Solution

function processData(input) {
    let D = [];
    for (let i = 0; i < input.length; ) {
        let c, d = 0;
        while ((c = input.charCodeAt(i++)) >= 48 && c <= 57)
            d = 10*d + c-48;
        D.push(d);
    }
    for (let i = 0, t = D[i++]; t; t--) {
        let n = D[i++], m = D[i++], k = D[i++]-1;
            let N = [], K;
            for (let j = 0; j < n; j++)
                N.push([]);
            for (let j = 0; j < m; j++) {
                let a = D[i++]-1, b = D[i++]-1, d = D[i++];
                if (j != k) {
                    N[a].push([b, d]);
                    N[b].push([a, d]);
                } else
                    K = [a, b, d];
            }
            test(N, K);
    }
}

function test(N, K) {
    let M = i => {
        let M = new Map(new Array(N.length).fill().map((_, j) => [j, j == i ? 0 : 1/0])), S = new Set([i]), H = [i], K = new Array(N.length).fill(null);
        K[i] = 0;
        let t = (i, j) => {
            let s = K[H[i]], t = H[i];
            K[H[i]] = K[H[j]];
            K[H[j]] = s;
            H[i] = H[j];
            H[j] = t;
        }, A = i => {
            if (K[i] == null) {
                H.push(i);
                K[i] = H.length-1;
            }
            let j = K[i], k;
            while ((k = Math.floor((j-1)/2)) >= 0) {
                if (M.get(H[j]) < M.get(H[k]))
                    t(j, k);
                j = k;
            }
        }, R = () => {
            if (H.length == 1) {
                K[H[0]] = null;
                return H.pop();
            }
            let r = H[0];
            K[r] = null;
            H[0] = H.pop();
            K[H[0]] = 0
            let j = i;
            while (2*j+1 < H.length)
                if (M.get(H[j]) > M.get(H[2*j+1]))
                    if (2*j+1 != H.length && M.get(H[2*j+2]) < M.get(H[2*j+1]))
                        t(j, j = 2*j+2);
                    else
                        t(j, j = 2*j+1);
                else if (2*j+1 != H.length && M.get(H[j]) > M.get(H[2*j+2]))
                    t(j, j = 2*j+2);
                else break;
            return r;
        }
        while (S.size) {
            let s = R();
            S.delete(s);
            for (let [j, d] of N[s])
                if (M.get(s) + d < M.get(j)) {
                        M.set(j, M.get(s) + d);
                        S.add(j);
                        A(j);
                    }
        }
        return M;
    }
    let [a, b, d] = K, A = M(a), B = M(b), C = new Map(), D = new Map();
    for (let i = 0; i < N.length; i++) {
        C.set(i, Math.min(A.get(i), B.get(i) + d));
        D.set(i, Math.min(A.get(i) + d, B.get(i)))
    }
    let L = new Array(N.length).fill().map((_, i) => i).sort((i, j) => C.get(j) - C.get(i)), l = L[0], s = 0, t = C.get(l);
    for (let i = 1; i < N.length; i++)
        if (D.get(L[i]) > D.get(l)) {
            if ((D.get(l) + d + C.get(L[i]))/2 < t) {
                t = (D.get(l) + d + C.get(L[i]))/2;
                s = (D.get(l) + d - C.get(L[i]))/2
            }
            l = L[i];
        }
    if (D.get(l) < t) {
        t = D.get(l);
        s = d;
    }
    console.log(s.toFixed(5), t.toFixed(5));
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Savita And Friends Python Solution

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()
c C# C++ HackerRank Solutions java javascript python