HackerRank Jeanie's Route Problem Solution

HackerRank Jeanie’s Route Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Jeanie’s Route Problem Solution.

Byteland has N cities (numbered from 1 to N) and N-1 bidirectional roads. It is guaranteed that there is a route from any city to any other city.
Jeanie is a postal worker who must deliver K letters to various cities in Byteland. She can start and end her delivery route in any city. Given the destination cities for K letters and the definition of each road in Byteland, find and print the minimum distance Jeanie must travel to deliver all K letters.
Note: The letters can be delivered in any order.
Input Format
The first line contains two space-separated integers, N (the number of cities) and K (the number of letters), respectively.
The second line contains K space-separated integers describing the delivery city for each
letter.
Each line i of the N – 1 subsequent lines contains 3 space-separated integers describing a road as u, v, d, where d, is the distance (length) of the bidirectional road between cities u, and vi

Output Format

Print the minimum distance Jeanie must travel to deliver all K letters.

Sample Input 0

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

Sample Output 0

6
HackerRank Jeanie's Route Problem Solution
HackerRank Jeanie’s Route Problem Solution

Jeanie’s Route C Solution

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct wire {
    int id;
    unsigned cost;
    struct wire *next;
} wire_t;

unsigned clean_needless(int i, char color[], char deliver[], wire_t *links[]) {
    if (color[i]) return 0;
    color[i] = 1;

    unsigned dcount = deliver[i];

    wire_t **pp = &links[i];
    wire_t *p = links[i];
    while (p) {
    unsigned branch_count = clean_needless(p->id, color, deliver, links);
    dcount += branch_count;

    if (branch_count)
        pp = &p->next;
    else
        *pp = p->next;
    
    p = p->next;
    }

    return dcount;
}

#define max(a, b) ((a) > (b) ? (a) : (b))
unsigned count_cost(unsigned *tcost, unsigned *icost,
        int i, char deliver[], wire_t *links[]) {
    if (!links[i]) {
    *tcost = 0;
    *icost = 0;
    return 0;
    }
    
    if (!links[i]->next) {
    unsigned count = count_cost(tcost, icost, links[i]->id, deliver, links);
    *tcost += links[i]->cost;

    if (deliver[i])
        *icost = max(*icost, *tcost);
    
    return count + links[i]->cost;
    }

    unsigned micost = 0;
    unsigned mtcost[2] = { 0, 0 };

    unsigned count = 0;
    for (wire_t *p = links[i]; p; p = p->next) {
    unsigned licost, ltcost;
    count += count_cost(&ltcost, &licost, p->id, deliver, links);
    count += p->cost;
    ltcost += p->cost;
    
    micost = max(micost, licost);
    if (mtcost[0] < ltcost) {
        mtcost[1] = mtcost[0];
        mtcost[0] = ltcost;
    } else if (mtcost[1] < ltcost) {
        mtcost[1] = ltcost;
    }
    }

    if (deliver[i])
    micost = max(micost, mtcost[0]);

    *icost = max(micost, mtcost[0] + mtcost[1]);
    *tcost = mtcost[0];

    return count;
}

int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);

    int id = 0;
    char *deliver = calloc(n, 1);
    for (int i = 0; i < m; i++) {
    scanf("%d", &id);
    id -= 1;
    deliver[id] = 1;
    }
    
    wire_t *wires = malloc(2*(n-1)*sizeof(wire_t));
    int take_pos = 0;

    wire_t **links = calloc(n, sizeof(wire_t *));

    for (int i = 0; i < n-1; i++) {
    int src, dst;
    unsigned cost;
    scanf("%d%d%u", &src, &dst, &cost);
    src -= 1;
    dst -= 1;

    wire_t *wire;

    wire= &wires[take_pos++];
    wire->id = dst;
    wire->cost = cost;
    wire->next = links[src];
    links[src] = wire;

    wire = &wires[take_pos++];
    wire->id = src;
    wire->cost = cost;
    wire->next = links[dst];
    links[dst] = wire;
    }

    char *color = calloc(n, 1);
    clean_needless(id, color, deliver, links);

    unsigned icost, tcost;
    unsigned total = 2*count_cost(&tcost, &icost, id, deliver, links);

    unsigned min_cost = total - icost;
    printf("%u\n", min_cost);
    
    free(color);
    free(links);
    free(wires);
    free(deliver);
}

