import Mathlib /-! # Network Delay Time You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1. ## Constraints - 1 <= k <= n <= 100 - 1 <= times.length <= 6000 - times[i].length == 3 - 1 <= u_i, v_i <= n - u_i != v_i - 0 <= w_i <= 100 - All the pairs (u_i, v_i) are unique. (i.e., no multiple edges.) ## Provided examples - `times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2` → `2` - `times = [[1, 2, 1]], n = 2, k = 1` → `1` - `times = [[1, 2, 1]], n = 2, k = 2` → `-1` ## Synthesized negative examples - invalid input: `times = [[1, 2, 0]], n = 2, k = 0` ([structural] a predicate that admits 1 <= k <= n <= 100. k is one below the allowed minimum) - invalid input: `times = [], n = 2, k = 1` ([structural] a predicate that admits 1 <= times.length <= 6000. empty edge list below the required length) - invalid input: `times = [[1, 2]], n = 2, k = 1` ([structural] a predicate that admits times[i].length == 3. accepts a two-element row as a triple) - `times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2` → `3` is wrong ([structural] minimality omitted; achievability only. all nodes have received by 3, but 2 is sooner) - `times = [[1, 2, 1]], n = 2, k = 1` → `0` is wrong ([structural] answer can be any value below the true propagation time. node 2 cannot receive by time 0) - `times = [[1, 2, 1]], n = 2, k = 2` → `0` is wrong ([structural] nothing requires every node to receive; only the starting node is reached. only k must receive, so 0 survives) -/ namespace PNetworkDelayTime abbrev Input := (Nat) × (List (List Nat)) × (Nat) abbrev Output := Int /-! ### Specification helpers -/ /-- A serialized edge is the triple `[u, v, w]` with distinct endpoints in `1..n` and weight at most 100. -/ def isValidEdge (n : Nat) (e : List Nat) : Bool := e.length == 3 && (match e with | [u, v, w] => 1 ≤ u && u ≤ n && 1 ≤ v && v ≤ n && u != v && w ≤ 100 | _ => true) /-- There is a directed path from `u` to `v` along triples stored in `times` whose total weight is at most `t`. -/ def HasPathWithin (times : List (List Nat)) (u v : Nat) (t : Int) : Prop := ∃ edges : List (Nat × Nat × Nat), (∀ e ∈ edges, [e.1, e.2.1, e.2.2] ∈ times) ∧ edges.Chain' (fun a b => a.2.1 = b.1) ∧ (match edges with | [] => u = v | e :: _ => e.1 = u) ∧ (match edges.getLast? with | none => u = v | some e => e.2.1 = v) ∧ (edges.map fun e => (e.2.2 : Int)).sum ≤ t /-- Every node `v` with `1 ≤ v ≤ n` is reachable from `k` within total time `t`. -/ def AllReachedWithin (times : List (List Nat)) (n k : Nat) (t : Int) : Prop := ∀ v : Nat, 1 ≤ v → v ≤ n → HasPathWithin times k v t /-! ### Validity predicate (V) -/ /-- Valid input: `1 ≤ n ≤ 100`, `1 ≤ k ≤ n`, between 1 and 6000 valid edges, and no repeated `(u, v)` pair. -/ def isValidInput (input : Input) : Bool := match input with | (n, times, k) => 1 ≤ n && n ≤ 100 && 1 ≤ k && k ≤ n && 1 ≤ times.length && times.length ≤ 6000 && times.all (isValidEdge n) && (times.map (·.take 2)).Nodup /-! ### Ideal specification (P_spec) -/ /-- `result` is the least nonnegative time by which every node has received the signal from `k`, or `-1` when no such time exists. -/ def networkDelayTime_spec (input : Input) (result : Output) : Prop := match input with | (n, times, k) => ((∃ t : Int, 0 ≤ t ∧ AllReachedWithin times n k t) → IsLeast {t : Int | 0 ≤ t ∧ AllReachedWithin times n k t} result) ∧ ((¬∃ t : Int, 0 ≤ t ∧ AllReachedWithin times n k t) → result = -1) /-! ### Decidable specification (P_check) -/ /-- All sequences of length at most `m` with entries drawn from `edges`. -/ def edgeSeqs : Nat → List (Nat × Nat × Nat) → List (List (Nat × Nat × Nat)) | 0, _ => [[]] | m + 1, edges => [] :: (edgeSeqs m edges).flatMap fun rest => edges.map (· :: rest) /-- Adjacent-edge agreement of a candidate path, mirroring `List.Chain'`. -/ def chainOk : List (Nat × Nat × Nat) → Bool | [] => true | [_] => true | a :: b :: rest => a.2.1 == b.1 && chainOk (b :: rest) /-- The conditions inside `HasPathWithin` checked on one candidate edge list. -/ def pathFits (times : List (List Nat)) (u v : Nat) (t : Int) (edges : List (Nat × Nat × Nat)) : Bool := edges.all (fun e => decide ([e.1, e.2.1, e.2.2] ∈ times)) && chainOk edges && (match edges with | [] => decide (u = v) | e :: _ => decide (e.1 = u)) && (match edges.getLast? with | none => decide (u = v) | some e => decide (e.2.1 = v)) && decide ((edges.map fun e => (e.2.2 : Int)).sum ≤ t) /-- Finite realization of `HasPathWithin`: some path of at most `n - 1` edges from `times` fits. -/ def hasPathWithinBool (times : List (List Nat)) (n u v : Nat) (t : Int) : Bool := let triples := times.filterMap fun e => match e with | [a, b, c] => some (a, b, c) | _ => none (edgeSeqs (n - 1) triples).any (pathFits times u v t) /-- Finite realization of `AllReachedWithin` over the nodes `1 ≤ v ≤ n`. -/ def allReachedWithinBool (times : List (List Nat)) (n k : Nat) (t : Int) : Bool := (List.range n).all fun i => hasPathWithinBool times n k (i + 1) t /-- `f - n` applies `f : Output → Bool` to the negative integer `-(n : Output)`, so an unparenthesized negative output in a test row still means checking the answer `-n`. -/ instance subNegOutput : HSub (Output → Bool) Nat Bool where hSub f n := f (-(n : Output)) /-- Executable checker for `networkDelayTime_spec`. -/ def networkDelayTime_check (input : Input) (result : Output) : Bool := match input with | (n, times, k) => let anyTime := allReachedWithinBool times n k ((100 * (n - 1) : Nat) : Int) (!anyTime || (decide (0 ≤ result) && allReachedWithinBool times n k result && (List.range result.toNat).all fun t => !allReachedWithinBool times n k (t : Int))) && (anyTime || result == -1) /-- A walk from `u` to `v` along stored triples, one edge at a time. -/ def WalkE (times : List (List Nat)) : Nat → List (Nat × Nat × Nat) → Nat → Prop | u, [], v => u = v | u, e :: rest, v => [e.1, e.2.1, e.2.2] ∈ times ∧ e.1 = u ∧ WalkE times e.2.1 rest v /-- Total weight of an edge list, in `Nat`. -/ def wsum (l : List (Nat × Nat × Nat)) : Nat := (l.map fun e => e.2.2).sum theorem walkE_cons (times : List (List Nat)) (u : Nat) (e : Nat × Nat × Nat) (rest : List (Nat × Nat × Nat)) (v : Nat) : WalkE times u (e :: rest) v ↔ ([e.1, e.2.1, e.2.2] ∈ times ∧ e.1 = u ∧ WalkE times e.2.1 rest v) := Iff.rfl theorem sum_cast (l : List (Nat × Nat × Nat)) : (l.map fun e => (e.2.2 : Int)).sum = ((wsum l : Nat) : Int) := by induction l with | nil => simp [wsum] | cons a l ih => simp only [List.map_cons, List.sum_cons, wsum] at ih ⊢ rw [ih] omega theorem chainOk_iff (l : List (Nat × Nat × Nat)) : chainOk l = true ↔ List.IsChain (fun a b : Nat × Nat × Nat => a.2.1 = b.1) l := by induction l using List.twoStepInduction with | nil => simp [chainOk] | singleton a => simp [chainOk] | cons_cons a b l ih1 ih2 => simp [chainOk, List.isChain_cons_cons, ih2] theorem pathFits_iff (times : List (List Nat)) (u v : Nat) (t : Int) (edges : List (Nat × Nat × Nat)) : pathFits times u v t edges = true ↔ ((∀ e ∈ edges, [e.1, e.2.1, e.2.2] ∈ times) ∧ List.IsChain (fun a b : Nat × Nat × Nat => a.2.1 = b.1) edges ∧ (match edges with | [] => u = v | e :: _ => e.1 = u) ∧ (match edges.getLast? with | none => u = v | some e => e.2.1 = v) ∧ (edges.map fun e => (e.2.2 : Int)).sum ≤ t) := by unfold pathFits simp only [Bool.and_eq_true, List.all_eq_true, decide_eq_true_eq, chainOk_iff] cases edges with | nil => simp [and_assoc] | cons e rest => cases h : (e :: rest).getLast? <;> simp [and_assoc] theorem body_iff_walk (times : List (List Nat)) : ∀ (edges : List (Nat × Nat × Nat)) (u v : Nat), ((∀ e ∈ edges, [e.1, e.2.1, e.2.2] ∈ times) ∧ List.IsChain (fun a b : Nat × Nat × Nat => a.2.1 = b.1) edges ∧ (match edges with | [] => u = v | e :: _ => e.1 = u) ∧ (match edges.getLast? with | none => u = v | some e => e.2.1 = v)) ↔ WalkE times u edges v := by intro edges induction edges with | nil => intro u v; simp [WalkE] | cons e rest ih => intro u v cases rest with | nil => simp [WalkE] | cons e' r => rw [walkE_cons, ← ih] simp only [List.forall_mem_cons, List.isChain_cons_cons, List.getLast?_cons_cons] constructor · rintro ⟨⟨he, hall⟩, ⟨hc, hch⟩, hu, hl⟩ exact ⟨he, hu, hall, hch, hc.symm, hl⟩ · rintro ⟨he, hu, hall, hch, hc, hl⟩ exact ⟨⟨he, hall⟩, ⟨hc.symm, hch⟩, hu, hl⟩ theorem hasPath_iff (times : List (List Nat)) (u v : Nat) (t : Int) : HasPathWithin times u v t ↔ ∃ edges, WalkE times u edges v ∧ (edges.map fun e => (e.2.2 : Int)).sum ≤ t := by unfold HasPathWithin constructor · rintro ⟨edges, h1, h2, h3, h4, h5⟩ exact ⟨edges, (body_iff_walk times edges u v).1 ⟨h1, h2, h3, h4⟩, h5⟩ · rintro ⟨edges, hw, hs⟩ obtain ⟨h1, h2, h3, h4⟩ := (body_iff_walk times edges u v).2 hw exact ⟨edges, h1, h2, h3, h4, hs⟩ theorem walk_suffix (times : List (List Nat)) (f : Nat × Nat × Nat) (B : List (Nat × Nat × Nat)) (v : Nat) : ∀ (A : List (Nat × Nat × Nat)) (x : Nat), WalkE times x (A ++ f :: B) v → WalkE times f.2.1 B v := by intro A induction A with | nil => intro x h; exact ((walkE_cons times x f B v).1 h).2.2 | cons a A' ih => intro x h; exact ih a.2.1 ((walkE_cons times x a (A' ++ f :: B) v).1 h).2.2 theorem walk_mem (times : List (List Nat)) (v : Nat) : ∀ (edges : List (Nat × Nat × Nat)) (u : Nat), WalkE times u edges v → ∀ e ∈ edges, [e.1, e.2.1, e.2.2] ∈ times := by intro edges induction edges with | nil => intro u _ e he; simp at he | cons a l ih => intro u h e he have h' := (walkE_cons times u a l v).1 h rcases List.mem_cons.mp he with rfl | he · exact h'.1 · exact ih _ h'.2.2 e he theorem walk_erase (times : List (List Nat)) : ∀ (m : Nat) (edges : List (Nat × Nat × Nat)) (u v : Nat), edges.length ≤ m → WalkE times u edges v → ∃ edges', WalkE times u edges' v ∧ wsum edges' ≤ wsum edges ∧ (u :: edges'.map (fun e => e.2.1)).Nodup ∧ (∀ e ∈ edges', e ∈ edges) := by intro m induction m with | zero => intro edges u v hlen hw rw [Nat.le_zero, List.length_eq_zero_iff] at hlen subst hlen exact ⟨[], hw, le_rfl, by simp, by simp⟩ | succ m ih => intro edges u v hlen hw cases edges with | nil => exact ⟨[], hw, le_rfl, by simp, by simp⟩ | cons e rest => obtain ⟨he, heu, hwr⟩ := (walkE_cons times u e rest v).1 hw have hlen' : rest.length ≤ m := by simp only [List.length_cons] at hlen omega obtain ⟨r', hw', hs', hnd', hsub'⟩ := ih rest e.2.1 v hlen' hwr have hsum : wsum (e :: rest) = e.2.2 + wsum rest := by simp only [wsum, List.map_cons, List.sum_cons] by_cases hu : u ∈ e.2.1 :: r'.map (fun e => e.2.1) · rcases List.mem_cons.mp hu with hue | hum · refine ⟨r', ?_, by omega, ?_, fun x hx => List.mem_cons_of_mem _ (hsub' x hx)⟩ · rw [hue] exact hw' · rw [hue] exact hnd' · obtain ⟨f, hf, hfu⟩ := List.mem_map.mp hum obtain ⟨A, B, rfl⟩ := List.append_of_mem hf have hB : WalkE times u B v := by have hs := walk_suffix times f B v A e.2.1 hw' rw [hfu] at hs exact hs have hsAB : wsum B ≤ wsum (A ++ f :: B) := by simp only [wsum, List.map_append, List.map_cons, List.sum_append, List.sum_cons] omega refine ⟨B, hB, by omega, ?_, fun x hx => List.mem_cons_of_mem _ (hsub' x (List.mem_append_right _ (List.mem_cons_of_mem _ hx)))⟩ have hsl : (u :: B.map (fun e => e.2.1)).Sublist (e.2.1 :: (A ++ f :: B).map (fun e => e.2.1)) := by rw [List.map_append, List.map_cons, hfu] exact List.Sublist.cons _ (List.sublist_append_right _ _) exact List.Nodup.sublist hsl hnd' · refine ⟨e :: r', (walkE_cons times u e r' v).2 ⟨he, heu, hw'⟩, ?_, List.nodup_cons.2 ⟨hu, hnd'⟩, ?_⟩ · simp only [wsum, List.map_cons, List.sum_cons] at hs' hsum ⊢ omega · intro x hx rcases List.mem_cons.mp hx with rfl | hx · exact List.mem_cons_self · exact List.mem_cons_of_mem _ (hsub' x hx) theorem edge_bounds (n : Nat) (e : Nat × Nat × Nat) (h : isValidEdge n [e.1, e.2.1, e.2.2] = true) : 1 ≤ e.2.1 ∧ e.2.1 ≤ n ∧ e.2.2 ≤ 100 := by simp [isValidEdge] at h omega theorem nodup_len (n u : Nat) (edges : List (Nat × Nat × Nat)) (hu : 1 ≤ u ∧ u ≤ n) (hnd : (u :: edges.map (fun e => e.2.1)).Nodup) (hb : ∀ e ∈ edges, 1 ≤ e.2.1 ∧ e.2.1 ≤ n) : edges.length ≤ n - 1 := by have hsub : ∀ x ∈ u :: edges.map (fun e => e.2.1), x ∈ List.range' 1 n := by intro x hx rw [List.mem_range'_1] rcases List.mem_cons.mp hx with rfl | hx · omega · obtain ⟨e, he, rfl⟩ := List.mem_map.mp hx have := hb e he omega have hle := (List.subperm_of_subset hnd hsub).length_le simp only [List.length_cons, List.length_map, List.length_range'] at hle omega theorem wsum_le (l : List (Nat × Nat × Nat)) (h : ∀ e ∈ l, e.2.2 ≤ 100) : wsum l ≤ 100 * l.length := by induction l with | nil => simp [wsum] | cons a l ih => have ha := h a List.mem_cons_self have hr := ih (fun e he => h e (List.mem_cons_of_mem _ he)) simp only [wsum, List.map_cons, List.sum_cons, List.length_cons] at hr ⊢ omega theorem short_path (n : Nat) (times : List (List Nat)) (hvalid : ∀ e ∈ times, isValidEdge n e = true) (u v : Nat) (hu : 1 ≤ u ∧ u ≤ n) (t : Int) (hp : HasPathWithin times u v t) : ∃ edges', WalkE times u edges' v ∧ ((wsum edges' : Nat) : Int) ≤ t ∧ edges'.length ≤ n - 1 ∧ wsum edges' ≤ 100 * (n - 1) := by obtain ⟨edges, hw, hs⟩ := (hasPath_iff times u v t).1 hp obtain ⟨e', hw', hs', hnd, _⟩ := walk_erase times edges.length edges u v le_rfl hw have hmem := walk_mem times v e' u hw' have hbounds : ∀ e ∈ e', 1 ≤ e.2.1 ∧ e.2.1 ≤ n ∧ e.2.2 ≤ 100 := fun e he => edge_bounds n e (hvalid _ (hmem e he)) have hlen : e'.length ≤ n - 1 := nodup_len n u e' hu hnd (fun e he => ⟨(hbounds e he).1, (hbounds e he).2.1⟩) have hw100 := wsum_le e' (fun e he => (hbounds e he).2.2) rw [sum_cast] at hs refine ⟨e', hw', by omega, hlen, ?_⟩ have hmul : 100 * e'.length ≤ 100 * (n - 1) := Nat.mul_le_mul_left 100 hlen omega theorem mem_edgeSeqs_of (es : List (Nat × Nat × Nat)) : ∀ (m : Nat) (l : List (Nat × Nat × Nat)), l.length ≤ m → (∀ e ∈ l, e ∈ es) → l ∈ edgeSeqs m es := by intro m induction m with | zero => intro l hl _ rw [Nat.le_zero, List.length_eq_zero_iff] at hl subst hl simp [edgeSeqs] | succ m ih => intro l hl hes cases l with | nil => simp [edgeSeqs] | cons a l' => show a :: l' ∈ [] :: (edgeSeqs m es).flatMap (fun rest => es.map (· :: rest)) apply List.mem_cons_of_mem rw [List.mem_flatMap] have hl' : l'.length ≤ m := by simp only [List.length_cons] at hl omega refine ⟨l', ih l' hl' (fun e he => hes e (List.mem_cons_of_mem _ he)), ?_⟩ exact List.mem_map.2 ⟨a, hes a List.mem_cons_self, rfl⟩ theorem hasPathBool_iff (n : Nat) (times : List (List Nat)) (hvalid : ∀ e ∈ times, isValidEdge n e = true) (u v : Nat) (hu : 1 ≤ u ∧ u ≤ n) (t : Int) : hasPathWithinBool times n u v t = true ↔ HasPathWithin times u v t := by show (edgeSeqs (n - 1) _).any (pathFits times u v t) = true ↔ HasPathWithin times u v t rw [List.any_eq_true] constructor · rintro ⟨edges, _, hf⟩ exact ⟨edges, (pathFits_iff times u v t edges).1 hf⟩ · intro hp obtain ⟨e', hw', hs', hlen, _⟩ := short_path n times hvalid u v hu t hp refine ⟨e', mem_edgeSeqs_of _ (n - 1) e' hlen (fun e he => List.mem_filterMap.2 ⟨[e.1, e.2.1, e.2.2], walk_mem times v e' u hw' e he, rfl⟩), (pathFits_iff times u v t e').2 ?_⟩ obtain ⟨h1, h2, h3, h4⟩ := (body_iff_walk times e' u v).2 hw' exact ⟨h1, h2, h3, h4, by rw [sum_cast]; exact hs'⟩ theorem allReached_iff (n : Nat) (times : List (List Nat)) (hvalid : ∀ e ∈ times, isValidEdge n e = true) (k : Nat) (hk : 1 ≤ k ∧ k ≤ n) (t : Int) : allReachedWithinBool times n k t = true ↔ AllReachedWithin times n k t := by unfold allReachedWithinBool AllReachedWithin rw [List.all_eq_true] constructor · intro h v hv1 hv2 have h' : hasPathWithinBool times n k (v - 1 + 1) t = true := h (v - 1) (List.mem_range.2 (by omega)) rw [show v - 1 + 1 = v from by omega] at h' exact (hasPathBool_iff n times hvalid k v hk t).1 h' · intro h i hi rw [List.mem_range] at hi exact (hasPathBool_iff n times hvalid k (i + 1) hk t).2 (h (i + 1) (by omega) (by omega)) theorem anyTime_iff (n : Nat) (times : List (List Nat)) (hvalid : ∀ e ∈ times, isValidEdge n e = true) (k : Nat) (hk : 1 ≤ k ∧ k ≤ n) : allReachedWithinBool times n k ((100 * (n - 1) : Nat) : Int) = true ↔ ∃ t : Int, 0 ≤ t ∧ AllReachedWithin times n k t := by rw [allReached_iff n times hvalid k hk] constructor · intro hr exact ⟨_, by omega, hr⟩ · rintro ⟨t, _, ht⟩ v hv1 hv2 obtain ⟨e', hw', _, _, h100⟩ := short_path n times hvalid k v hk t (ht v hv1 hv2) refine (hasPath_iff times k v _).2 ⟨e', hw', ?_⟩ rw [sum_cast] omega theorem glue_delay (a : Bool) (B : Int → Bool) (R : Int → Prop) (result : Int) (ha : a = true ↔ ∃ t, 0 ≤ t ∧ R t) (hB : ∀ t, B t = true ↔ R t) : ((!a || (decide (0 ≤ result) && B result && (List.range result.toNat).all fun t => !B (t : Int))) && (a || result == -1)) = true ↔ (((∃ t : Int, 0 ≤ t ∧ R t) → IsLeast {t : Int | 0 ≤ t ∧ R t} result) ∧ ((¬∃ t : Int, 0 ≤ t ∧ R t) → result = -1)) := by cases a with | false => have hn : ¬ ∃ t : Int, 0 ≤ t ∧ R t := fun hex => by simpa using ha.2 hex simp only [Bool.not_false, Bool.true_or, Bool.true_and, Bool.false_or, beq_iff_eq] constructor · intro hr exact ⟨fun hex => absurd hex hn, fun _ => hr⟩ · rintro ⟨_, h2⟩ exact h2 hn | true => have hex : ∃ t : Int, 0 ≤ t ∧ R t := ha.1 rfl simp only [Bool.not_true, Bool.false_or, Bool.true_or, Bool.and_true, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, List.mem_range, Bool.not_eq_true'] constructor · rintro ⟨⟨h0, hb⟩, hmin⟩ refine ⟨fun _ => ⟨⟨h0, (hB _).1 hb⟩, ?_⟩, fun hn => absurd hex hn⟩ rintro t ⟨ht0, ht⟩ by_contra hlt have hlt' : t < result := not_le.mp hlt have hm := hmin t.toNat (by omega) have htn : ((t.toNat : Nat) : Int) = t := by omega rw [htn, (hB t).2 ht] at hm simp at hm · rintro ⟨hl, _⟩ obtain ⟨⟨h0, hr⟩, hlb⟩ := hl hex refine ⟨⟨h0, (hB _).2 hr⟩, fun x hx => ?_⟩ cases hbx : B (x : Int) with | false => rfl | true => exfalso have hx' : (x : Int) ∈ {t : Int | 0 ≤ t ∧ R t} := ⟨by omega, (hB _).1 hbx⟩ have hle := hlb hx' omega /-- On valid input the checker accepts exactly the specified outputs. -/ theorem networkDelayTime_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : networkDelayTime_check input result ↔ networkDelayTime_spec input result := by obtain ⟨n, times, k⟩ := input simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true] at h obtain ⟨⟨⟨⟨⟨⟨⟨_, _⟩, hk1⟩, hk2⟩, _⟩, _⟩, hedges⟩, _⟩ := h exact glue_delay (allReachedWithinBool times n k ((100 * (n - 1) : Nat) : Int)) (allReachedWithinBool times n k) (AllReachedWithin times n k) result (anyTime_iff n times hedges k ⟨hk1, hk2⟩) (fun t => allReached_iff n times hedges k ⟨hk1, hk2⟩ t) /-! ### Implementation helpers -/ /-- The serialized `times` entries parsed as `(source, target, weight)` triples. -/ def edgeList (times : List (List Nat)) : List (Nat × Nat × Nat) := times.filterMap fun e => match e with | [u, v, w] => some (u, v, w) | _ => none /-- Outgoing `(target, weight)` pairs grouped by source node, indexed `0..n`. -/ def adjacency (n : Nat) (edges : List (Nat × Nat × Nat)) : Array (List (Nat × Nat)) := edges.foldl (fun adj e => adj.set! e.1 ((e.2.1, e.2.2) :: adj[e.1]!)) (Array.replicate (n + 1) []) /-- The unvisited node with the smallest known distance, if any unvisited node is reachable. -/ def pickMin (dist : Array (Option Nat)) (visited : Array Bool) (n : Nat) : Option Nat := (List.range n).foldl (fun best i => let v := i + 1 if visited[v]! then best else match dist[v]!, best with | none, _ => best | some _, none => some v | some dv, some b => match dist[b]! with | some db => if dv < db then some v else best | none => some v) none /-- Dijkstra over nodes `1..n`: shortest distances from `k`, with `none` for unreachable nodes. -/ def dijkstraDistances (n : Nat) (edges : List (Nat × Nat × Nat)) (k : Nat) : Array (Option Nat) := let adj := adjacency n edges let start : Array (Option Nat) × Array Bool := ((Array.replicate (n + 1) none).set! k (some 0), Array.replicate (n + 1) false) ((List.range n).foldl (fun (dist, visited) _ => match pickMin dist visited n with | none => (dist, visited) | some u => let du := (dist[u]!).getD 0 let dist' := (adj[u]!).foldl (fun d (v, w) => let cand := du + w match d[v]! with | none => d.set! v (some cand) | some old => if cand < old then d.set! v (some cand) else d) dist (dist', visited.set! u true)) start).1 /-! ### Main algorithm (impl) -/ /-- Dijkstra's algorithm from `k`: the maximum shortest distance, or `-1` if a node is unreachable. -/ def minNetworkDelayTime (input : Input) : Output := match input with | (n, times, k) => let dist := dijkstraDistances n (edgeList times) k if (List.range n).any (fun i => (dist[i + 1]!).isNone) then -1 else ((List.range n).foldl (fun acc i => max acc ((dist[i + 1]!).getD 0 : Int)) (0 : Int)) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem minNetworkDelayTime_correct (input : Input) (h : isValidInput input) : networkDelayTime_spec input (minNetworkDelayTime input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (4, [[2, 1, 1], [2, 3, 1], [3, 4, 1]], 2) #guard isValidInput (2, [[1, 2, 1]], 1) #guard isValidInput (2, [[1, 2, 1]], 2) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (2, [[1, 2, 0]], 0)) #guard !(isValidInput (2, [], 1)) #guard !(isValidInput (2, [[1, 2]], 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard networkDelayTime_check (4, [[2, 1, 1], [2, 3, 1], [3, 4, 1]], 2) 2 #guard networkDelayTime_check (2, [[1, 2, 1]], 1) 1 #guard networkDelayTime_check (2, [[1, 2, 1]], 2) -1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(networkDelayTime_check (4, [[2, 1, 1], [2, 3, 1], [3, 4, 1]], 2) 3) #guard !(networkDelayTime_check (2, [[1, 2, 1]], 1) 0) #guard !(networkDelayTime_check (2, [[1, 2, 1]], 2) 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard minNetworkDelayTime (4, [[2, 1, 1], [2, 3, 1], [3, 4, 1]], 2) == 2 #guard minNetworkDelayTime (2, [[1, 2, 1]], 1) == 1 #guard minNetworkDelayTime (2, [[1, 2, 1]], 2) == (-1) /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard networkDelayTime_check (4, [[2, 1, 1], [2, 3, 1], [3, 4, 1]], 2) (minNetworkDelayTime (4, [[2, 1, 1], [2, 3, 1], [3, 4, 1]], 2)) #guard networkDelayTime_check (2, [[1, 2, 1]], 1) (minNetworkDelayTime (2, [[1, 2, 1]], 1)) #guard networkDelayTime_check (2, [[1, 2, 1]], 2) (minNetworkDelayTime (2, [[1, 2, 1]], 2)) end PNetworkDelayTime