10278  Fire Station
Moderator: Board moderators

 New poster
 Posts: 11
 Joined: Mon Sep 02, 2002 4:40 pm
 Location: Poland

 New poster
 Posts: 11
 Joined: Mon Sep 02, 2002 4:40 pm
 Location: Poland
OK. Output belongs to Even is correct.
At last I've got ACCEPTED.
My algorithm is almost good. It produced bad solutions for m = 0.
For this case you can find solution in time O(E) and overall O(ElogV).
In spite of that, my program has O(VElogV) complexity because there was less modification to create it.
At last I've got ACCEPTED.
My algorithm is almost good. It produced bad solutions for m = 0.
For this case you can find solution in time O(E) and overall O(ElogV).
In spite of that, my program has O(VElogV) complexity because there was less modification to create it.
 Krzysztof Sikora
the test data:
answer is 2.
node 1 to node 2 is 10. and from node 2, you can go to 3 and 4, distance of 10 each.
2 is the "central" node, and if you place firestation there, all other nodes only have a distance of 10 from node 2.
if you place the station at 1, 1 to 3 (1>2>3) is 20, and 1 to 4 is 20 as well.
did i understand this correctly?
Krzysztof, I understand you algorithm with a starting set of all nodes with firestations before launching dijkstra. so what was the error that caused your program to be Not accepted previously?
thanks.
=)
Code: Select all
0 4
1 2 10
2 3 10
2 4 10
node 1 to node 2 is 10. and from node 2, you can go to 3 and 4, distance of 10 each.
2 is the "central" node, and if you place firestation there, all other nodes only have a distance of 10 from node 2.
if you place the station at 1, 1 to 3 (1>2>3) is 20, and 1 to 4 is 20 as well.
did i understand this correctly?
Krzysztof, I understand you algorithm with a starting set of all nodes with firestations before launching dijkstra. so what was the error that caused your program to be Not accepted previously?
thanks.
=)
so i have to find the intersection which have the most/average shortest path to another intersection? from the matrix, can i just sum the total distance of every intersection to other intersection and find the minimum?
for the previous test case, my floydd matrix is:
sum of intersect #1 = 10+20+20 = 50
sum of intersect #2 = 10+10+10 = 30
sum of intersect #3 = 20+10+20 = 50
sum of intersect #4 = 20+10+20 = 50
so the answer is 2. Is it correct? If it is, why i'm still getting WA
(...almost give up...)
for the previous test case, my floydd matrix is:
Code: Select all
0 10 20 20
10 0 10 10
20 10 0 20
20 10 20 0
sum of intersect #2 = 10+10+10 = 30
sum of intersect #3 = 20+10+20 = 50
sum of intersect #4 = 20+10+20 = 50
so the answer is 2. Is it correct? If it is, why i'm still getting WA
(...almost give up...)
WA too
i think you are right... hmm... but i get WA too.
when there isnt any existing fire station, is it so that we should put the firestation at an intersection which has the
minimum (Maximum (shortest distance to ALL other nodes))
?
when there isnt any existing fire station, is it so that we should put the firestation at an intersection which has the
minimum (Maximum (shortest distance to ALL other nodes))
?
hello...arc16...
according to your method...
sample input can form an floyd like
your answer?? every intersection is the minimum...
do you miss understand what the problem means?
or I miss understand your method...
according to your method...
sample input can form an floyd like
Code: Select all
0 1 2 3 2 1 += 9
1 0 1 2 3 2 += 9
2 1 0 1 2 3 += 9
3 2 1 0 1 2 += 9
2 3 2 1 0 1 += 9
1 3 3 2 1 0 += 9
do you miss understand what the problem means?
or I miss understand your method...
Re: WA too
we should "always" put the new firestation at an intersection which has no other firestation and can cause the min_max_distance...hongping wrote:i think you are right... hmm... but i get WA too.
when there isnt any existing fire station, is it so that we should put the firestation at an intersection which has the
minimum (Maximum (shortest distance to ALL other nodes))
?
not only when there isn't any existing firestation...
if no such firestation exist, output is "1".

 New poster
 Posts: 11
 Joined: Mon Sep 02, 2002 4:40 pm
 Location: Poland
Because if #fs = 0 then for all vertex dist. from firestation to it was infinity and '1' was written and it is not correct.hongping wrote:Krzysztof, I understand you algorithm with a starting set of all nodes with firestations before launching dijkstra. so what was the error that caused your program to be Not accepted previously?
 Krzysztof Sikora
hi even,
first, thank you so much for your help
according to your hint, i change my algo to the following, please tell me where i go wrong...
first, thank you so much for your help
according to your hint, i change my algo to the following, please tell me where i go wrong...
Code: Select all
min = inf, nmin = 1
for all intersect i do
for all intersect j do
if no firestation in intersection j and distance[i,j]<min then
nmin = j
min = distance[i,j]
end if
end for
end for
if nmin=1 then nmin=1
Code: Select all
min = inf, nmin = 1
for all intersect i do
for all intersect j do
if no firestation in intersection j and distance[i,j]<min then
nmin = j
min = distance[i,j]
end if
end for
end for
if nmin=1 then nmin=1
that is... if there are three sites A, B, C, two roads AB 1, BC 2, and existing one firestation [] at C...
I express it as A 2 B 1 [C]
then the distance from each site to its nearest firestation is
A B C
3 1 0 ... and the maximum distance is 3
now, we wanna set a new firestation to minimize the maximun distance
if set at A
then the distance from each site to its nearest firestation become
A B C
0 1 0 ... and the maximum distance is 1
if set at B
then the distance from each site to its nearest firestation become
A B C
2 0 0 ... and the maximum distance is 2
we should set at A for the maximum distance is less than if we set at B
according to this example...
My method first find the minimum distance from any pair d[j]
and find ecah site its nearest distance to the nearest firestation min
second,
MIN_MAX ( the maximum distance before add a new firestation )
MIN_MAX_P = 1
for each site i which is not firestation {
for ecah site j which is not firestation
max = maximun( max, minimun( d[j], min ) )
if max < MIN_MAX then MIN_MAX = max, MIN_MAX_P = i ;
}
wish you understand it... Good Luck

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
Hello
I'm having problems with this very problem.
I've got a Time Limit Exceed. After having tested around, I found that it was my floyd algorithm who was too long (no TLE because of infinte loop in input parsing, nothing of the kind).
I'm doing floyd on the whole graph (where the vertices are the intersections and the edges are the road)... Does anyone use the same, or should I use something else ?
Thanks by advance
I'm having problems with this very problem.
I've got a Time Limit Exceed. After having tested around, I found that it was my floyd algorithm who was too long (no TLE because of infinte loop in input parsing, nothing of the kind).
I'm doing floyd on the whole graph (where the vertices are the intersections and the edges are the road)... Does anyone use the same, or should I use something else ?
Thanks by advance

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact: