# UVa 10278

## Summary

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

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

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).

```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
```

```5

2

1

1
```