Jeanie’s Route C++ Solution

/* try some examples with two nodes , three nodes , four nodes will get the ans !! observe that we will have two nodes for which dist between them will be added and for other nodes dist to that path will be added twice , now there can be o ( n ^ 2 ) starting ending pair. but observe that starting ending will be the farthest !! so simply it is 2 * total_dist - max_dist_pair */

//----------------------------------------------------------------------------------------------------------------------------------------------

//#define NDEBUG
#include <bits/stdc++.h>

using namespace std ;

typedef pair < int , int > pii ;
typedef vector < pii > vpii ;
typedef multiset < int > msi ;

//#define dbg 1
#define dash "---------------------------------------------------"
#define fie(i,start,stop) for ( int i = start ; i < stop ; i ++ )
#define fii(i,start,stop) for ( int i = start ; i <= stop ; i ++ )
#define fdei(i,start,stop) for ( int i = start - 1 ; i >= stop ; i -- )
#define fdii(i,start,stop) for ( int i = start ; i >= stop ; i -- )
#define tr(it,container) for ( __typeof ( container.begin () ) it = container.begin () ; it != container.end () ; it ++ )
#define print(s,x) cout << "> " << s << " " << #x << " : " << x << endl
#define print1(x) cout << "> " << #x << " : " << x << endl
#define print2(x1,x2) cout << "> " << #x1 << " : " << x1 << " , " << #x2 << " : " << x2 << endl
#define print3(x1,x2,x3) cout << "> " << #x1 << " : " << x1 << " , " << #x2 << " : " << x2 << " , " << #x3 << " : " << x3 << endl
#define print4(x1,x2,x3,x4) cout << "> " << #x1 << " : " << x1 << " , " << #x2 << " : " << x2 << " , " << #x3 << " : " << x3 << " , " << #x4 << " : " << x4 << endl
#define all(x) x.begin () , x.end ()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template < class T > void print_2darray ( const char * s , T arr , int n , int m )
{
    cout << "> " << s << endl ;
    cout << "[" << endl ;
    fie ( i , 0 , n )
    {
        cout << "{" ;
        fie ( j , 0 , m )
        {
            cout << arr [ i ] [ j ] << ( j == m - 1 ? "" : "," ) ;
        }
        cout << "}" << endl ;
    }
    cout << "]" << endl ;
}

template < class T > void print_1darray ( const char * s , T arr , int n )
{
    cout << "> " << s << endl ;
    cout << "[" << endl ;
    fie ( i , 0 , n )
    {
        cout << arr [ i ] << ( i == n - 1 ? "" : "," ) ;
    }
    cout << endl << "]" << endl ;
}

//----------------------------------------------------------------------------------------------------------------------------------------------

const int N = 100000 ;
int n , k , x ;
int post [ N + 1 ] ;
vpii edges [ N + 1 ] ; 
int total_dist [ N + 1 ] , farthest_node [ N + 1 ] , max_dist_pair [ N + 1 ] , present [ N + 1 ] ;
msi :: iterator it1 , it2 ;

