最短路径与图状态

from collections import deque


def open_lock(deadends: list[str], target: str) -> int:
    """Fewest wheel turns from "0000" to target, never resting on a deadend (LC 752)."""
    dead = set(deadends)
    if "0000" in dead:
        return -1
    dist = {"0000": 0}  # every state seen so far, with its distance
    q = deque(["0000"])
    while q:
        s = q.popleft()
        if s == target:
            return dist[s]
        for i in range(4):
            for step in (1, -1):  # turn wheel i up or down
                t = s[:i] + str((int(s[i]) + step) % 10) + s[i + 1 :]
                if t not in dead and t not in dist:
                    dist[t] = dist[s] + 1
                    q.append(t)
    return -1

// Fewest wheel turns from "0000" to target, never resting on a deadend (LC 752).
int openLock(const vector<string>& deadends, const string& target) {
    unordered_set<string> dead(deadends.begin(), deadends.end());
    if (dead.count("0000")) return -1;
    unordered_map<string, int> dist{{"0000", 0}};  // every state seen so far, with its distance
    queue<string> q;
    q.push("0000");
    while (!q.empty()) {
        string s = q.front();
        q.pop();
        if (s == target) return dist[s];
        for (int i = 0; i < 4; i++)
            for (int step : {1, 9}) {  // turn wheel i up, or down (+9 is -1 mod 10)
                string t = s;
                t[i] = '0' + (s[i] - '0' + step) % 10;
                if (!dead.count(t) && !dist.count(t)) {
                    dist[t] = dist[s] + 1;
                    q.push(t);
                }
            }
    }
    return -1;
}

class Solution {
    // Fewest wheel turns from "0000" to target, never resting on a deadend (LC 752).
    int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
        if (dead.contains("0000")) return -1;
        Map<String, Integer> dist = new HashMap<>(Map.of("0000", 0)); // every state seen so far, with its distance
        Deque<String> q = new ArrayDeque<>(List.of("0000"));
        while (!q.isEmpty()) {
            String s = q.poll();
            if (s.equals(target)) return dist.get(s);
            for (int i = 0; i < 4; i++)
                for (int step : new int[] {1, 9}) { // turn wheel i up, or down (+9 is -1 mod 10)
                    char[] t = s.toCharArray();
                    t[i] = (char) ('0' + (t[i] - '0' + step) % 10);
                    String next = new String(t);
                    if (!dead.contains(next) && !dist.containsKey(next)) {
                        dist.put(next, dist.get(s) + 1);
                        q.offer(next);
                    }
                }
        }
        return -1;
    }
}

// openLock returns the fewest wheel turns from "0000" to target, never resting on a deadend (LC 752).
func openLock(deadends []string, target string) int {
	dead := map[string]bool{}
	for _, d := range deadends {
		dead[d] = true
	}
	if dead["0000"] {
		return -1
	}
	dist := map[string]int{"0000": 0} // every state seen so far, with its distance
	q := []string{"0000"}
	for len(q) > 0 {
		s := q[0]
		q = q[1:]
		if s == target {
			return dist[s]
		}
		for i := 0; i < 4; i++ {
			for _, step := range []byte{1, 9} { // turn wheel i up, or down (+9 is -1 mod 10)
				t := []byte(s)
				t[i] = '0' + (t[i]-'0'+step)%10
				next := string(t)
				if _, seen := dist[next]; !seen && !dead[next] {
					dist[next] = dist[s] + 1
					q = append(q, next)
				}
			}
		}
	}
	return -1
}

def cheapest_within(n: int, flights: list[tuple[int, int, int]], src: int, dst: int, k: int) -> int:
    """Cheapest price from src to dst with at most k stops, i.e. k + 1 flights (LC 787)."""
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):  # after round i: best prices using at most i flights
        prev = dist[:]  # relax from last round only, so each round adds at most one flight
        for u, v, w in flights:
            if prev[u] + w < dist[v]:
                dist[v] = prev[u] + w
    return -1 if dist[dst] == INF else dist[dst]

// Cheapest price from src to dst with at most k stops, i.e. k + 1 flights (LC 787).
long long cheapestWithin(int n, const vector<array<int, 3>>& flights, int src, int dst, int k) {
    const long long INF = LLONG_MAX / 4;
    vector<long long> dist(n, INF);
    dist[src] = 0;
    for (int round = 0; round <= k; round++) {  // after round i: best prices using at most i flights
        vector<long long> prev = dist;  // relax from last round only, so each round adds at most one flight
        for (auto [u, v, w] : flights)
            if (prev[u] + w < dist[v]) dist[v] = prev[u] + w;
    }
    return dist[dst] == INF ? -1 : dist[dst];
}

