Problem context and objectives
Mission briefing
Realm network architect · Routes have costs, dependencies, and unreliable bridges
Choose the next frontier that preserves the route guarantee: The Threshold City.
One locally tempting edge can invalidate the whole journey.
How you win
- 1Recognize when Floyd-Warshall threshold counting matches the clues
- 2Keep this true after every move: the distance matrix contains the cheapest path between every city pair
- 3Reach the result within O(V cubed)
Rules and pressure
- Target cost: O(V cubed)
- State rule: the distance matrix contains the cheapest path between every city pair
Lesson 1 of 3
Live algorithm trace
Floyd-Warshall threshold counting
Complete execution1 of 6
0
city
1
2
3
Build the symmetric direct-distance matrix.
1
build an undirected distance matrix2
run Floyd-Warshall3
for each city4
count other cities within threshold5
replace answer on count <= best6
return greatest tied indexthreshold = 4directEdges = 4
Truth to preserve / Cost target
Truth to preserve
the distance matrix contains the cheapest path between every city pair
Cost target
O(V cubed)
After all-pairs shortest paths, count for each city how many others lie within the distance threshold. Select the smallest count, breaking ties toward the greatest city index.
Your call · What should guide every step of this algorithm?