Transport (TLAC) Complete Solution using Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution {

    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int n = fs.nextInt();
        Graph g = new Graph(n);
        g.readCities(fs);
        g.addEdgeWeight(fs);
        g.convertStartEnd(fs);
        g.findPath();
        g.printPath(out);
        out.close();
    }

    static class Graph {

        int n;
        String[] cities;
        int[] connected;
        LinkedList<Integer> adj[];
        int[][] cost;
        boolean[] visited;
        int start;
        int end;
        LinkedList<Integer> currentPath;
        LinkedList<String> res;
        int minWeight;
        int minCount;

        Graph(int n) {
            this.n = n;
            cities = new String[n];
            connected = new int[n];
            adj = new LinkedList[n];
            for(int i = 0; i < n; i++) {
                adj[i] = new LinkedList();
            }
            cost = new int[n][n];
            for(int i = 0; i < n; i++) {
                Arrays.fill(cost[i], 0);
            }
            visited = new boolean[n];
            Arrays.fill(visited, false);
            currentPath = new LinkedList<>();
            minWeight = Integer.MAX_VALUE;
            minCount = Integer.MAX_VALUE;
            res = new LinkedList();
        }

        void readCities(FastScanner fs) {
            for(int i = 0; i < n; i++) {
                cities[i] = fs.next();
                connected[i] = fs.nextInt();
            }
        }

        int convertCityToNum(String city) {
            for(int i = 0; i < cities.length; i++) {
                if(city.equals(cities[i])) {
                    return i;
                }
            }
            return -1;
        }

        void addEdgeWeight(FastScanner fs) {
            for(int u = 0; u < n; u++) {
                for(int i = 0; i < connected[u]; i++) {
                    String city = fs.next();
                    int weight = fs.nextInt();
                    int v = convertCityToNum(city);
                    adj[u].add(v);
                    cost[u][v] = weight;
                }
            }
        }

        void convertStartEnd(FastScanner fs) {
            start = convertCityToNum(fs.next());
            end = convertCityToNum(fs.next());
        }

        void findPath() {
            DFS(start, end);
        }

        void DFS(int u, int d) {
            visited[u] = true;
            currentPath.add(u);
            if(u == d) {
                Object[] objectArray = currentPath.toArray();
                Integer[] path = Arrays.copyOf(objectArray, objectArray.length, Integer[].class);
                updatePath(path);
            }
            else {
                for(int v : adj[u]) {
                    if(!visited[v]) {
                        DFS(v, d);
                    }
                }
            }
            visited[u] = false;
            currentPath.removeLast();
        }

        void updatePath(Integer[] path) {
            int total = 0;
            LinkedList<String> collect = new LinkedList<>();
            int sz = path.length;
            for(int i = 0; i < sz; i++) {
                if(i < sz - 1) {
                    total += cost[path[i]][path[i+1]];
                }
                collect.add(cities[path[i]]);
            }
            if(total < minWeight) {
                minWeight = total;
                minCount = sz;
                res = collect;
            }
            else if(total == minWeight && sz < minCount) {
                minCount = sz;
                res = collect;
            }
        }

        void printPath(PrintWriter out) {
            for(int i = 0; i < res.size(); i++) {
                if(i > 0) {
                    out.print("->");
                }
                out.print(res.get(i));
            }
            out.println();
        }

    }

    static void sort(int[] a) {
        ArrayList<Integer> arr = new ArrayList<>();
        for(int x : a) {
            arr.add(x);
        }
        Collections.sort(arr);
        for(int i = 0; i < a.length; i++) {
            a[i] = arr.get(i);
        }
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while(!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch(IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for(int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch(IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}