## 10278 - Fire Station

**Moderator:** Board moderators

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.

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

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

[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(stationlocsq.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]}

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]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(stationsif(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]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]

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 itv is the furthest place from firestations.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.

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?

### 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:
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:
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"

--

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 ]
```

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

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

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

*= 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?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?

Seems that you don't understand what I mean......

Floyd's certainly NOT the only way to compute all-pair shortest paths.

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

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

...

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.