## 10278 - Fire Station

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Plz anyone plz help me

I'm getting TLE, and I still can't figure out how I can get the answer without consider all possible intersections in turn...

So... any hints? Thanks in advance.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

czar
New poster
Posts: 15
Joined: Tue Jun 10, 2003 7:30 pm

### 10278 fire stations runtime error

I am getting a runtime error and I have no idea why....

[cpp]#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<numeric>

using namespace std;

typedef vector<vector<int> > VVI;
typedef vector<int> VI;

int nis,nfs;

typedef struct Cell Cell;
struct Cell {
int v;
int weight;
Cell(){}
Cell(int rv, int rweight): v(rv),weight(rweight) {}
};

bool operator<(const Cell &a, const Cell &b) {
return a.weight < b.weight;
}

int maxdist(VVI &adjmat, VVI& weights, int start, VI &stationlocs) {

VI inpath(nis+1);
VI dist(nis+1,INT_MAX);

int v = start,u;
int w;
int len = 0;

priority_queue<Cell> q;

Cell c;

for(int i = 0; i < stationlocs.size(); i++) {

dist[stationlocs] = 0;
q.push(Cell(stationlocs,0));

}

dist[v] = 0;

while( !inpath[v] ) {

inpath[v] = 1;

for(int i = 0; i < len; ++i) {

if(dist > dist[v]+w)
dist = dist[v]+w;

q.push(Cell(u,dist));

}

while( !q.empty() && inpath[v] ) {

c = q.top(); q.pop();
v = c.v;

}

}

return *max_element(dist.begin()+1,dist.end());

}

int go(VVI &adjmat, VVI &weights, VI &stations, VI &stationlocs) {

int mini = INT_MAX;
int ret = 1;
int res;

for(int i = 1; i <= nis; i++) {

if(stations)
continue;

res = maxdist( adjmat, weights, i, stationlocs );

if( res < mini ) {
mini = res;
ret = i;
}

}

return ret;

}

int main() {

int ncases;

cin>>ncases,cin.ignore(),cin.ignore();

for(int ncase = 0; ncase < ncases; ++ncase,cin.ignore()) {

VI stations,stationlocs;

int station;
int x,y,z;

cin>>nfs>>nis,cin.ignore();

stations = VI(nis+1);
weights = VVI(nis+1,VI(nis+1, INT_MAX));

for(int nf = 0; nf < nfs; ++nf) {
cin>>station,cin.ignore();
if(!stations[station])
stationlocs.push_back(station);
stations[station] = 1;
}

for(int ni = 0; ni < nis; ++ni) {
cin>>x>>y>>z;
weights[x][y] = weights[y][x] = z;
}

}

return 0;
}
[/cpp]

InOutMoTo
New poster
Posts: 18
Joined: Sun Aug 10, 2003 12:47 pm
TO Julien Cornebise:

Because this prob have 10000 edges (500*20) fewer than 500*500.
I use this method to get AC. (but very slow)

Or you can optimize Dijkstra with heap (ElogV)
can get AC within 2 secs

Best regards

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
Krzysztof Sikora wrote: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.

I don't know, maybe i misunderstood this algorithm but consider this case:
1 10
1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
2 7 1
7 8 1
8 9 1
9 10 1

when we compute the distance we have:
d[1]=0 d[2]=1 d[3]=2 d[4]=3 d[5]=4 d[6]=5 d[7]=2 d[8]=3 d[9]=4 d[10]=5

so according to this algo we choose 6, but then the will be max_dist=5,
and when we choose 2 the max_dist will be 4.
what i misunderstand or maybe this algo is wrong?

SDiZ
New poster
Posts: 13
Joined: Fri Aug 05, 2005 12:20 pm
Location: Hong Kong
Contact:

### 10278 - clarification needed.

I guess I may have misunderstood something on 10278

My understand 10278 is :
Minimizing the maximum distance from all intersetion to it's nearest firestation.

For example,

Case 1:

Code: Select all

``````   * = with firestation
Assume all path are equal length

[ 1 ] ------ [ 2 ] ------ [ 3* ] ------ [ 4 ] ------ [ 5 ]
``````
No matter where do I put the new firestation, the maximum distance is still 2. So we pick the lowest intersection number, i.e. "1".

Case 2:

Code: Select all

``````   * = with firestation
Assume all path are equal length

[ 1 ] -- [ 2 ] -- [ 3 ] -- [ 4* ] -- [ 5 ] -- [ 6 ] -- [ 7 ] -- [ 8 ] -- [ 9 ] -- [ 10 ]
``````
If we put the fs at 6, the max distance is 4 (6->7->8->9->10)
If we put the fs at 7, the max distance is 3 (4->3->2->1)
If we put the fs at 8, the max distance is 3..(4->3->2->1)
If we put the fs at 9, the max distance is 3..(4->3->2->1)
If we put the fs at 10, the max distance is 3..(4->3->2->1)

Is that correct?
If yes, how can we do it without tring all intersetions? ( i got TLE using floyd )
--

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Hi,

You can get Accepted in this task even if you attempt to try all intersections. Hint: Floyd is NOT optimal here to calculate all-pair shortest paths.

Happy programming
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

SDiZ
New poster
Posts: 13
Joined: Fri Aug 05, 2005 12:20 pm
Location: Hong Kong
Contact:
I use an all-pair shortest path algorithm here, because i can update the new maximum distance in O(n) time. ( using the relation NewNearestDistanceFromCity = MIN( OldNearestDistanceFromCity, Distanace[ NewFireStation, i ] ) )

I have seen some post saying putting all firestation to a heap, and run dijkstra. In that case, we can't do a incremental update of the maximum distance, shouldn't it be slower?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Seems that you don't understand what I mean......

Floyd's certainly NOT the only way to compute all-pair shortest paths.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

SDiZ
New poster
Posts: 13
Joined: Fri Aug 05, 2005 12:20 pm
Location: Hong Kong
Contact:
Observer wrote:Seems that you don't understand what I mean......

Floyd's certainly NOT the only way to compute all-pair shortest paths.
Floyd is the only all-pair shortest paths i know how to code. Or did you means useing a single-source, all destination algorithm and repeat N times?

SDiZ
New poster
Posts: 13
Joined: Fri Aug 05, 2005 12:20 pm
Location: Hong Kong
Contact:
okay, i get A.C. eventally.
I didn't knew Floyd is that slow..

N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:
This algorithms tries to read exactly number_of_intersection lines which describe segments. But any number of road segments can follow. We read (intersection_1, intersection_2, road length) information until we reach an empty line.

N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:
What did you use instead of Floyd?
Did you try placing a firestation on every empty intersection and running special-Dijkstra?
Or just used some other all-pairs algorithm and then doing the job...

SDiZ
New poster
Posts: 13
Joined: Fri Aug 05, 2005 12:20 pm
Location: Hong Kong
Contact:
N|N0 wrote:What did you use instead of Floyd?
Did you try placing a firestation on every empty intersection and running special-Dijkstra?
Or just used some other all-pairs algorithm and then doing the job...

I just use Dijkstra on every feasible sol'n

Ynobe
New poster
Posts: 1
Joined: Sat Jan 27, 2007 2:36 am

### 10278 [fire station ] RTE(Run time error!)

I tried using Floyid to solve the problem.

But my program got "Run time error"

Do I have to use dijkstra algorithm?

Is there anyone who use floyd but got acepted?

plz notice me.

...
Last edited by Ynobe on Fri Feb 02, 2007 12:42 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
There are some threads on this problem..
So just try to search first and don't open a new thread if there is one..
Your floyd has nothing to do with RTE..