Expert · Graphs · 227 of 264
Cheapest network
Connect all n towns with cables as cheaply as possible (a minimum spanning tree). Use Kruskal's algorithm: take the cheapest cables first, skipping those that would close a loop.
Input: n and m, then m lines "a b cost"; all towns can be connected. Output: the total cost.
Examples
Input
4 5 1 2 1 2 3 2 3 4 3 1 4 4 1 3 5
Output
6
Input
2 1 1 2 9
Output
9
Input
3 3 1 2 5 2 3 5 1 3 1
Output
6
One more test checks other inputs when you press Check.
Stuck? The idea behind graphs
A graph is places (nodes) joined by edges. Keep it as a dictionary of neighbours: graph[a] is the list of nodes next to a.
Breadth-first search, with a queue, finds the shortest path when every step costs the same; Dijkstra's algorithm, with a heap, when steps cost different amounts.
from collections import deque
graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
dist = {1: 0}
queue = deque([1])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
print(dist[4])Watch for: Mark a node as seen when you add it to the queue, not when you take it out, or it is added many times.