dijkstra

// User function Template for Java

class Solution {
    static class Pair {
        int distance;
        int node;

        Pair(int distance, int node) {
            this.distance = distance;
            this.node = node;
        }
    }

    public int[] dijkstra(int V, int[][] edges, int src) {
        // Step 1: Build Adjacency List
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adj.get(u).add(new int[]{v, w});
            adj.get(v).add(new int[]{u, w}); // remove this if graph is directed
        }

        // Step 2: Dijkstra using Min Heap
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.distance - b.distance);
        pq.add(new Pair(0, src));

        while (!pq.isEmpty()) {
            Pair current = pq.poll();
            int u = current.node;
            int d = current.distance;

            for (int[] neighbor : adj.get(u)) {
                int v = neighbor[0];
                int wt = neighbor[1];

                if (d + wt < dist[v]) {
                    dist[v] = d + wt;
                    pq.add(new Pair(dist[v], v));
                }
            }
        }

        return dist;
    }
}