Dijkstra's algorithm

import heapq

def shortest_distances(n, edges, src):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [-1] * n                     # -1 until settled
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if dist[u] != -1:
            continue                    # stale entry: u is already final
        dist[u] = d                     # smallest unsettled distance: final
        for v, w in adj[u]:
            if dist[v] == -1:
                heapq.heappush(heap, (d + w, v))
    return dist

#include <functional>
#include <queue>
#include <utility>
#include <vector>

std::vector<long long> solve(int n, const std::vector<std::vector<int>>& edges, int src) {
    std::vector<std::vector<std::pair<int, int>>> adj(n);
    for (const auto& e : edges) adj[e[0]].push_back({e[1], e[2]});
    std::vector<long long> dist(n, -1);                 // -1 until settled
    using Entry = std::pair<long long, int>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
    heap.push({0, src});
    while (!heap.empty()) {
        auto [d, u] = heap.top();
        heap.pop();
        if (dist[u] != -1) continue;                    // stale entry
        dist[u] = d;                                    // final
        for (auto [v, w] : adj[u])
            if (dist[v] == -1) heap.push({d + w, v});
    }
    return dist;
}

import java.util.*;

class Solution {
    public int[] shortestDistances(int n, int[][] edges, int src) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(new int[]{e[1], e[2]});
        int[] dist = new int[n];
        Arrays.fill(dist, -1);                          // -1 until settled
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.add(new int[]{0, src});
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int d = top[0], u = top[1];
            if (dist[u] != -1) continue;                // stale entry
            dist[u] = d;                                // final
            for (int[] e : adj.get(u))
                if (dist[e[0]] == -1) heap.add(new int[]{d + e[1], e[0]});
        }
        return dist;
    }
}

function shortestDistances(n, edges, src) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) adj[u].push([v, w]);
  // binary min-heap of [distance, node]
  const heap = [];
  const push = e => { heap.push(e); let i = heap.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (heap[p][0] <= heap[i][0]) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } };
  const pop = () => { const top = heap[0], last = heap.pop(); if (heap.length) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < heap.length && heap[l][0] < heap[m][0]) m = l; if (r < heap.length && heap[r][0] < heap[m][0]) m = r; if (m === i) break; [heap[m], heap[i]] = [heap[i], heap[m]]; i = m; } } return top; };
  const dist = new Array(n).fill(-1);  // -1 until settled
  push([0, src]);
  while (heap.length) {
    const [d, u] = pop();
    if (dist[u] !== -1) continue;      // stale entry
    dist[u] = d;                       // final
    for (const [v, w] of adj[u]) if (dist[v] === -1) push([d + w, v]);
  }
  return dist;
}

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn solve(n: i64, edges: &[[i64; 3]], src: i64) -> Vec<i64> {
    let n = n as usize;
    let mut adj = vec![Vec::new(); n];
    for e in edges {
        adj[e[0] as usize].push((e[1] as usize, e[2]));
    }
    let mut dist = vec![-1i64; n];                      // -1 until settled
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i64, src as usize)));
    while let Some(Reverse((d, u))) = heap.pop() {
        if dist[u] != -1 {
            continue;                                   // stale entry
        }
        dist[u] = d;                                    // final
        for &(v, w) in &adj[u] {
            if dist[v] == -1 {
                heap.push(Reverse((d + w, v)));
            }
        }
    }
    dist
}

import qualified Data.Map.Strict as M
import qualified Data.Set as S

solve :: Int -> [[Int]] -> Int -> [Int]
solve n edges src = [M.findWithDefault (-1) v final | v <- [0 .. n - 1]]
  where
    adj = M.fromListWith (++) [(u, [(v, w)]) | [u, v, w] <- edges]
    final = go (S.singleton (0, src)) M.empty
    -- the set of (distance, node) is the heap; the map holds settled nodes
    go heap dist = case S.minView heap of
      Nothing -> dist
      Just ((d, u), rest)
        | M.member u dist -> go rest dist                     -- stale entry
        | otherwise ->
            let dist' = M.insert u d dist
                next = [(d + w, v) | (v, w) <- M.findWithDefault [] u adj, not (M.member v dist')]
            in go (foldr S.insert rest next) dist'