10278 - Fire Station

[Observer]

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.

[czar]

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]

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

[Monsoon]

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]

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]

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

[SDiZ]

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]

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

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

[SDiZ]

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]

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

[N|N0]

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]

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]

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]

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.

...

[helloneo]

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