10278  Fire Station
Moderator: Board moderators

 New poster
 Posts: 11
 Joined: Mon Sep 02, 2002 4:40 pm
 Location: Poland
10278  Fire Station
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?
I used Dijkstra and set all cities with fire station on 0, others on infinity.
Could you help me? Maybe a trick?
 Krzysztof Sikora

 New poster
 Posts: 11
 Joined: Mon Sep 02, 2002 4:40 pm
 Location: Poland
time limit exceeded
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?
but i get time limit exceeded. any way to speed up?

 New poster
 Posts: 11
 Joined: Mon Sep 02, 2002 4:40 pm
 Location: Poland
my output is 1.2 2
1
2
Last edited by Krzysztof Sikora on Sat Sep 21, 2002 3:21 pm, edited 1 time in total.
 Krzysztof Sikora

 New poster
 Posts: 11
 Joined: Mon Sep 02, 2002 4:40 pm
 Location: Poland
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).
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).
Last edited by Krzysztof Sikora on Sat Sep 21, 2002 3:20 pm, edited 1 time in total.
 Krzysztof Sikora

 New poster
 Posts: 11
 Joined: Mon Sep 02, 2002 4:40 pm
 Location: Poland
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
v is the furthest place from firestations.
I wish it worked, but I don't know why.
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);
I wish it worked, but I don't know why.
 Krzysztof Sikora
hi guys,
i'm in the middle of testing my solution. could you tell me what is the output for the following input?
thank you
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

 New poster
 Posts: 11
 Joined: Mon Sep 02, 2002 4:40 pm
 Location: Poland
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:
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:
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
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
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
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 )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:
i would output 3, since intersect #1 and #2 already have 2 firestations but #3 and #4 have 1.Code: Select all
6 4 1 1 2 2 3 4 1 2 10 2 3 10 3 4 10 4 1 10
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:
output is 2 (1 have 3 connecting roads, while others have only 1)Code: Select all
4 4 1 2 3 4 1 2 1 1 3 1 1 4 1 4 1 1
however, the judge still giving me WA anything that i miss? or my though above was wrong? please help....anyone
thanks
How about this...
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...
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...
output is
is it correct?
Code: Select all
1
1
1
2