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

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

Post by Observer » Tue Dec 02, 2003 4:55 pm

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

Post by czar » Mon Jul 05, 2004 6:22 pm

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;
len = adjmat[v].size();

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

u = adjmat[v];
w = weights[v][adjmat[v]];

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;
VVI weights,adjmat;

int station;
int x,y,z;

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

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

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;
adjmat[y].push_back(x);
adjmat[x].push_back(y);
weights[x][y] = weights[y][x] = z;
}

cout<<go(adjmat,weights,stations,stationlocs)<<endl;

}

return 0;
}
[/cpp]

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

Post by InOutMoTo » Thu Jul 29, 2004 5:00 pm

TO Julien Cornebise:

Try to use link-list to store edges instead of adj-matrix.
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 :lol:

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Wed Jul 20, 2005 2:29 pm

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.

Post by SDiZ » Mon Aug 15, 2005 12:13 pm

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)

so the answer is "7"


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

Post by Observer » Wed Aug 17, 2005 5:49 pm

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 :wink:
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:

Post by SDiZ » Wed Aug 17, 2005 6:36 pm

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

Post by Observer » Thu Aug 18, 2005 12:13 pm

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:

Post by SDiZ » Thu Aug 18, 2005 2:03 pm

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:

Post by SDiZ » Fri Aug 19, 2005 5:46 pm

okay, i get A.C. eventally.
I didn't knew Floyd is that slow..

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Sun Sep 11, 2005 8:35 pm

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.

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Sun Sep 11, 2005 9:06 pm

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:

Post by SDiZ » Mon Sep 12, 2005 2:01 am

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!)

Post by Ynobe » Thu Feb 01, 2007 10:37 am

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. :oops:

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

Post by helloneo » Thu Feb 01, 2007 12:01 pm

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

Post Reply

Return to “Volume 102 (10200-10299)”