class Solution {
    // Cheapest price from src to dst with at most k stops, i.e. k + 1 flights (LC 787).
    long cheapestWithin(int n, int[][] flights, int src, int dst, int k) {
        final long INF = Long.MAX_VALUE / 4;
        long[] dist = new long[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int round = 0; round <= k; round++) { // after round i: best prices using at most i flights
            long[] prev = dist.clone(); // relax from last round only, so each round adds at most one flight
            for (int[] f : flights)
                if (prev[f[0]] + f[2] < dist[f[1]]) dist[f[1]] = prev[f[0]] + f[2];
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
}

// cheapestWithin returns the cheapest price from src to dst with at most k stops (LC 787).
func cheapestWithin(n int, flights [][3]int, src, dst, k int) int {
	const inf = 1 << 60
	dist := make([]int, n)
	for i := range dist {
		dist[i] = inf
	}
	dist[src] = 0
	for round := 0; round <= k; round++ { // after round i: best prices using at most i flights
		prev := append([]int(nil), dist...) // relax from last round only, so each round adds at most one flight
		for _, f := range flights {
			if prev[f[0]]+f[2] < dist[f[1]] {
				dist[f[1]] = prev[f[0]] + f[2]
			}
		}
	}
	if dist[dst] == inf {
		return -1
	}
	return dist[dst]
}

from collections import deque


def shortest_path_all_nodes(graph: list[list[int]]) -> int:
    """Length of the shortest walk that visits every node; edges may repeat (LC 847)."""
    n = len(graph)
    full = (1 << n) - 1
    seen = [[False] * (1 << n) for _ in range(n)]  # state (node, mask of visited nodes)
    q = deque()
    for i in range(n):  # every node is a start, at distance 0
        seen[i][1 << i] = True
        q.append((i, 1 << i))
    steps = 0
    while q:
        for _ in range(len(q)):
            u, mask = q.popleft()
            if mask == full:
                return steps
            for v in graph[u]:
                nxt = mask | 1 << v
                if not seen[v][nxt]:
                    seen[v][nxt] = True
                    q.append((v, nxt))
        steps += 1
    return -1

// Length of the shortest walk that visits every node; edges may repeat (LC 847).
int shortestPathAllNodes(const vector<vector<int>>& graph) {
    int n = graph.size(), full = (1 << n) - 1;
    vector<vector<bool>> seen(n, vector<bool>(1 << n, false));  // state (node, mask of visited nodes)
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++) {  // every node is a start, at distance 0
        seen[i][1 << i] = true;
        q.push({i, 1 << i});
    }
    for (int steps = 0; !q.empty(); steps++)
        for (int k = q.size(); k > 0; k--) {
            auto [u, mask] = q.front();
            q.pop();
            if (mask == full) return steps;
            for (int v : graph[u]) {
                int next = mask | 1 << v;
                if (!seen[v][next]) {
                    seen[v][next] = true;
                    q.push({v, next});
                }
            }
        }
    return -1;
}

class Solution {
    // Length of the shortest walk that visits every node; edges may repeat (LC 847).
    int shortestPathAllNodes(int[][] graph) {
        int n = graph.length, full = (1 << n) - 1;
        boolean[][] seen = new boolean[n][1 << n]; // state (node, mask of visited nodes)
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) { // every node is a start, at distance 0
            seen[i][1 << i] = true;
            q.offer(new int[] {i, 1 << i});
        }
        for (int steps = 0; !q.isEmpty(); steps++)
            for (int k = q.size(); k > 0; k--) {
                int[] state = q.poll();
                if (state[1] == full) return steps;
                for (int v : graph[state[0]]) {
                    int next = state[1] | 1 << v;
                    if (!seen[v][next]) {
                        seen[v][next] = true;
                        q.offer(new int[] {v, next});
                    }
                }
            }
        return -1;
    }
}

// shortestPathAllNodes returns the length of the shortest walk that visits every node (LC 847).
func shortestPathAllNodes(graph [][]int) int {
	n := len(graph)
	full := 1<<n - 1
	seen := make([][]bool, n) // state (node, mask of visited nodes)
	var q [][2]int
	for i := range seen { // every node is a start, at distance 0
		seen[i] = make([]bool, 1<<n)
		seen[i][1<<i] = true
		q = append(q, [2]int{i, 1 << i})
	}
	for steps := 0; len(q) > 0; steps++ {
		var next [][2]int // the following BFS level
		for _, s := range q {
			if s[1] == full {
				return steps
			}
			for _, v := range graph[s[0]] {
				if mask := s[1] | 1<<v; !seen[v][mask] {
					seen[v][mask] = true
					next = append(next, [2]int{v, mask})
				}
			}
		}
		q = next
	}
	return -1
}