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