void dfs ( int node , int parent )
{
    msi val ;
    tr ( it , edges [ node ] )
    {
        if ( it->f != parent )
        {
            dfs ( it->f , node ) ;
            if ( ! present [ it->f ] )
            {
                continue ;
            }
            present [ node ] = 1 ;
            farthest_node [ node ] = max ( farthest_node [ node ] , farthest_node [ it->f ] + it->s ) ;
            total_dist [ node ] += total_dist [ it->f ] + it->s ;
            max_dist_pair [ node ] = max ( max_dist_pair [ node ] , max_dist_pair [ it->f ] ) ;
            val.insert ( farthest_node [ it->f ] + it->s ) ;
            if ( val.size () > 2 )
            {
                it1 = val.begin () ;
                it1 ++ ;
                val.erase ( val.begin () , it1 ) ;
            }
        }
    }
    if ( post [ node ] )
    {
        present [ node ] = 1 ;
        max_dist_pair [ node ] = max ( max_dist_pair [ node ] , farthest_node [ node ] ) ;  // dont forget this !! max dist pair can be from root to other also !! 
    }
    if ( val.size () == 2 )
    {
        it1 = val.begin () ;
        it2 = it1 ;
        it2 ++ ;
        max_dist_pair [ node ] = max ( max_dist_pair [ node ] , * it1 + * it2 ) ;
    }
}

void read_input ()
{
    cin >> n >> k ;
    fie ( i , 0 , k )
    {
        cin >> x ;
        post [ x ] = 1 ;
    }
    int u , v , d ;
    fie ( i , 1 , n )
    {
        cin >> u >> v >> d ;
        edges [ u ].pb ( mp ( v , d ) ) ;
        edges [ v ].pb ( mp ( u , d ) ) ;
    }
}

int main ()
{
    read_input () ;
    dfs ( x , x ) ;
    cout << 2 * total_dist [ x ] - max_dist_pair [ x ] << endl ; 
    
    return 0 ;
}

Jeanie’s Route C Sharp Solution

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

class Solution {
    class Edge {
        public int Cost { get; set; }
        public int Node { get; set; }
    }
    
    class Node {
        public List<Edge> Edges { get; set; }
        public int ParentNode { get; set; }
        public int CostToRootNode { get; set; }
    }
    
    /*
     * Complete the JeanisRoute function below.
     */
    static int JeanisRoute(int[] nodesToVisit, int[][] edges) {
        if (nodesToVisit.Count() <= 1) {
            return 0;
        }
        
        var graph = new Node[edges.Count() + 1];
        
        for (var i = 0; i < graph.Count(); ++i) {
            graph[i] = new Node {
                Edges = new List<Edge>()
            };
        }

        foreach (var edge in edges) {
            var u = edge[0] - 1;
            var v = edge[1] - 1;
            var d = edge[2];
            
            graph[u].Edges.Add(new Edge {
                Node = v,
                Cost = d
            });
            
            graph[v].Edges.Add(new Edge {
                Node = u,
                Cost = d
            });
        }
        
        for (var i = 0; i < nodesToVisit.Count(); ++i) {
            --nodesToVisit[i];
        }

        var nodesToVisitSet = new HashSet<int>(nodesToVisit);
        var rootNode = FindInternalNode(graph, nodesToVisitSet);
        
        RemoveUnnecessaryNodes(graph, nodesToVisitSet, rootNode);
        CalculateCostToRootNode(graph, rootNode);
        
        var traversedEdgesCost = CalculateTraversedEdgesCost(graph, rootNode);
        var startNode = nodesToVisit[0];       
        
        foreach (var node in nodesToVisit) {
            if (graph[node].CostToRootNode > graph[startNode].CostToRootNode) {
                startNode = node;
            }
        }
        
        RecalculateAffectedCostToRootNode(graph, rootNode, startNode);
        
        var endNode = rootNode;
        
        foreach (var node in nodesToVisit) {
            if (graph[node].CostToRootNode > graph[endNode].CostToRootNode) {
                endNode = node;
            }
        }

        return 2 * traversedEdgesCost + graph[startNode].CostToRootNode - graph[endNode].CostToRootNode;
    }
    
    static void RecalculateAffectedCostToRootNode(Node[] graph, int rootNode, int startNode) {
        RecalculateAffectedCostToRootNodeImpl(graph, rootNode, startNode, -1);
    }
    
