10278 - Fire Station

[Krzysztof Sikora]

I solved this problem but I got WA.
I used Dijkstra and set all cities with fire station on 0, others on infinity.
Could you help me? Maybe a trick?

[dwyak]

I found no trick. I just use a simple Floyd.
Are you sure there's nothing wrong with your program.

[Krzysztof Sikora]

I'm sure. Last year there was a contest in Poland. One of problem was the same meaning and I got ACCEPTED.

[Even]

I'm sure. Last year there was a contest in Poland. One of problem was the same meaning and I got ACCEPTED.

If the original input need no more fire station for minimize the max distance ... that is, if input like

2 2
1
2

what is your output ?

[hongping]

hi i tried using dijkstra n^3 to find distances between all pairs. then iterate through all possible intersection for placement of the new firestation, and then recalculate the max distance, and then find the best.
but i get time limit exceeded. any way to speed up?

[Krzysztof Sikora]

2 2
1
2

my output is 1.

[Krzysztof Sikora]

To Hongping.

You needn't iterate through all possible intersection.
Initially, you can put all firestations to heap and run Dijkstra.
Than find the intersection with the lowest distance.
Time Complexity O(E*logV).

[hongping]

Krzysztof,
thanks for the hint.
so i only need to do dijkstra for all the intersections with firestations.

what do you mean by " find the intersection with the lowest distance"?
how do i use this to find which position to place the new fire station?

thanks.

hongping

[Krzysztof Sikora]

Sorry, no lowest but highest. Find max in array of dist.

Normally we use Dijksta with one vertex (source) and dist for this vertex is 0.
In this case we use Dijkstra with a set (set of firestations) and for all vertex from this set dist is 0.
Now you must launch Dijksta. After it

Code: Select all

max := -1;
for all vertex v do
  if dist[v] > max then max := dist[v];
writeln(v);

v is the furthest place from firestations.

I wish it worked, but I don't know why.

[arc16]

hi guys,
i'm in the middle of testing my solution. could you tell me what is the output for the following input?

Code: Select all

2

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

thank you

[Krzysztof Sikora]

Output:

Code: Select all

1

1

Warning. My program is not ACCEPTED.

[arc16]

hmmm, same as mine... i still got WA too..
i have test the judge input using halt() (pascal), and it looks like there's an input when there's already one or more firestation in every intersection. So i think i have to find how to solve that case, but how

some of my though:
1. put the firestation in the 1st intersection which have the _least_ firestation relative to the other. for example:

Code: Select all

6 4
1
1
2
2
3
4
1 2 10
2 3 10
3 4 10
4 1 10

i would output 3, since intersect #1 and #2 already have 2 firestations but #3 and #4 have 1.

2. if above doesn't work (all intersection have the same number of firestation), put the firestation on intersection which have the most connecting road. for example:

Code: Select all

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

output is 2 (1 have 3 connecting roads, while others have only 1)

however, the judge still giving me WA anything that i miss? or my though above was wrong? please help....anyone

thanks

[Even]

hmmm, same as mine... i still got WA too..
i have test the judge input using halt() (pascal), and it looks like there's an input when there's already one or more firestation in every intersection. So i think i have to find how to solve that case, but how

some of my though:
1. put the firestation in the 1st intersection which have the _least_ firestation relative to the other. for example:

Code: Select all

6 4
1
1
2
2
3
4
1 2 10
2 3 10
3 4 10
4 1 10

i would output 3, since intersect #1 and #2 already have 2 firestations but #3 and #4 have 1.

2. if above doesn't work (all intersection have the same number of firestation), put the firestation on intersection which have the most connecting road. for example:

Code: Select all

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

output is 2 (1 have 3 connecting roads, while others have only 1)

however, the judge still giving me WA anything that i miss? or my though above was wrong? please help....anyone

thanks

both output should be 1 ( the minimun number )

[Even]

4

3 3
1
2
3
1 2 10
2 3 10
3 1 10

0 5

0 4
1 2 10
2 3 10
2 4 10

1 2
1
1 2 5

try it...

[arc16]

output is

Code: Select all

1

1

1

2

is it correct?