Page 1 of 4

10278 - Fire Station

Posted: Mon Sep 02, 2002 4:48 pm
by 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?

Posted: Mon Sep 02, 2002 7:24 pm
by dwyak
I found no trick. I just use a simple Floyd.
Are you sure there's nothing wrong with your program.

Posted: Mon Sep 02, 2002 11:45 pm
by Krzysztof Sikora
I'm sure. Last year there was a contest in Poland. One of problem was the same meaning and I got ACCEPTED.

Posted: Sun Sep 15, 2002 8:46 pm
by Even
Krzysztof Sikora wrote: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 ? :)

time limit exceeded

Posted: Sun Sep 15, 2002 11:43 pm
by 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?

Posted: Sat Sep 21, 2002 11:00 am
by Krzysztof Sikora
2 2
1
2
my output is 1.

Posted: Sat Sep 21, 2002 11:05 am
by 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).

Posted: Sat Sep 21, 2002 2:50 pm
by 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

Posted: Sat Sep 21, 2002 3:33 pm
by 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.

Posted: Tue Sep 24, 2002 2:23 am
by 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 :)

Posted: Tue Sep 24, 2002 9:58 am
by Krzysztof Sikora
Output:

Code: Select all

1

1
Warning. My program is not ACCEPTED.

Posted: Wed Sep 25, 2002 1:46 am
by 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

Posted: Wed Sep 25, 2002 9:25 am
by Even
arc16 wrote: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 )

How about this...

Posted: Wed Sep 25, 2002 9:28 am
by 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...

Posted: Wed Sep 25, 2002 10:25 am
by arc16
output is

Code: Select all

1

1

1

2
is it correct?