HackerRank Savita And Friends problem solution YASH PAL, 31 July 2024 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. 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 %.5fn", 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 %.5lfn",(double)C,(double)maxb); else if(maxa<=(double)max2+((double)C+max1-max2)/2) printf("%.5lf %.5lfn",0.0,(double)maxa); else printf("%.5lf %.5lfn",((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 %.5lfn",0.0,(double)maxa); else if(maxb<(double)max1+((double)C-max1+max2)/2) printf("%.5lf %.5lfn",(double)C,(double)maxb); else printf("%.5lf %.5lfn",((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} Algorithms coding problems solutions