import heapq

def dijkstras(graph, src):
    n = len(graph)
    dist = [float('inf')] * n
    dist[src] = 0

    pq = []
    heapq.heappush(pq, (0, src))  # (distance, node)

    while pq:
        node_dist, node = heapq.heappop(pq)

        if node_dist > dist[node]:
            continue

        for neighbor, weight in graph[node]:
            new_dist = dist[node] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return dist


graph = [
    [(1, 2), (2, 4)],
    [(3, 7), (2, 1)],
    [(4, 3), (5, 1)],
    [(6, 1)],
    [(3, 2), (6, 5)],
    [(3, 3), (6, 8)],
    []
]

print(dijkstras(graph, 0))

    

import java.util.*;

class Solution {
    static int[] shortestDistance(List> graph, int src) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        Queue q = new LinkedList<>();
        q.add(src);

        while (!q.isEmpty()) {
            int curr = q.poll();
            for (int neighbor : graph.get(curr)) {
                if (dist[neighbor] == Integer.MAX_VALUE) {
                    dist[neighbor] = dist[curr] + 1;
                    q.add(neighbor);
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        List> graph = new ArrayList<>();

        graph.add(Arrays.asList(1, 2));
        graph.add(Arrays.asList(3));
        graph.add(Arrays.asList(4));
        graph.add(Arrays.asList(5));
        graph.add(Arrays.asList(3));
        graph.add(new ArrayList<>());

        System.out.println(Arrays.toString(shortestDistance(graph, 0)));
    }
}
  

#include <bits/stdc++.h>
using namespace std;

vector dijkstras(vector>>& graph, int src) {
    int n = graph.size();
    vector dist(n, INT_MAX);
    dist[src] = 0;

    priority_queue,
        vector>,
        greater>> pq;

    pq.push({0, src});

    while (!pq.empty()) {
        auto [nodeDist, node] = pq.top();
        pq.pop();

        if (nodeDist > dist[node]) continue;

        for (auto [neighbor, weight] : graph[node]) {
            int newDist = dist[node] + weight;
            if (newDist < dist[neighbor]) {
                dist[neighbor] = newDist;
                pq.push({newDist, neighbor});
            }
        }
    }
    return dist;
}

int main() {
    vector>> graph(7);

    graph[0] = {{1,2},{2,4}};
    graph[1] = {{3,7},{2,1}};
    graph[2] = {{4,3},{5,1}};
    graph[3] = {{6,1}};
    graph[4] = {{3,2},{6,5}};
    graph[5] = {{3,3},{6,8}};

    vector res = dijkstras(graph, 0);
    for (int x : res) cout << x << " ";
}

#include <stdio.h>
#include <limits.h>

#define V 7
#define E 12

typedef struct {
    int node, dist;
} HeapNode;

HeapNode heap[100];
int heapSize = 0;

void swap(int i, int j) {
    HeapNode temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
}

void push(int node, int dist) {
    heap[heapSize++] = (HeapNode){node, dist};
    int i = heapSize - 1;

    while (i > 0 && heap[(i - 1) / 2].dist > heap[i].dist) {
        swap(i, (i - 1) / 2);
        i = (i - 1) / 2;
    }
}

HeapNode pop() {
    HeapNode root = heap[0];
    heap[0] = heap[--heapSize];

    int i = 0;
    while (1) {
        int smallest = i;
        int l = 2*i + 1, r = 2*i + 2;

        if (l < heapSize && heap[l].dist < heap[smallest].dist)
            smallest = l;
        if (r < heapSize && heap[r].dist < heap[smallest].dist)
            smallest = r;

        if (smallest == i) break;
        swap(i, smallest);
        i = smallest;
    }
    return root;
}

int main() {
    int graph[V][V] = {
        {0,2,4,0,0,0,0},
        {0,0,1,7,0,0,0},
        {0,0,0,0,3,1,0},
        {0,0,0,0,0,0,1},
        {0,0,0,2,0,0,5},
        {0,0,0,3,0,0,8},
        {0,0,0,0,0,0,0}
    };

    int dist[V];
    for (int i = 0; i < V; i++) dist[i] = INT_MAX;
    dist[0] = 0;

    push(0, 0);

    while (heapSize) {
        HeapNode curr = pop();
        int u = curr.node;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                push(v, dist[v]);
            }
        }
    }

    for (int i = 0; i < V; i++)
        printf("%d ", dist[i]);

    return 0;
}

using System;
using System.Collections.Generic;

class Solution {
    static int[] Dijkstras(List<(int,int)>[] graph, int src) {
        int n = graph.Length;
        int[] dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[src] = 0;

        var pq = new PriorityQueue();
        pq.Enqueue(src, 0);

        while (pq.Count > 0) {
            pq.TryDequeue(out int node, out int nodeDist);

            if (nodeDist > dist[node]) continue;

            foreach (var (neighbor, weight) in graph[node]) {
                int newDist = dist[node] + weight;
                if (newDist < dist[neighbor]) {
                    dist[neighbor] = newDist;
                    pq.Enqueue(neighbor, newDist);
                }
            }
        }
        return dist;
    }

    static void Main() {
        var graph = new List<(int,int)>[7];
        for (int i = 0; i < 7; i++) graph[i] = new();

        graph[0].Add((1,2));
        graph[0].Add((2,4));
        graph[1].Add((3,7));
        graph[1].Add((2,1));
        graph[2].Add((4,3));
        graph[2].Add((5,1));
        graph[3].Add((6,1));
        graph[4].Add((3,2));
        graph[4].Add((6,5));
        graph[5].Add((3,3));
        graph[5].Add((6,8));

        Console.WriteLine(string.Join(" ", Dijkstras(graph, 0)));
    }
}