10278 - Fire Station
Moderator: Board moderators
Re: 10278 - Fire Station
Here's 1 more tricky test case, where the correct output is 1 even though there's already a fire station there. So don't immediately reject any intersection that already has a fire station. Be careful on TLE though, because after making this change my code went from 1sec to 6sec.
1
1 2
1
1 2 0
1
1 2
1
1 2 0
Re: 10278 - Fire Station
Isn't that wrong? The answer should be 2, since that location doesn't have any station already.stcheung wrote:Here's 1 more tricky test case, where the correct output is 1 even though there's already a fire station there. So don't immediately reject any intersection that already has a fire station. Be careful on TLE though, because after making this change my code went from 1sec to 6sec.
1
1 2
1
1 2 0
-
- Learning poster
- Posts: 72
- Joined: Tue May 30, 2006 5:57 pm
- Location: bangladesh
Re: 10278 - Fire Station
Actually the tricky part is below.
input:
output will be:
No intersection without fire station. so Answer is 1.
input:
Code: Select all
1
2 2
1
2
1 2 10
Code: Select all
1
Mak
Help me PLZ!!
Help me PLZ!!
-
- New poster
- Posts: 1
- Joined: Fri Dec 17, 2010 6:16 am
Re: 10278 - Fire Station
I got snagged by some tricky inputs, so I'll give a sample output from my ACC program.
Most of these inputs have already been posted, but this combination was:
- Brutal on my program, and
- Easy to verify at a glance
Input:
The correct output is:
Hope this helps someone, and best of luck!
Most of these inputs have already been posted, but this combination was:
- Brutal on my program, and
- Easy to verify at a glance
Input:
Code: Select all
8
2 2
1
2
1 2 10
0 4
1 2 10
2 3 10
2 4 10
2 7
1
4
1 2 5
1 4 30
1 3 20
2 4 45
2 5 25
3 4 15
3 6 35
5 7 10
6 7 40
1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10
1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10
1 8
3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
1 9
3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
1 8
1
1 2 1
2 3 2
3 4 2
3 5 2
3 6 2
3 7 2
3 8 15
Code: Select all
1
2
3
4
5
6
7
8
Problem in reading input
Hi, im new to UVa and finds that sometimes input-output here quite non-trivial.
I just want to work on this problem http://uva.onlinejudge.org/index.php?op ... oblem=1219
but I can't code to detect the blank lines between each testcase. I also found that this kind of input format is common for UVa problems (reading input until some blank lines).
I have tried using getline but still not working.
Anyone can help me with C++ code for reading input like the problem above ? (http://uva.onlinejudge.org/index.php?op ... oblem=1219)
Thanks before
I just want to work on this problem http://uva.onlinejudge.org/index.php?op ... oblem=1219
but I can't code to detect the blank lines between each testcase. I also found that this kind of input format is common for UVa problems (reading input until some blank lines).
I have tried using getline but still not working.
Anyone can help me with C++ code for reading input like the problem above ? (http://uva.onlinejudge.org/index.php?op ... oblem=1219)
Thanks before
I Ac All the Samples that you gave, But WA,WHY!!HELP!!!
#include<cstdio>
#include<cstring>
using namespace std;
int map[501][501],zj[501],yl[102],now[501];
bool used[501];
int main()
{
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
int i,j,k,l,n,m,t,o=0;scanf("%d\n",&t);
while (t--)
{
if (o)printf("\n");o=1;
scanf("%d %d",&m,&n);
memset(used,0,sizeof(used));
memset(map,60,sizeof(map));
for (i=1;i<=m;i++){scanf("%d\n",&yl);used[yl]=1;}
char s[300];
gets(s);
while (gets(s) != NULL && s[0] != '\0')
{
int x,y,z;
sscanf(s, "%d%d%d", &x, &y, &z);
map[x][y] = map[y][x] = z;
}
for (i=1;i<=n;i++)map=0;
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
{
if (k==i)continue;
for (j=1;j<=n;j++)
if (j!=i&&j!=k&&map[k]+map[k][j]<map[j])
map[j]=map[k]+map[k][j];
}
memset(zj,50,sizeof(zj));
int gd=100000000,gdn=1;
for (k=1;k<=n;k++)
if (!used[k])
{
int big=-1,bn;yl[m+1]=k;
memset(zj,60,sizeof(zj));
for (i=1;i<=n;i++)
for (j=1;j<=m+1;j++)
if (zj>map[yl[j]])
zj[i]=map[i][yl[j]];
for (i=1;i<=n;i++)
if (big<zj[i]){big=zj[i];}
if (big<gd){gd=big;gdn=k;}
}
printf("%d\n",gdn);
}
return 0;
}
#include<cstring>
using namespace std;
int map[501][501],zj[501],yl[102],now[501];
bool used[501];
int main()
{
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
int i,j,k,l,n,m,t,o=0;scanf("%d\n",&t);
while (t--)
{
if (o)printf("\n");o=1;
scanf("%d %d",&m,&n);
memset(used,0,sizeof(used));
memset(map,60,sizeof(map));
for (i=1;i<=m;i++){scanf("%d\n",&yl);used[yl]=1;}
char s[300];
gets(s);
while (gets(s) != NULL && s[0] != '\0')
{
int x,y,z;
sscanf(s, "%d%d%d", &x, &y, &z);
map[x][y] = map[y][x] = z;
}
for (i=1;i<=n;i++)map=0;
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
{
if (k==i)continue;
for (j=1;j<=n;j++)
if (j!=i&&j!=k&&map[k]+map[k][j]<map[j])
map[j]=map[k]+map[k][j];
}
memset(zj,50,sizeof(zj));
int gd=100000000,gdn=1;
for (k=1;k<=n;k++)
if (!used[k])
{
int big=-1,bn;yl[m+1]=k;
memset(zj,60,sizeof(zj));
for (i=1;i<=n;i++)
for (j=1;j<=m+1;j++)
if (zj>map[yl[j]])
zj[i]=map[i][yl[j]];
for (i=1;i<=n;i++)
if (big<zj[i]){big=zj[i];}
if (big<gd){gd=big;gdn=k;}
}
printf("%d\n",gdn);
}
return 0;
}
-
- New poster
- Posts: 2
- Joined: Mon Apr 30, 2012 12:50 am
Re: 10278 - Fire Station
Stargazer71 wrote:I got snagged by some tricky inputs, so I'll give a sample output from my ACC program.
Most of these inputs have already been posted, but this combination was:
- Brutal on my program, and
- Easy to verify at a glance
Input:
The correct output is:Code: Select all
8 2 2 1 2 1 2 10 0 4 1 2 10 2 3 10 2 4 10 2 7 1 4 1 2 5 1 4 30 1 3 20 2 4 45 2 5 25 3 4 15 3 6 35 5 7 10 6 7 40 1 7 2 1 2 10 2 3 10 3 4 10 4 5 10 5 6 10 6 7 10 7 1 10 1 6 2 1 2 10 2 3 10 3 4 10 4 5 10 5 6 10 6 1 10 1 8 3 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 1 9 3 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 1 8 1 1 2 1 2 3 2 3 4 2 3 5 2 3 6 2 3 7 2 3 8 15
Hope this helps someone, and best of luck!Code: Select all
1 2 3 4 5 6 7 8
why output of this input is 4, I think it must be 5 ?
Code: Select all
1
1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10
distance of Intersection 4 to Fire station 2 is 20, But distance of Intersection 5 to that Fire Station is 30.
Please help me,
I Can't get AC.
I write this Code :
Code: Select all
#include<iostream>
#include<string>
#include <sstream>
#define MAXINT 2147483647
#define size 502
using namespace std;
int floyd( int Graph[][size] , int I ,int f)
{
int IndexMax = 1 ;
if( f!= 0 )
{
int through_k;
for( int k = 1 ; k <= I+1 ; k++ )
{
for(int i =1 ; i < I + 2 ; i++ )
{
for( int j =1 ; j < I + 2 ; j++ )
{
if(Graph[i][k] == MAXINT||Graph[k][j] ==MAXINT)
through_k = MAXINT;
else
through_k = Graph[i][k]+Graph[k][j];
if(through_k < Graph[i][j])
Graph[i][j]=through_k;
}
}
}
int MaxD = Graph[1][I+1];
for( int i = 2 ; i < I + 1 ; i++ )
{
if ( MaxD < Graph[i][I+1] )
{
MaxD = Graph[i][I+1];
IndexMax = i ;
}
}
return IndexMax;
}
else
{
int MaxD = 0;
for( int i = 1 ; i < I + 1 ; i++ )
{
int val = 0 ;
for( int j = 1 ; j < I+1 ; j++ )
{
if( i == j )
continue;
val+=Graph[i][j];
}
if ( MaxD < val )
{
MaxD = val;
IndexMax = i ;
}
}
return IndexMax;
}
}
int main()
{
int NumberOfTestCase;
cin>>NumberOfTestCase;
for(int number = 0 ; number < NumberOfTestCase ; number++)
{
int Graph[ size ] [ size ];
int F , I ;
cin >> F >> I ;
for( int i = 0 ; i < I + 2 ; i++ )
for( int j = 0 ; j < I + 2 ; j++ )
Graph[i][j]=MAXINT;
for( int i = 0 ; i < F ; i++ )
{
int FirStation ;
cin>>FirStation;
Graph[I+1][FirStation] = 0;
Graph[FirStation][I+1] = 0;
}
string Input ;
cin.ignore(10, '\n' );
getline(cin,Input,'\n');
while( !Input.empty())
{
istringstream iss(Input);
int v1 , v2 , Edge;
iss>>v1;
iss>>v2;
iss>>Edge;
Graph[v1][v2] = Edge;
Graph[v2][v1] = Edge;
getline(cin,Input,'\n');
}
cout<<floyd(Graph , I , F ) <<endl ;
}
return 0 ;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10278 - Fire Station
For this input, there is already a fire station at 2:
If you put the new fire station at 4, the distance from each intersection to the nearest fire station is:
1: 10
2: 0
3: 10
4: 0
5: 10
6: 20
7: 20
If you put the new fire station at 5, the distance from each intersection to the nearest fire station is:
1: 10
2: 0
3: 10
4: 10
5: 0
6: 10
7: 20
I think you misunderstood the question. You are to find the intersection to put the new fire station to minimize the maximum distance from any intersection to the nearest fire station. If you put the new fire station at intersection 4 or 5 the max distance is 20 so in that case you pick the lowest intersection number.
Code: Select all
1
1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10
1: 10
2: 0
3: 10
4: 0
5: 10
6: 20
7: 20
If you put the new fire station at 5, the distance from each intersection to the nearest fire station is:
1: 10
2: 0
3: 10
4: 10
5: 0
6: 10
7: 20
I think you misunderstood the question. You are to find the intersection to put the new fire station to minimize the maximum distance from any intersection to the nearest fire station. If you put the new fire station at intersection 4 or 5 the max distance is 20 so in that case you pick the lowest intersection number.
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 2
- Joined: Mon Apr 30, 2012 12:50 am
Re: 10278 - Fire Station
Thank you,
I write this code for minimize maximum dis. but I got Run-time error,
I don't know why,
I compiled this code , every thing was Okay.
I write this code for minimize maximum dis. but I got Run-time error,
I don't know why,
I compiled this code , every thing was Okay.
Code: Select all
#include<iostream>
#include<sstream>
#include<vector>
#define INF 2147483647
#define SIZE 502
using namespace std;
template <class T>
class PriorityQueue
{
private:
vector<int> Key;
vector<T> element;
vector<int>::iterator it;
void insert(const T &value,const int &key ,const int l ,const int h)
{
if( h<=l )
{
if(Key.at(l)>= key )
{
it = element.begin();
//it++;
element.insert(it+l,value);
it = Key.begin();
//it++;
Key.insert(it+l,key);
}
else
{
it = element.begin();
it++;
element.insert(it+l,value);
it = Key.begin();
it++;
Key.insert(it+l,key);
}
}
else
{
int mid = ( l + h ) / 2 ;
if ( Key.at( mid ) == key ) // maybe queue have two element with same Priority
{
it = element.begin();
//it++;
element.insert(it+mid,value);
it = Key.begin();
//it++;
Key.insert(it+mid,key);
}
else if( Key.at( mid ) > key )
{
insert(value,key,l,mid-1 );
}
else if ( Key.at( mid ) < key )
{
insert(value,key,mid+1,h );
}
}
}
public:
PriorityQueue(const PriorityQueue& Copy)
{
Key = Copy.Key;
element = Copy.element;
}
PriorityQueue operator=(const PriorityQueue& Copy)
{
Key = Copy.Key;
element = Copy.element;
return *this;
}
PriorityQueue()
{
}
bool empty()
{
return element.empty();
}
int size()
{
return element.size();
}
void push(const T& value ,const int& key)
{
if(element.empty())
{
element.push_back(value);
Key.push_back(key);
}
else
{
int s= element.size()-1;
insert(value,key,0,s);
}
}
T popLowestPriority()
{
T temp = element.at(0);
it = element.begin();
element.erase(it);
it = Key.begin();
Key.erase(it);
return temp ;
}
T popHighestPriority()
{
T temp = element.back();
element.pop_back();
Key.pop_back();
return temp ;
}
void changePriority(T value , int newKey)
{
it = element.begin();
int elementSize = element.size();
for( int i = 0 ; i < elementSize ; i++ )
{
if( element.at( i ) == value )
{
element.erase( it+i);
it = Key.begin();
Key.erase(it+i);
this->push(value,newKey);
}
}
}
};
class graph
{
private:
vector<int> GraphAdj[ 3 ];
vector<int> Locate;
int Order;
public:
graph( const graph& Copy )
{
for( int i = 0 ; i < 3 ; i++ )
{
GraphAdj[ i ] = Copy.GraphAdj[ i ];
}
Locate = Copy.Locate;
Order = Copy.Order;
}
graph operator=(const graph& Copy )
{
for( int i = 0 ; i < 3 ; i++ )
{
GraphAdj[ i ] = Copy.GraphAdj[ i ];
}
Locate = Copy.Locate;
Order = Copy.Order;
return *this;
}
int getOrder()
{
return Order;
}
int getSize()
{
return GraphAdj[ 2 ].at( 0 );
}
void UpdateLocate()
{
int LocateSize = Locate.size();
int GraphAdjSize = GraphAdj[0].size();
for( int i = 1 ; i < LocateSize ; i++ )
Locate.at( i ) = -1 ;
//
int temp = GraphAdj[0].at( 1 );
Locate.at(temp) = 1;
for( int i = temp + 1 ; i < GraphAdjSize ; i++ )
{
if ( temp != GraphAdj[ 0 ].at( i ) )
{
temp = GraphAdj[0].at( i );
Locate.at(temp) = i;
}
}
}
int Dijkstra_Find_farestCity(const int& s)
{
//cout<<endl << endl <<"Start"<<endl<<endl ;
PriorityQueue<int> Q ;
vector<int> d (Order);
int dSize = d.size();
for( int i = 1 ; i < dSize ; i++ )
{
if( i != s )
{
Q.push(i, INF );
d.at( i ) = INF ;
}
else if ( i == s )
{
Q.push(i, 0 );
d.at( i ) = 0;
}
}
//
//cout<<"Size Q is: " << Q.size() <<endl;
while( !Q.empty() )
{
int u = Q.popLowestPriority();
int LocateU = Locate.at( u ) ;
int temp = GraphAdj[ 0 ].at( LocateU );
int i = LocateU;
int GraphAdjSize = GraphAdj[1].size();
while( i < GraphAdjSize && (temp == GraphAdj[ 0 ].at( i )))
{
int v = GraphAdj[ 1 ].at( i ) ;
int wuv = GraphAdj[2].at( i );
int dist;
if( d.at( u ) == INF )
dist = INF;
else
{
dist = d.at( u ) + wuv ;
}
if( d.at( v ) > dist )
{
d.at( v ) = dist ;
Q.changePriority(v,dist);
}
i++;
}
}
int maxD = 0;
for( int i = 1 ; i <dSize -1 ; i++ )
if ( d.at( i ) != INF && maxD < d.at( i ) )
maxD = d.at( i ) ;
return maxD;
}
int getEdge( const int& v1 , const int& v2 )
{
int i1 = Locate.at( v1 ) ;
if( i1 == -1 )
return INF ;
int temp = GraphAdj[ 0 ].at( i1 );
int i2 = i1 ;
int GraphAdjSize = GraphAdj[ 1 ].size();
while( ( i2 <GraphAdjSize ) && ( temp == (GraphAdj[ 0 ].at( i2 ))) )
{
if( GraphAdj[ 1 ].at( i2 ) == v2 )
return GraphAdj[2].at(i2);
else
i2++;
}
return INF;
}
void addEdge(const int& v1,const int& v2 ,const int& w , bool update=false )
{
if( GraphAdj[ 0 ].size() == 1 )
{
}
int i = 1 ;
int GraphAdjSize = GraphAdj[ 0 ].size();
while( i < GraphAdjSize && GraphAdj[ 0 ].at( i ) < v1 )
{
i++;
}
if( i == GraphAdj[ 0 ].size() )
{
GraphAdj[ 0 ].push_back( v1 );
GraphAdj[ 1 ].push_back( v2 );
GraphAdj[ 2 ].push_back( w );
}
else
{
vector<int>::iterator it;
it = GraphAdj[0].begin();
GraphAdj[ 0 ].insert(it+i,v1);
it = GraphAdj[1].begin();
GraphAdj[ 1 ].insert(it+i,v2);
it = GraphAdj[2].begin();
GraphAdj[ 2 ].insert(it+i,w);
}
GraphAdj[2].at(0)++;
//update Locate
if( update == true )
{
UpdateLocate();
}
}
void removeEdge(const int& v1 , const int& v2 )
{
int i1 = Locate.at( v1 ) ;
if( i1 == -1 )
return ;
int temp = GraphAdj[ 0 ].at( i1 );
int i2 = i1 ;
int GraphAdjSize = GraphAdj[ 1 ].size();
while( ( i2 <GraphAdjSize ) && ( temp == (GraphAdj[ 0 ].at( i2 ))) )
{
if( GraphAdj[ 1 ].at( i2 ) == v2 )
{
vector<int>::iterator it;
it = GraphAdj[ 0 ].begin();
GraphAdj[0].erase(it+i2);
it = GraphAdj[ 1 ].begin();
GraphAdj[1].erase(it+i2);
it = GraphAdj[ 2 ].begin();
GraphAdj[2].erase(it+i2);
GraphAdj[2].at(0)--;
//update Locate
UpdateLocate();
return;
}
else
i2++;
}
}
graph(int order)
{
Order = order+1;
//Locate.resize(Order);
for( int i = 0 ; i < Order ; i++ )
Locate.push_back(-1);
GraphAdj[ 0 ].push_back(Order);
GraphAdj[ 1 ].push_back(Order);
GraphAdj[ 2 ].push_back(0);
}
};
int findIntersection( graph& g , int I ,int NumberOfFireStation)
{
vector<int> MaxDistance ( I+2 ) ;
//
for( int i = 1 ; i < I + 1 ; i++ )
{
//Build FireStation on Intersetion i
graph g1 = g ;
int sg = g.getSize();
g1.addEdge(i,I+1,0);
g1.addEdge(I+1,i,0,true);
int sg1 = g1.getSize();
MaxDistance[ i ] = g1.Dijkstra_Find_farestCity(I+1);
}
int MinD = MaxDistance[1],IndexMin = 1 ;
for( int i = 2 ; i < I + 1 ; i++ )
{
if( MinD > MaxDistance[ i ] )
{
MinD = MaxDistance[ i ];
IndexMin = i ;
}
}
return IndexMin;
}
int main()
{
int NumberOfTestCase;
cin>>NumberOfTestCase;
for(int number = 0 ; number < NumberOfTestCase ; number++)
{
//structure of Graph
vector<int> GraphAdj[ 3 ];
int F , I ;
cin >> F >> I ;
if( I == 1 )
{
cout<<"1"<<endl;
}
else
{
graph g(I+1);
//
for( int i = 0 ; i < F ; i++ )
{
int FirStation ;
cin>>FirStation;
g.addEdge(FirStation,I+1,0);
g.addEdge(I+1,FirStation,0);
}
string Input ;
cin.ignore(10, '\n' );
getline(cin,Input,'\n');
while( !Input.empty())
{
istringstream iss(Input);
int v1 , v2 , Edge;
iss>>v1;
iss>>v2;
iss>>Edge;
g.addEdge(v1,v2,Edge);
g.addEdge(v2,v1,Edge);
getline(cin,Input,'\n');
}
g.UpdateLocate();
cout<<findIntersection(g,I , F ) <<endl ;
if( number != NumberOfTestCase - 1 )
cout<<endl;
}
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10278 - Fire Station
Input:
AC output:
Code: Select all
2
1 1
1
1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10
Code: Select all
1
4
Check input and AC output for thousands of problems on uDebug!
Re: 10278 - Fire Station
Nice article of yours about "10278 - Fire Station". I like your well post. How can I help you ? I think your topic about road distance between cities with fire station. Thanks for your fine sharing.
-
- New poster
- Posts: 20
- Joined: Fri Aug 30, 2013 5:42 am
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10278 - Fire Station
Input:AC output 10
Code: Select all
1
1 15
13
1 2 92
1 3 24
1 7 56
1 8 38
1 11 23
1 12 66
1 13 68
1 14 17
2 3 47
2 4 58
2 5 11
2 6 73
2 7 66
2 10 24
2 11 37
2 12 84
2 13 49
3 5 58
3 6 29
3 9 42
3 10 65
3 11 80
3 12 60
3 13 37
3 15 57
4 6 74
4 7 45
4 8 30
4 11 62
5 9 57
5 13 95
5 15 55
6 7 5
6 9 61
6 10 9
6 11 56
6 12 15
6 13 56
6 14 84
6 15 78
7 9 25
7 11 81
7 12 49
8 9 19
8 10 4
8 11 60
8 12 8
8 13 51
8 14 17
9 10 25
9 11 72
9 12 36
9 13 85
9 15 80
10 12 24
10 14 24
10 15 62
11 12 85
11 13 15
11 14 33
11 15 23
12 14 42
12 15 46
13 15 26
Check input and AC output for thousands of problems on uDebug!
Re: 10278 - Fire Station
Is there anyway to solve the problem by running dijkstra's algo only once instead of placing firestation at every possible intersection?
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10278 - Fire Station
I got AC in 0.022 seconds by running Dijkstra's Algorithm from every intersection that doesn't already have a fire station.
I got AC in 1.356 seconds using the Floyd-Warshall Algorithm.
This line from the problem statement is not met in the judge's input: "there will exist a route between any pair of intersections."
I got AC in 1.356 seconds using the Floyd-Warshall Algorithm.
This line from the problem statement is not met in the judge's input: "there will exist a route between any pair of intersections."
Check input and AC output for thousands of problems on uDebug!