# UVa 10278

## 10278 - Fire Station[edit]

## Summary[edit]

Dikstra with multi-sources. We need to put a fire station in one node for minimize the maximum distance from an intersection to a the nearest fire station.

## Explanation[edit]

This problem can be modelled as a graph of multiples sources. Try putting a Fire Station in every node, run Dijsktra, ask for the node more far of a Fire Station and save the result for the node that minimize this distance. When we are working with a multi-source graph, we can make a dummy node connected to every fire station with a distance equal to 0.

## Gotchas[edit]

The input doesn't specify the number of roads, only tells you there's a blank line after the set of roads.

Careful when there is no fire stations.

1 0 4 1 2 1 3 2 1 4 2 1

The answer is 2, because if we put a fire station in 1(for example), the max distance it's 2 (to the node 3).

## Input[edit]

4 1 6 2 1 2 10 2 3 10 3 4 10 4 5 10 5 6 10 6 1 10 0 4 1 2 1 3 2 1 4 2 1 3 6 2 5 4 1 2 20 2 3 10 3 4 15 4 5 20 5 6 10 6 1 10 4 6 2 3 4 5 1 2 20 2 3 10 3 4 15 4 5 20 5 6 10 6 1 10

## Output[edit]

5 2 1 1