    static void RecalculateAffectedCostToRootNodeImpl(Node[] graph, int rootNode, int currentNode, int previousNode) {
        if (currentNode == rootNode) {
            return;
        }
        
        graph[currentNode].CostToRootNode *= -1;
        
        foreach (var edge in graph[currentNode].Edges.Where(e => e.Node != previousNode)) {
            CalculateCostToRootNodeImpl(graph, edge.Node, graph[currentNode].CostToRootNode + edge.Cost);
        }
        
        RecalculateAffectedCostToRootNodeImpl(graph, rootNode, graph[currentNode].ParentNode, currentNode);
    }
    
    static void CalculateCostToRootNode(Node[] graph, int rootNode) {
        CalculateCostToRootNodeImpl(graph, rootNode, 0);
    }
    
    static void CalculateCostToRootNodeImpl(Node[] graph, int node, int cost) {
        graph[node].CostToRootNode = cost;
        
        foreach (var edge in graph[node].Edges) {
            CalculateCostToRootNodeImpl(graph, edge.Node, cost + edge.Cost);
        }
    }
    
    static int CalculateTraversedEdgesCost(Node[] graph, int rootNode) {
        return graph[rootNode].Edges.Sum(e => e.Cost + CalculateTraversedEdgesCost(graph, e.Node));
    }
    
    static void RemoveUnnecessaryNodes(Node[] graph, HashSet<int> nodesToVisit, int rootNode) {
        RemoveUnnecessaryNodesImpl(graph, nodesToVisit, rootNode, -1);
    }
    
    static bool RemoveUnnecessaryNodesImpl(Node[] graph, HashSet<int> nodesToVisit, int currentNode, int parentNode) {
        var edgesToKeep = new List<Edge>();
        
        foreach (var edge in graph[currentNode].Edges.Where(e => e.Node != parentNode)) {
            if (RemoveUnnecessaryNodesImpl(graph, nodesToVisit, edge.Node, currentNode)) {
                edgesToKeep.Add(edge);
            }
        }
        
        graph[currentNode].Edges = edgesToKeep;
        graph[currentNode].ParentNode = parentNode;
        
        return edgesToKeep.Any() ? true : nodesToVisit.Contains(currentNode);
    }
    
    static int FindInternalNode(Node[] graph, HashSet<int> nodesToVisit) {
        return FindInternalNodeImpl(graph, nodesToVisit, 0, -1);
    }

    static int FindInternalNodeImpl(Node[] graph, HashSet<int> nodesToVisit, int currentNode, int parentNode) {
        foreach (var childNode in graph[currentNode].Edges.Select(e => e.Node).Where(n => n != parentNode)) {
            var internalNode = FindInternalNodeImpl(graph, nodesToVisit, childNode, currentNode);
            
            if (internalNode != -1) {
                return internalNode;
            }
        }
        
        return nodesToVisit.Contains(currentNode) ? parentNode : -1;
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] nk = Console.ReadLine().Split(' ');

        int n = Convert.ToInt32(nk[0]);

        int k = Convert.ToInt32(nk[1]);

        int[] city = Array.ConvertAll(Console.ReadLine().Split(' '), cityTemp => Convert.ToInt32(cityTemp))
        ;

        int[][] roads = new int[n-1][];

        for (int roadsRowItr = 0; roadsRowItr < n-1; roadsRowItr++) {
            roads[roadsRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), roadsTemp => Convert.ToInt32(roadsTemp));
        }

        int result = JeanisRoute(city, roads);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Jeanie’s Route Java Solution

import java.util.Scanner;
import java.util.Queue;
import java.util.ArrayDeque;

