An archipelago has n islands 0 .. n-1. Ferry lines are directed: lines[i] = [a, b, fare] sails
from a to b for fare (fare >= 0). You want to travel from src to dst making at most k
intermediate stops (that is, using at most k + 1 ferries). Return the cheapest total fare, or -1 if
no such itinerary exists. If src == dst the answer is 0.
Examples
Input: n = 4, lines = [[0,1,100],[1,2,100],[2,3,100],[0,2,500],[0,3,1000]], src = 0, dst = 3, k = 1
Output: 600
Explanation: 0 -> 2 -> 3 makes one stop and costs 600; 0 -> 1 -> 2 -> 3 is cheaper but makes two.
Input: same lines, k = 0
Output: 1000
Input: same lines, k = 2
Output: 300
Constraints
1 <= n <= 3000,0 <= len(lines) <= 5000,0 <= k < n- Target
O(k * E)time.
Goals
- Bound the number of edges on a path with Bellman-Ford rounds
- Relax from a frozen copy so each round adds exactly one edge
- Handle unreachable and zero-stop cases