UVa 10278

From Algorithmist
Jump to: navigation, search

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