Shortest Path

import heapq
def dijkstra(n, adj, src):
    dist=[float('inf')]*n; dist[src]=0
    pq=[(0,src)]
    while pq:
        d,u=heapq.heappop(pq)
        if d!=dist[u]: continue
        for v,w in adj[u]:
            nd=d+w
            if nd<dist[v]: dist[v]=nd; heapq.heappush(pq,(nd,v))
    return dist

from collections import deque
def zero_one_bfs(n, adj, src):
    dist=[10**18]*n; dist[src]=0
    dq=deque([src])
    while dq:
        u=dq.popleft()
        for v,w in adj[u]:
            nd=dist[u]+w
            if nd<dist[v]:
                dist[v]=nd
                (dq.appendleft if w==0 else dq.append)(v)
    return dist

def bellman_ford(n, edges, src):
    INF=10**18; dist=[INF]*n; dist[src]=0
    for _ in range(n-1):
        changed=False
        for u,v,w in edges:
            if dist[u]+w<dist[v]: dist[v]=dist[u]+w; changed=True
        if not changed: break
    # Optional: detect negative cycle
    for u,v,w in edges:
        if dist[u]+w<dist[v]: return None  # negative cycle
    return dist

from collections import deque
def multi_source_bfs(grid, sources):
    R,C=len(grid),len(grid[0]); dist=[[ -1]*C for _ in range(R)]
    q=deque()
    for r,c in sources: dist[r][c]=0; q.append((r,c))
    while q:
        r,c=q.popleft()
        for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr,nc=r+dr,c+dc
            if 0<=nr<R and 0<=nc<C and dist[nr][nc]==-1:
                dist[nr][nc]=dist[r][c]+1
                q.append((nr,nc))
    return dist