// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
}
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// We may have queued this node more than once; ignore stale, longer copies.
}
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// We may have queued this node more than once; ignore stale, longer copies.
if cur.dist > dist[cur.node] {
continue
}
}
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// We may have queued this node more than once; ignore stale, longer copies.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
}
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// We may have queued this node more than once; ignore stale, longer copies.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for _, e := range graph[cur.node] {
if nd := cur.dist + e.weight; nd < dist[e.to] {
dist[e.to] = nd
heap.Push(pq, Item{node: e.to, dist: nd})
}
}
}
return dist // O((V + E) log V)
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// We may have queued this node more than once; ignore stale, longer copies.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for _, e := range graph[cur.node] {
if nd := cur.dist + e.weight; nd < dist[e.to] {
dist[e.to] = nd
heap.Push(pq, Item{node: e.to, dist: nd})
}
}
}
return dist // O((V + E) log V)
}
// The rest is the container/heap plumbing: an Item and a slice that implements
// heap.Interface as a MIN-heap ordered by dist.// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// We may have queued this node more than once; ignore stale, longer copies.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for _, e := range graph[cur.node] {
if nd := cur.dist + e.weight; nd < dist[e.to] {
dist[e.to] = nd
heap.Push(pq, Item{node: e.to, dist: nd})
}
}
}
return dist // O((V + E) log V)
}
// The rest is the container/heap plumbing: an Item and a slice that implements
// heap.Interface as a MIN-heap ordered by dist.
type Item struct {
node, dist int
}
type PriorityQueue []Item// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// We may have queued this node more than once; ignore stale, longer copies.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for _, e := range graph[cur.node] {
if nd := cur.dist + e.weight; nd < dist[e.to] {
dist[e.to] = nd
heap.Push(pq, Item{node: e.to, dist: nd})
}
}
}
return dist // O((V + E) log V)
}
// The rest is the container/heap plumbing: an Item and a slice that implements
// heap.Interface as a MIN-heap ordered by dist.
type Item struct {
node, dist int
}
type PriorityQueue []Item
// Len/Less/Swap define the ordering. Less by dist is what makes it a min-heap.// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// We may have queued this node more than once; ignore stale, longer copies.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for _, e := range graph[cur.node] {
if nd := cur.dist + e.weight; nd < dist[e.to] {
dist[e.to] = nd
heap.Push(pq, Item{node: e.to, dist: nd})
}
}
}
return dist // O((V + E) log V)
}
// The rest is the container/heap plumbing: an Item and a slice that implements
// heap.Interface as a MIN-heap ordered by dist.
type Item struct {
node, dist int
}
type PriorityQueue []Item
// Len/Less/Swap define the ordering. Less by dist is what makes it a min-heap.
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// We may have queued this node more than once; ignore stale, longer copies.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for _, e := range graph[cur.node] {
if nd := cur.dist + e.weight; nd < dist[e.to] {
dist[e.to] = nd
heap.Push(pq, Item{node: e.to, dist: nd})
}
}
}
return dist // O((V + E) log V)
}
// The rest is the container/heap plumbing: an Item and a slice that implements
// heap.Interface as a MIN-heap ordered by dist.
type Item struct {
node, dist int
}
type PriorityQueue []Item
// Len/Less/Swap define the ordering. Less by dist is what makes it a min-heap.
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
// Push/Pop operate on the END of the slice; heap.Push/heap.Pop handle sifting.// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Best-known distance to each node; everything starts unreachable.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// A min-heap always hands back the closest unfinished node next.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// We may have queued this node more than once; ignore stale, longer copies.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for _, e := range graph[cur.node] {
if nd := cur.dist + e.weight; nd < dist[e.to] {
dist[e.to] = nd
heap.Push(pq, Item{node: e.to, dist: nd})
}
}
}
return dist // O((V + E) log V)
}
// The rest is the container/heap plumbing: an Item and a slice that implements
// heap.Interface as a MIN-heap ordered by dist.
type Item struct {
node, dist int
}
type PriorityQueue []Item
// Len/Less/Swap define the ordering. Less by dist is what makes it a min-heap.
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
// Push/Pop operate on the END of the slice; heap.Push/heap.Pop handle sifting.
func (pq *PriorityQueue) Push(x any) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() any {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[:n-1]
return item
}import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.
pq = MinPQ(src, 0)
while len(pq) > 0:
node, cur_dist = pq.pop()import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.
pq = MinPQ(src, 0)
while len(pq) > 0:
node, cur_dist = pq.pop()
# We may have queued this node more than once; ignore stale, longer copies.import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.
pq = MinPQ(src, 0)
while len(pq) > 0:
node, cur_dist = pq.pop()
# We may have queued this node more than once; ignore stale, longer copies.
if cur_dist > dist[node]:
continueimport heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.
pq = MinPQ(src, 0)
while len(pq) > 0:
node, cur_dist = pq.pop()
# We may have queued this node more than once; ignore stale, longer copies.
if cur_dist > dist[node]:
continue
# Relax each neighbor: if going through cur is shorter, record and queue it.import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.
pq = MinPQ(src, 0)
while len(pq) > 0:
node, cur_dist = pq.pop()
# We may have queued this node more than once; ignore stale, longer copies.
if cur_dist > dist[node]:
continue
# Relax each neighbor: if going through cur is shorter, record and queue it.
for to, weight in graph[node]:
nd = cur_dist + weight
if nd < dist[to]:
dist[to] = nd
pq.push(to, nd)
return dist # O((V + E) log V)import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.
pq = MinPQ(src, 0)
while len(pq) > 0:
node, cur_dist = pq.pop()
# We may have queued this node more than once; ignore stale, longer copies.
if cur_dist > dist[node]:
continue
# Relax each neighbor: if going through cur is shorter, record and queue it.
for to, weight in graph[node]:
nd = cur_dist + weight
if nd < dist[to]:
dist[to] = nd
pq.push(to, nd)
return dist # O((V + E) log V)
# The rest is the priority-queue plumbing: heapq does the sifting on a plain
# list, MinPQ just gives it a name.import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.
pq = MinPQ(src, 0)
while len(pq) > 0:
node, cur_dist = pq.pop()
# We may have queued this node more than once; ignore stale, longer copies.
if cur_dist > dist[node]:
continue
# Relax each neighbor: if going through cur is shorter, record and queue it.
for to, weight in graph[node]:
nd = cur_dist + weight
if nd < dist[to]:
dist[to] = nd
pq.push(to, nd)
return dist # O((V + E) log V)
# The rest is the priority-queue plumbing: heapq does the sifting on a plain
# list, MinPQ just gives it a name.
class MinPQ:
def __init__(self, node, dist):
self.data = [(dist, node)]import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.
pq = MinPQ(src, 0)
while len(pq) > 0:
node, cur_dist = pq.pop()
# We may have queued this node more than once; ignore stale, longer copies.
if cur_dist > dist[node]:
continue
# Relax each neighbor: if going through cur is shorter, record and queue it.
for to, weight in graph[node]:
nd = cur_dist + weight
if nd < dist[to]:
dist[to] = nd
pq.push(to, nd)
return dist # O((V + E) log V)
# The rest is the priority-queue plumbing: heapq does the sifting on a plain
# list, MinPQ just gives it a name.
class MinPQ:
def __init__(self, node, dist):
self.data = [(dist, node)]
# Entries are (dist, node) tuples: tuples compare left to right, so ordering
# by dist is what makes this a MIN-heap.import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.
pq = MinPQ(src, 0)
while len(pq) > 0:
node, cur_dist = pq.pop()
# We may have queued this node more than once; ignore stale, longer copies.
if cur_dist > dist[node]:
continue
# Relax each neighbor: if going through cur is shorter, record and queue it.
for to, weight in graph[node]:
nd = cur_dist + weight
if nd < dist[to]:
dist[to] = nd
pq.push(to, nd)
return dist # O((V + E) log V)
# The rest is the priority-queue plumbing: heapq does the sifting on a plain
# list, MinPQ just gives it a name.
class MinPQ:
def __init__(self, node, dist):
self.data = [(dist, node)]
# Entries are (dist, node) tuples: tuples compare left to right, so ordering
# by dist is what makes this a MIN-heap.
def __len__(self):
return len(self.data)import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.
pq = MinPQ(src, 0)
while len(pq) > 0:
node, cur_dist = pq.pop()
# We may have queued this node more than once; ignore stale, longer copies.
if cur_dist > dist[node]:
continue
# Relax each neighbor: if going through cur is shorter, record and queue it.
for to, weight in graph[node]:
nd = cur_dist + weight
if nd < dist[to]:
dist[to] = nd
pq.push(to, nd)
return dist # O((V + E) log V)
# The rest is the priority-queue plumbing: heapq does the sifting on a plain
# list, MinPQ just gives it a name.
class MinPQ:
def __init__(self, node, dist):
self.data = [(dist, node)]
# Entries are (dist, node) tuples: tuples compare left to right, so ordering
# by dist is what makes this a MIN-heap.
def __len__(self):
return len(self.data)
# heappush and heappop do the sifting for you.import heapq
# graph[node] = list of (to, weight) edges. Edge weights must be non-negative.
def dijkstra(graph, src):
# Best-known distance to each node; everything starts unreachable.
inf = 10 ** 18
dist = [inf] * len(graph)
dist[src] = 0
# A min-heap always hands back the closest unfinished node next.
pq = MinPQ(src, 0)
while len(pq) > 0:
node, cur_dist = pq.pop()
# We may have queued this node more than once; ignore stale, longer copies.
if cur_dist > dist[node]:
continue
# Relax each neighbor: if going through cur is shorter, record and queue it.
for to, weight in graph[node]:
nd = cur_dist + weight
if nd < dist[to]:
dist[to] = nd
pq.push(to, nd)
return dist # O((V + E) log V)
# The rest is the priority-queue plumbing: heapq does the sifting on a plain
# list, MinPQ just gives it a name.
class MinPQ:
def __init__(self, node, dist):
self.data = [(dist, node)]
# Entries are (dist, node) tuples: tuples compare left to right, so ordering
# by dist is what makes this a MIN-heap.
def __len__(self):
return len(self.data)
# heappush and heappop do the sifting for you.
def push(self, node, dist):
heapq.heappush(self.data, (dist, node))
def pop(self):
dist, node = heapq.heappop(self.data)
return node, dist// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
}
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
}
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
}
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
}
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: JavaScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: JavaScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
class MinPQ {
constructor(node, dist) {
this.data = [{ node, dist }];
}
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: JavaScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
class MinPQ {
constructor(node, dist) {
this.data = [{ node, dist }];
}
// size/less/swap define the ordering. less by dist is what makes it a min-heap.
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: JavaScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
class MinPQ {
constructor(node, dist) {
this.data = [{ node, dist }];
}
// size/less/swap define the ordering. less by dist is what makes it a min-heap.
size() {
return this.data.length;
}
less(i, j) {
return this.data[i].dist < this.data[j].dist;
}
swap(i, j) {
[this.data[i], this.data[j]] = [this.data[j], this.data[i]];
}
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: JavaScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
class MinPQ {
constructor(node, dist) {
this.data = [{ node, dist }];
}
// size/less/swap define the ordering. less by dist is what makes it a min-heap.
size() {
return this.data.length;
}
less(i, j) {
return this.data[i].dist < this.data[j].dist;
}
swap(i, j) {
[this.data[i], this.data[j]] = [this.data[j], this.data[i]];
}
// push appends to the END then sifts up; pop takes the root and sifts down.
}// graph[node] = list of {to, weight} edges. Edge weights must be non-negative.
function dijkstra(graph, src) {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: JavaScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
class MinPQ {
constructor(node, dist) {
this.data = [{ node, dist }];
}
// size/less/swap define the ordering. less by dist is what makes it a min-heap.
size() {
return this.data.length;
}
less(i, j) {
return this.data[i].dist < this.data[j].dist;
}
swap(i, j) {
[this.data[i], this.data[j]] = [this.data[j], this.data[i]];
}
// push appends to the END then sifts up; pop takes the root and sifts down.
push(node, dist) {
this.data.push({ node, dist });
let i = this.data.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (!this.less(i, parent)) {
break;
}
this.swap(i, parent);
i = parent;
}
}
pop() {
const top = this.data[0];
const last = this.data.pop();
if (this.data.length === 0) {
return top;
}
this.data[0] = last;
let i = 0;
for (;;) {
let smallest = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < this.data.length && this.less(l, smallest)) {
smallest = l;
}
if (r < this.data.length && this.less(r, smallest)) {
smallest = r;
}
if (smallest === i) {
break;
}
this.swap(i, smallest);
i = smallest;
}
return top;
}
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
}
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
}
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
}
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
}
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: TypeScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: TypeScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
interface Item {
node: number;
dist: number;
}
class MinPQ {
private data: Item[];
constructor(node: number, dist: number) {
this.data = [{ node, dist }];
}
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: TypeScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
interface Item {
node: number;
dist: number;
}
class MinPQ {
private data: Item[];
constructor(node: number, dist: number) {
this.data = [{ node, dist }];
}
// size/less/swap define the ordering. less by dist is what makes it a min-heap.
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: TypeScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
interface Item {
node: number;
dist: number;
}
class MinPQ {
private data: Item[];
constructor(node: number, dist: number) {
this.data = [{ node, dist }];
}
// size/less/swap define the ordering. less by dist is what makes it a min-heap.
size(): number {
return this.data.length;
}
private less(i: number, j: number): boolean {
return this.data[i].dist < this.data[j].dist;
}
private swap(i: number, j: number): void {
[this.data[i], this.data[j]] = [this.data[j], this.data[i]];
}
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: TypeScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
interface Item {
node: number;
dist: number;
}
class MinPQ {
private data: Item[];
constructor(node: number, dist: number) {
this.data = [{ node, dist }];
}
// size/less/swap define the ordering. less by dist is what makes it a min-heap.
size(): number {
return this.data.length;
}
private less(i: number, j: number): boolean {
return this.data[i].dist < this.data[j].dist;
}
private swap(i: number, j: number): void {
[this.data[i], this.data[j]] = [this.data[j], this.data[i]];
}
// push appends to the END then sifts up; pop takes the root and sifts down.
}// graph[node] = list of outgoing edges. Edge weights must be non-negative.
interface Edge {
to: number;
weight: number;
}
function dijkstra(graph: Edge[][], src: number): number[] {
// Best-known distance to each node; everything starts unreachable.
const inf = 1e18;
const dist: number[] = new Array(graph.length).fill(inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
const pq = new MinPQ(src, 0);
while (pq.size() > 0) {
const cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const e of graph[cur.node]) {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: TypeScript has no heap, so MinPQ is
// a binary MIN-heap on a plain array, ordered by dist.
interface Item {
node: number;
dist: number;
}
class MinPQ {
private data: Item[];
constructor(node: number, dist: number) {
this.data = [{ node, dist }];
}
// size/less/swap define the ordering. less by dist is what makes it a min-heap.
size(): number {
return this.data.length;
}
private less(i: number, j: number): boolean {
return this.data[i].dist < this.data[j].dist;
}
private swap(i: number, j: number): void {
[this.data[i], this.data[j]] = [this.data[j], this.data[i]];
}
// push appends to the END then sifts up; pop takes the root and sifts down.
push(node: number, dist: number): void {
this.data.push({ node, dist });
let i = this.data.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (!this.less(i, parent)) {
break;
}
this.swap(i, parent);
i = parent;
}
}
pop(): Item {
const top = this.data[0];
// pop() is only called on a non-empty heap, so this is always an Item.
const last = this.data.pop() as Item;
if (this.data.length === 0) {
return top;
}
this.data[0] = last;
let i = 0;
for (;;) {
let smallest = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < this.data.length && this.less(l, smallest)) {
smallest = l;
}
if (r < this.data.length && this.less(r, smallest)) {
smallest = r;
}
if (smallest === i) {
break;
}
this.swap(i, smallest);
i = smallest;
}
return top;
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
}
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
}
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist() > dist[cur.node()]) {
continue;
}
}
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist() > dist[cur.node()]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
}
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist() > dist[cur.node()]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (Edge e : graph.get(cur.node())) {
long nd = cur.dist() + e.weight();
if (nd < dist[e.to()]) {
dist[e.to()] = nd;
pq.push(e.to(), nd);
}
}
}
return dist; // O((V + E) log V)
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist() > dist[cur.node()]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (Edge e : graph.get(cur.node())) {
long nd = cur.dist() + e.weight();
if (nd < dist[e.to()]) {
dist[e.to()] = nd;
pq.push(e.to(), nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: java.util.PriorityQueue does the
// sifting, MinPQ just gives it a name.
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist() > dist[cur.node()]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (Edge e : graph.get(cur.node())) {
long nd = cur.dist() + e.weight();
if (nd < dist[e.to()]) {
dist[e.to()] = nd;
pq.push(e.to(), nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: java.util.PriorityQueue does the
// sifting, MinPQ just gives it a name.
record Item(int node, long dist) {}
static class MinPQ {
private final PriorityQueue<Item> heap;
MinPQ(int node, long dist) {
heap = new PriorityQueue<Item>(MinPQ::byDist);
heap.add(new Item(node, dist));
}
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist() > dist[cur.node()]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (Edge e : graph.get(cur.node())) {
long nd = cur.dist() + e.weight();
if (nd < dist[e.to()]) {
dist[e.to()] = nd;
pq.push(e.to(), nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: java.util.PriorityQueue does the
// sifting, MinPQ just gives it a name.
record Item(int node, long dist) {}
static class MinPQ {
private final PriorityQueue<Item> heap;
MinPQ(int node, long dist) {
heap = new PriorityQueue<Item>(MinPQ::byDist);
heap.add(new Item(node, dist));
}
// byDist defines the ordering. Comparing by dist is what makes it a min-heap.
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist() > dist[cur.node()]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (Edge e : graph.get(cur.node())) {
long nd = cur.dist() + e.weight();
if (nd < dist[e.to()]) {
dist[e.to()] = nd;
pq.push(e.to(), nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: java.util.PriorityQueue does the
// sifting, MinPQ just gives it a name.
record Item(int node, long dist) {}
static class MinPQ {
private final PriorityQueue<Item> heap;
MinPQ(int node, long dist) {
heap = new PriorityQueue<Item>(MinPQ::byDist);
heap.add(new Item(node, dist));
}
// byDist defines the ordering. Comparing by dist is what makes it a min-heap.
private static int byDist(Item a, Item b) {
return Long.compare(a.dist(), b.dist());
}
int size() {
return heap.size();
}
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist() > dist[cur.node()]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (Edge e : graph.get(cur.node())) {
long nd = cur.dist() + e.weight();
if (nd < dist[e.to()]) {
dist[e.to()] = nd;
pq.push(e.to(), nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: java.util.PriorityQueue does the
// sifting, MinPQ just gives it a name.
record Item(int node, long dist) {}
static class MinPQ {
private final PriorityQueue<Item> heap;
MinPQ(int node, long dist) {
heap = new PriorityQueue<Item>(MinPQ::byDist);
heap.add(new Item(node, dist));
}
// byDist defines the ordering. Comparing by dist is what makes it a min-heap.
private static int byDist(Item a, Item b) {
return Long.compare(a.dist(), b.dist());
}
int size() {
return heap.size();
}
// add() and poll() do the sifting for you.
}
}import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
// graph.get(node) = list of outgoing edges. Edge weights must be non-negative.
record Edge(int to, int weight) {}
public long[] dijkstra(List<List<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
final long inf = (long) 1e18;
long[] dist = new long[graph.size()];
Arrays.fill(dist, inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist() > dist[cur.node()]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (Edge e : graph.get(cur.node())) {
long nd = cur.dist() + e.weight();
if (nd < dist[e.to()]) {
dist[e.to()] = nd;
pq.push(e.to(), nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: java.util.PriorityQueue does the
// sifting, MinPQ just gives it a name.
record Item(int node, long dist) {}
static class MinPQ {
private final PriorityQueue<Item> heap;
MinPQ(int node, long dist) {
heap = new PriorityQueue<Item>(MinPQ::byDist);
heap.add(new Item(node, dist));
}
// byDist defines the ordering. Comparing by dist is what makes it a min-heap.
private static int byDist(Item a, Item b) {
return Long.compare(a.dist(), b.dist());
}
int size() {
return heap.size();
}
// add() and poll() do the sifting for you.
void push(int node, long dist) {
heap.add(new Item(node, dist));
}
Item pop() {
return heap.poll();
}
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.Count > 0) {
Item cur = pq.Pop();
}
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.Count > 0) {
Item cur = pq.Pop();
// We may have queued this node more than once; ignore stale, longer copies.
}
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.Count > 0) {
Item cur = pq.Pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.Dist > dist[cur.Node]) {
continue;
}
}
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.Count > 0) {
Item cur = pq.Pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.Dist > dist[cur.Node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
}
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.Count > 0) {
Item cur = pq.Pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.Dist > dist[cur.Node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
foreach (Edge e in graph[cur.Node]) {
long nd = cur.Dist + e.Weight;
if (nd < dist[e.To]) {
dist[e.To] = nd;
pq.Push(e.To, nd);
}
}
}
return dist; // O((V + E) log V)
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.Count > 0) {
Item cur = pq.Pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.Dist > dist[cur.Node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
foreach (Edge e in graph[cur.Node]) {
long nd = cur.Dist + e.Weight;
if (nd < dist[e.To]) {
dist[e.To] = nd;
pq.Push(e.To, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: PriorityQueue<TElement, TPriority>
// does the sifting, MinPQ just gives it a name.
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.Count > 0) {
Item cur = pq.Pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.Dist > dist[cur.Node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
foreach (Edge e in graph[cur.Node]) {
long nd = cur.Dist + e.Weight;
if (nd < dist[e.To]) {
dist[e.To] = nd;
pq.Push(e.To, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: PriorityQueue<TElement, TPriority>
// does the sifting, MinPQ just gives it a name.
public record Item(int Node, long Dist);
public class MinPQ {
private readonly PriorityQueue<Item, long> heap;
public MinPQ(int node, long dist) {
heap = new PriorityQueue<Item, long>();
heap.Enqueue(new Item(node, dist), dist);
}
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.Count > 0) {
Item cur = pq.Pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.Dist > dist[cur.Node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
foreach (Edge e in graph[cur.Node]) {
long nd = cur.Dist + e.Weight;
if (nd < dist[e.To]) {
dist[e.To] = nd;
pq.Push(e.To, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: PriorityQueue<TElement, TPriority>
// does the sifting, MinPQ just gives it a name.
public record Item(int Node, long Dist);
public class MinPQ {
private readonly PriorityQueue<Item, long> heap;
public MinPQ(int node, long dist) {
heap = new PriorityQueue<Item, long>();
heap.Enqueue(new Item(node, dist), dist);
}
// The priority IS the dist, and PriorityQueue always dequeues the smallest
// priority first — that is what makes it a min-heap.
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.Count > 0) {
Item cur = pq.Pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.Dist > dist[cur.Node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
foreach (Edge e in graph[cur.Node]) {
long nd = cur.Dist + e.Weight;
if (nd < dist[e.To]) {
dist[e.To] = nd;
pq.Push(e.To, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: PriorityQueue<TElement, TPriority>
// does the sifting, MinPQ just gives it a name.
public record Item(int Node, long Dist);
public class MinPQ {
private readonly PriorityQueue<Item, long> heap;
public MinPQ(int node, long dist) {
heap = new PriorityQueue<Item, long>();
heap.Enqueue(new Item(node, dist), dist);
}
// The priority IS the dist, and PriorityQueue always dequeues the smallest
// priority first — that is what makes it a min-heap.
public int Count => heap.Count;
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.Count > 0) {
Item cur = pq.Pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.Dist > dist[cur.Node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
foreach (Edge e in graph[cur.Node]) {
long nd = cur.Dist + e.Weight;
if (nd < dist[e.To]) {
dist[e.To] = nd;
pq.Push(e.To, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: PriorityQueue<TElement, TPriority>
// does the sifting, MinPQ just gives it a name.
public record Item(int Node, long Dist);
public class MinPQ {
private readonly PriorityQueue<Item, long> heap;
public MinPQ(int node, long dist) {
heap = new PriorityQueue<Item, long>();
heap.Enqueue(new Item(node, dist), dist);
}
// The priority IS the dist, and PriorityQueue always dequeues the smallest
// priority first — that is what makes it a min-heap.
public int Count => heap.Count;
// Enqueue and Dequeue do the sifting for you.
}
}using System.Collections.Generic;
public class Solution {
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
public record Edge(int To, int Weight);
public long[] Dijkstra(IList<IList<Edge>> graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long inf = 1000000000000000000L;
long[] dist = new long[graph.Count];
for (int i = 0; i < dist.Length; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq = new MinPQ(src, 0);
while (pq.Count > 0) {
Item cur = pq.Pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.Dist > dist[cur.Node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
foreach (Edge e in graph[cur.Node]) {
long nd = cur.Dist + e.Weight;
if (nd < dist[e.To]) {
dist[e.To] = nd;
pq.Push(e.To, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: PriorityQueue<TElement, TPriority>
// does the sifting, MinPQ just gives it a name.
public record Item(int Node, long Dist);
public class MinPQ {
private readonly PriorityQueue<Item, long> heap;
public MinPQ(int node, long dist) {
heap = new PriorityQueue<Item, long>();
heap.Enqueue(new Item(node, dist), dist);
}
// The priority IS the dist, and PriorityQueue always dequeues the smallest
// priority first — that is what makes it a min-heap.
public int Count => heap.Count;
// Enqueue and Dequeue do the sifting for you.
public void Push(int node, long dist) {
heap.Enqueue(new Item(node, dist), dist);
}
public Item Pop() {
return heap.Dequeue();
}
}
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ* pq = pqNew(src, 0);
while (pqSize(pq) > 0) {
int node;
long long curDist;
pqPop(pq, &node, &curDist);
}
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ* pq = pqNew(src, 0);
while (pqSize(pq) > 0) {
int node;
long long curDist;
pqPop(pq, &node, &curDist);
// We may have queued this node more than once; ignore stale, longer copies.
}
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ* pq = pqNew(src, 0);
while (pqSize(pq) > 0) {
int node;
long long curDist;
pqPop(pq, &node, &curDist);
// We may have queued this node more than once; ignore stale, longer copies.
if (curDist > dist[node]) {
continue;
}
}
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ* pq = pqNew(src, 0);
while (pqSize(pq) > 0) {
int node;
long long curDist;
pqPop(pq, &node, &curDist);
// We may have queued this node more than once; ignore stale, longer copies.
if (curDist > dist[node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
}
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ* pq = pqNew(src, 0);
while (pqSize(pq) > 0) {
int node;
long long curDist;
pqPop(pq, &node, &curDist);
// We may have queued this node more than once; ignore stale, longer copies.
if (curDist > dist[node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (int i = 0; i < colSizes[node]; i++) {
Edge e = graph[node][i];
long long nd = curDist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pqPush(pq, e.to, nd);
}
}
}
pqFree(pq);
return dist; // O((V + E) log V)
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ* pq = pqNew(src, 0);
while (pqSize(pq) > 0) {
int node;
long long curDist;
pqPop(pq, &node, &curDist);
// We may have queued this node more than once; ignore stale, longer copies.
if (curDist > dist[node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (int i = 0; i < colSizes[node]; i++) {
Edge e = graph[node][i];
long long nd = curDist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pqPush(pq, e.to, nd);
}
}
}
pqFree(pq);
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: C has no heap, so MinPQ is a binary
// MIN-heap on a grown array, ordered by dist.
#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ* pq = pqNew(src, 0);
while (pqSize(pq) > 0) {
int node;
long long curDist;
pqPop(pq, &node, &curDist);
// We may have queued this node more than once; ignore stale, longer copies.
if (curDist > dist[node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (int i = 0; i < colSizes[node]; i++) {
Edge e = graph[node][i];
long long nd = curDist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pqPush(pq, e.to, nd);
}
}
}
pqFree(pq);
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: C has no heap, so MinPQ is a binary
// MIN-heap on a grown array, ordered by dist.
typedef struct {
int node;
long long dist;
} Item;
struct MinPQ {
Item* data;
int size, cap;
};
MinPQ* pqNew(int node, long long dist) {
MinPQ* pq = malloc(sizeof(MinPQ));
pq->cap = 16;
pq->data = malloc(pq->cap * sizeof(Item));
pq->size = 1;
pq->data[0] = (Item){node, dist};
return pq;
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ* pq = pqNew(src, 0);
while (pqSize(pq) > 0) {
int node;
long long curDist;
pqPop(pq, &node, &curDist);
// We may have queued this node more than once; ignore stale, longer copies.
if (curDist > dist[node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (int i = 0; i < colSizes[node]; i++) {
Edge e = graph[node][i];
long long nd = curDist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pqPush(pq, e.to, nd);
}
}
}
pqFree(pq);
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: C has no heap, so MinPQ is a binary
// MIN-heap on a grown array, ordered by dist.
typedef struct {
int node;
long long dist;
} Item;
struct MinPQ {
Item* data;
int size, cap;
};
MinPQ* pqNew(int node, long long dist) {
MinPQ* pq = malloc(sizeof(MinPQ));
pq->cap = 16;
pq->data = malloc(pq->cap * sizeof(Item));
pq->size = 1;
pq->data[0] = (Item){node, dist};
return pq;
}
// pqSize/pqLess/pqSwap define the ordering. Less by dist is what makes it a
// min-heap.
#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ* pq = pqNew(src, 0);
while (pqSize(pq) > 0) {
int node;
long long curDist;
pqPop(pq, &node, &curDist);
// We may have queued this node more than once; ignore stale, longer copies.
if (curDist > dist[node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (int i = 0; i < colSizes[node]; i++) {
Edge e = graph[node][i];
long long nd = curDist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pqPush(pq, e.to, nd);
}
}
}
pqFree(pq);
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: C has no heap, so MinPQ is a binary
// MIN-heap on a grown array, ordered by dist.
typedef struct {
int node;
long long dist;
} Item;
struct MinPQ {
Item* data;
int size, cap;
};
MinPQ* pqNew(int node, long long dist) {
MinPQ* pq = malloc(sizeof(MinPQ));
pq->cap = 16;
pq->data = malloc(pq->cap * sizeof(Item));
pq->size = 1;
pq->data[0] = (Item){node, dist};
return pq;
}
// pqSize/pqLess/pqSwap define the ordering. Less by dist is what makes it a
// min-heap.
int pqSize(MinPQ* pq) {
return pq->size;
}
static int pqLess(MinPQ* pq, int i, int j) {
return pq->data[i].dist < pq->data[j].dist;
}
static void pqSwap(MinPQ* pq, int i, int j) {
Item t = pq->data[i];
pq->data[i] = pq->data[j];
pq->data[j] = t;
}#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ* pq = pqNew(src, 0);
while (pqSize(pq) > 0) {
int node;
long long curDist;
pqPop(pq, &node, &curDist);
// We may have queued this node more than once; ignore stale, longer copies.
if (curDist > dist[node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (int i = 0; i < colSizes[node]; i++) {
Edge e = graph[node][i];
long long nd = curDist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pqPush(pq, e.to, nd);
}
}
}
pqFree(pq);
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: C has no heap, so MinPQ is a binary
// MIN-heap on a grown array, ordered by dist.
typedef struct {
int node;
long long dist;
} Item;
struct MinPQ {
Item* data;
int size, cap;
};
MinPQ* pqNew(int node, long long dist) {
MinPQ* pq = malloc(sizeof(MinPQ));
pq->cap = 16;
pq->data = malloc(pq->cap * sizeof(Item));
pq->size = 1;
pq->data[0] = (Item){node, dist};
return pq;
}
// pqSize/pqLess/pqSwap define the ordering. Less by dist is what makes it a
// min-heap.
int pqSize(MinPQ* pq) {
return pq->size;
}
static int pqLess(MinPQ* pq, int i, int j) {
return pq->data[i].dist < pq->data[j].dist;
}
static void pqSwap(MinPQ* pq, int i, int j) {
Item t = pq->data[i];
pq->data[i] = pq->data[j];
pq->data[j] = t;
}
// pqPush appends to the END then sifts up; pqPop takes the root and sifts down.
#include <stdlib.h>
// graph[node] holds colSizes[node] outgoing edges. Weights must be non-negative.
typedef struct {
int to, weight;
} Edge;
// The priority queue is defined at the bottom; declared up front so dijkstra
// can use it. MinPQ stays opaque here — only these four calls are needed.
typedef struct MinPQ MinPQ;
MinPQ* pqNew(int node, long long dist);
int pqSize(MinPQ* pq);
void pqPush(MinPQ* pq, int node, long long dist);
void pqPop(MinPQ* pq, int* node, long long* dist);
void pqFree(MinPQ* pq);
// Returns a graphSize-long array of distances; the caller owns it.
long long* dijkstra(Edge** graph, int graphSize, int* colSizes, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
long long* dist = malloc(graphSize * sizeof(long long));
for (int i = 0; i < graphSize; i++) {
dist[i] = inf;
}
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ* pq = pqNew(src, 0);
while (pqSize(pq) > 0) {
int node;
long long curDist;
pqPop(pq, &node, &curDist);
// We may have queued this node more than once; ignore stale, longer copies.
if (curDist > dist[node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (int i = 0; i < colSizes[node]; i++) {
Edge e = graph[node][i];
long long nd = curDist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pqPush(pq, e.to, nd);
}
}
}
pqFree(pq);
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: C has no heap, so MinPQ is a binary
// MIN-heap on a grown array, ordered by dist.
typedef struct {
int node;
long long dist;
} Item;
struct MinPQ {
Item* data;
int size, cap;
};
MinPQ* pqNew(int node, long long dist) {
MinPQ* pq = malloc(sizeof(MinPQ));
pq->cap = 16;
pq->data = malloc(pq->cap * sizeof(Item));
pq->size = 1;
pq->data[0] = (Item){node, dist};
return pq;
}
// pqSize/pqLess/pqSwap define the ordering. Less by dist is what makes it a
// min-heap.
int pqSize(MinPQ* pq) {
return pq->size;
}
static int pqLess(MinPQ* pq, int i, int j) {
return pq->data[i].dist < pq->data[j].dist;
}
static void pqSwap(MinPQ* pq, int i, int j) {
Item t = pq->data[i];
pq->data[i] = pq->data[j];
pq->data[j] = t;
}
// pqPush appends to the END then sifts up; pqPop takes the root and sifts down.
void pqPush(MinPQ* pq, int node, long long dist) {
if (pq->size == pq->cap) {
pq->cap *= 2;
pq->data = realloc(pq->data, pq->cap * sizeof(Item));
}
pq->data[pq->size++] = (Item){node, dist};
for (int i = pq->size - 1; i > 0;) {
int parent = (i - 1) / 2;
if (!pqLess(pq, i, parent)) {
break;
}
pqSwap(pq, i, parent);
i = parent;
}
}
void pqPop(MinPQ* pq, int* node, long long* dist) {
*node = pq->data[0].node;
*dist = pq->data[0].dist;
pq->data[0] = pq->data[--pq->size];
for (int i = 0;;) {
int smallest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < pq->size && pqLess(pq, l, smallest)) {
smallest = l;
}
if (r < pq->size && pqLess(pq, r, smallest)) {
smallest = r;
}
if (smallest == i) {
break;
}
pqSwap(pq, i, smallest);
i = smallest;
}
}
void pqFree(MinPQ* pq) {
free(pq->data);
free(pq);
}#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
}
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
}
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
}
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
}
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
}
}
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
}
}
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
}
}
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
}
}
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const Edge& e : graph[cur.node]) {
long long nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const Edge& e : graph[cur.node]) {
long long nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: std::priority_queue does the
// sifting, MinPQ just gives it a name.
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const Edge& e : graph[cur.node]) {
long long nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: std::priority_queue does the
// sifting, MinPQ just gives it a name.
struct Item {
int node;
long long dist;
};
class MinPQ {
priority_queue<Item, vector<Item>, ByDist> heap;
public:
MinPQ(int node, long long dist) {
heap.push({node, dist});
}
};
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const Edge& e : graph[cur.node]) {
long long nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: std::priority_queue does the
// sifting, MinPQ just gives it a name.
struct Item {
int node;
long long dist;
};
// priority_queue is a MAX-heap by default, so the comparator is inverted:
// "a.dist > b.dist" is what makes this a MIN-heap.
class MinPQ {
priority_queue<Item, vector<Item>, ByDist> heap;
public:
MinPQ(int node, long long dist) {
heap.push({node, dist});
}
};
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const Edge& e : graph[cur.node]) {
long long nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: std::priority_queue does the
// sifting, MinPQ just gives it a name.
struct Item {
int node;
long long dist;
};
// priority_queue is a MAX-heap by default, so the comparator is inverted:
// "a.dist > b.dist" is what makes this a MIN-heap.
struct ByDist {
bool operator()(const Item& a, const Item& b) const {
return a.dist > b.dist;
}
};
class MinPQ {
priority_queue<Item, vector<Item>, ByDist> heap;
public:
MinPQ(int node, long long dist) {
heap.push({node, dist});
}
int size() const {
return (int)heap.size();
}
};
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const Edge& e : graph[cur.node]) {
long long nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: std::priority_queue does the
// sifting, MinPQ just gives it a name.
struct Item {
int node;
long long dist;
};
// priority_queue is a MAX-heap by default, so the comparator is inverted:
// "a.dist > b.dist" is what makes this a MIN-heap.
struct ByDist {
bool operator()(const Item& a, const Item& b) const {
return a.dist > b.dist;
}
};
class MinPQ {
priority_queue<Item, vector<Item>, ByDist> heap;
public:
MinPQ(int node, long long dist) {
heap.push({node, dist});
}
int size() const {
return (int)heap.size();
}
// push and pop do the sifting for you; top() is the smallest entry.
};
};#include <queue>
#include <vector>
using namespace std;
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
struct Edge {
int to, weight;
};
class Solution {
public:
vector<long long> dijkstra(vector<vector<Edge>>& graph, int src) {
// Best-known distance to each node; everything starts unreachable.
const long long inf = 1000000000000000000LL;
vector<long long> dist(graph.size(), inf);
dist[src] = 0;
// A min-heap always hands back the closest unfinished node next.
MinPQ pq(src, 0);
while (pq.size() > 0) {
Item cur = pq.pop();
// We may have queued this node more than once; ignore stale, longer copies.
if (cur.dist > dist[cur.node]) {
continue;
}
// Relax each neighbor: if going through cur is shorter, record and queue it.
for (const Edge& e : graph[cur.node]) {
long long nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.push(e.to, nd);
}
}
}
return dist; // O((V + E) log V)
}
// The rest is the priority-queue plumbing: std::priority_queue does the
// sifting, MinPQ just gives it a name.
struct Item {
int node;
long long dist;
};
// priority_queue is a MAX-heap by default, so the comparator is inverted:
// "a.dist > b.dist" is what makes this a MIN-heap.
struct ByDist {
bool operator()(const Item& a, const Item& b) const {
return a.dist > b.dist;
}
};
class MinPQ {
priority_queue<Item, vector<Item>, ByDist> heap;
public:
MinPQ(int node, long long dist) {
heap.push({node, dist});
}
int size() const {
return (int)heap.size();
}
// push and pop do the sifting for you; top() is the smallest entry.
void push(int node, long long dist) {
heap.push({node, dist});
}
Item pop() {
Item top = heap.top();
heap.pop();
return top;
}
};
};Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.