## 10278 - Fire Station

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Krzysztof Sikora
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?
-- Krzysztof Sikora

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:
I found no trick. I just use a simple Floyd.
Are you sure there's nothing wrong with your program.

Krzysztof Sikora
New poster
Posts: 11
Joined: Mon Sep 02, 2002 4:40 pm
Location: Poland
I'm sure. Last year there was a contest in Poland. One of problem was the same meaning and I got ACCEPTED.
-- Krzysztof Sikora

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
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 ?

hongping
New poster
Posts: 11
Joined: Fri Jul 26, 2002 5:43 pm

### 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?

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

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).
Last edited by Krzysztof Sikora on Sat Sep 21, 2002 3:20 pm, edited 1 time in total.
-- Krzysztof Sikora

hongping
New poster
Posts: 11
Joined: Fri Jul 26, 2002 5:43 pm
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
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

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.
-- Krzysztof Sikora

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
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
New poster
Posts: 11
Joined: Mon Sep 02, 2002 4:40 pm
Location: Poland
Output:

Code: Select all

``````1

1``````
Warning. My program is not ACCEPTED.
-- Krzysztof Sikora

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
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
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
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 )

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

### 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...

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
output is

Code: Select all

``````1

1

1

2
``````
is it correct?