class Solution{
    static boolean[] prune(int[][][] adj, boolean[] isLett){
    int n=adj.length;
    int[] degree=new int[n];
    for(int i=0;i<n;++i) degree[i]=adj[i].length;
    boolean[] rem=new boolean[n];
    Queue<Integer> q=new ArrayDeque<>();
    for(int i=0;i<n;++i){
        if(!isLett[i] && degree[i]==1) q.add(i);
    }
    while(!q.isEmpty()){
        int leaf=q.remove();
        rem[leaf]=true;
        for(int[] edge: adj[leaf]){
        int node=edge[0];
        if(isLett[node]) break;
        else if(!rem[node]){
            if(--degree[node] == 1){
            q.add(node);
            break;
            }
        }
        }
    }
    return rem;
    }
    static int[] bfs(int[][][] adj, boolean[] rem, int source){
    int n=adj.length, unvis=-1;
    int[] dist=new int[n];
    for(int i=0;i<n;++i) dist[i]=unvis;
    Queue<Integer> q=new ArrayDeque<>();
    q.add(source);
    dist[source]=0;
    int best=0, total=0;
    while(!q.isEmpty()){
        int x=q.remove();
        for(int[] edge: adj[x]){
        int to=edge[0];
        if(!rem[to] && dist[to]==unvis){
            int weight=edge[1];
            total+=weight;
            q.add(to);
            dist[to]=dist[x]+weight;
            if(dist[to]>dist[best]) best=to;
        }
        }
    }
    int[] result={total,dist[best],best};
    return result;
    }
    static int solve(int[][][] adj, int[] lett){
    boolean[] isLett=new boolean[adj.length];
    for(int i: lett) isLett[i]=true;    
    boolean[] rem=prune(adj,isLett);
    int[] result=bfs(adj,rem,lett[0]);
    int totalWeight=result[0], sink=result[2];
    result=bfs(adj,rem,sink);
    int diameter=result[1];
    return 2*totalWeight-diameter;
    }
    static int[][][] weightedAdjacency(int n, int[] from, int[] to, int[] d){
    int[] count=new int[n];
    for(int f: from) ++count[f];
    for(int t: to) ++count[t];
    int[][][] adj=new int[n][][];
    for(int i=0;i<n;++i) adj[i]=new int[count[i]][];
    for(int i=0;i<from.length;++i){
        adj[from[i]][--count[from[i]]]=new int[]{to[i],d[i]};
        adj[to[i]][--count[to[i]]]=new int[]{from[i],d[i]};
    }
    return adj;
    }
    public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt(), k=sc.nextInt();
    int[] lett=new int[k];
    for(int i=0;i<k;++i) lett[i]=sc.nextInt()-1;
    int[] from=new int[n-1], to=new int[n-1], d=new int[n-1];
    for(int i=0;i<n-1;++i){
        from[i]=sc.nextInt()-1;
        to[i]=sc.nextInt()-1;
        d[i]=sc.nextInt();
    }
    sc.close();
    int[][][] adj=weightedAdjacency(n,from,to,d);
    System.out.println(solve(adj,lett));
    }
}

Jeanie’s Route JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the jeanisRoute function below.
 */
function jeanisRoute(n, cities, graph) {
    const citiesMap = {};
    for (let i = 0; i < cities.length; i++) {
        citiesMap[cities[i]] = true;
    }

    const visited = {};

    const stack = Array(n + 1);
    stack.size = 0;

    const result = Array(n + 1);
    result[0] = {
        result: 0,
        max: [],
        maxD: 0
    };


    push(stack, {v: cities[0], p: 0, w: 0});

    while (stack.size > 0) {
        let cur = pop(stack);

        if (visited[cur.v]) {
            const res = result[cur.v];

            res.max.sort((a, b) => a > b ? -1 : 1);

            if (res.max.length > 1) {
                res.maxD = Math.max(res.maxD, res.max[0] + res.max[1]);
            }

            // console.log(v, citiesMap[v], result, maxD, max);

            if (res.result === 0) {
                if (citiesMap[cur.v]) {
                    applyToParent(result[cur.p], { res: 0, max: 0, maxD: 0 }, cur.w);
                }
            } else {
                applyToParent(result[cur.p], { 
                    res: res.result, 
                    max: res.max[0] || 0, 
                    maxD: res.maxD }, cur.w);
            }

            delete result[cur.v];
        } else {
            push(stack, {v: cur.v, p: cur.p, w: cur.w});

            visited[cur.v] = true;
            result[cur.v] = {
                result: 0,
                max: [],
                maxD: 0
            };

            const edges = graph[cur.v];

            for (let i = 0; i < edges.length; i++) {
                const edge = edges[i];

                if (!visited[edge.v]) {
                    push(stack, {v: edge.v, p: cur.v, w: edge.w});
                }
            }
        }
    }

    const ans = result[0];//dfs(graph, visited, cities[0], citiesMap);

    // console.log(ans);

    return ans.result - Math.max(ans.maxD, ans.max[0]);
}

function pop(stack) {
    return stack[--stack.size];
}

function push(stack, value) {
    stack[stack.size++] = value;
}

function applyToParent(res, ans, w) {
    res.result += ans.res + w * 2;
    res.max.push(ans.max + w);
    res.maxD = Math.max(res.maxD, ans.maxD);
}

function dfs(graph, visited, v, citiesMap) {
    let result = 0;
    let max = [];
    let maxD = 0;

    const edges = graph[v];
    visited[v] = true;

    for (let i = 0; i < edges.length; i++) {
        const edge = edges[i];

        if (!visited[edge.v]) {
            const ans = dfs(graph, visited, edges[i].v, citiesMap);

            if (ans) {
            }
        }
    }

    max.sort((a, b) => a > b ? -1 : 1);

    if (max.length > 1) {
        maxD = Math.max(maxD, max[0] + max[1]);
    }

    // console.log(v, citiesMap[v], result, maxD, max);

    if (result === 0) {
        if (citiesMap[v]) {
            return { res: 0, max: 0, maxD: 0 }
        }
        
        return false;
    }

    return { res: result, max: max[0] || 0, maxD: maxD };
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const nk = readLine().split(' ');

    const n = parseInt(nk[0], 10);

    const k = parseInt(nk[1], 10);

    const city = readLine().split(' ').map(cityTemp => parseInt(cityTemp, 10));

    const graph = {};
    for (let i = 1; i <= n; i++) {
        graph[i] = [];
    }

    for (let roadsRowItr = 0; roadsRowItr < n-1; roadsRowItr++) {
        const edge = readLine().split(' ').map(roadsTemp => parseInt(roadsTemp, 10));

        graph[edge[0]].push({v: edge[1], w: edge[2]});
        graph[edge[1]].push({v: edge[0], w: edge[2]});
    }

    let result = jeanisRoute(n, city, graph);

    ws.write(result + "\n");

    ws.end();
}

Jeanie’s Route Python Solution

def dfs(root, adj, nodes):
    parent = {root: None}
    depth = {root: 0}
    dist = {root: 0}
    
    stack = [root]
    while len(stack):
        curr = stack.pop()
        curr_depth = depth[curr]
        curr_dist = dist[curr]
        
        for nei in adj[curr]:
            if nei != parent[curr] and nei in nodes:
                parent[nei] = curr
                depth[nei] = curr_depth + 1
                dist[nei] = curr_dist + adj[curr][nei]
                stack.append(nei)
        
    return parent, depth, dist

n, k = map(int, input().split())
targets = set(map(int, input().split()))

nodes = set(range(1, n + 1))
adj = {x: dict() for x in nodes}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    adj[a][b] = c
    adj[b][a] = c
    
parent, depth, dist = dfs(list(targets)[0], adj, nodes)

nodes_sorted = sorted(nodes, key=lambda x: depth[x], reverse=True)
for node in nodes_sorted:
    num_connected = len([x for x in adj[node] if x in nodes])
    if node not in targets and num_connected == 1:
        nodes.remove(node)
        del adj[node]

furthest_node = max(nodes, key=lambda x: dist[x])

# Re-root the tree at the last node
parent, depth, dist = dfs(furthest_node, adj, nodes)

# Get the new furthest
furthest_node = max(nodes, key=lambda x: dist[x])
largest_distance = dist[furthest_node]

tot_sum = 0
for node in nodes:
    for nei in adj[node]:
        if nei in nodes:
            tot_sum += adj[node][nei]

print(tot_sum - largest_distance)
c C# C++ HackerRank Solutions java javascript python

Leave a Reply