OJ Board

The Online Judge board
https://onlinejudge.org/board/

10278 - Fire Station

https://onlinejudge.org/board/viewtopic.php?t=14329

Page 4 of 4

Re: 10278 - Fire Station

Posted: Fri Oct 24, 2008 2:34 am
by stcheung
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

Re: 10278 - Fire Station

Posted: Sun May 03, 2009 7:31 pm
by ymgve
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
Isn't that wrong? The answer should be 2, since that location doesn't have any station already.

Re: 10278 - Fire Station

Posted: Sun Sep 06, 2009 4:33 pm
by mak(cse_DU)
Actually the tricky part is below.
input:

Code: Select all

1
2 2
1
2
1 2 10
output will be:

Code: Select all

1
No intersection without fire station. so Answer is 1.

Re: 10278 - Fire Station

Posted: Fri Dec 17, 2010 6:27 am
by Stargazer71
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:

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
The correct output is:

Code: Select all

1

2

3

4

5

6

7

8
Hope this helps someone, and best of luck!

Problem in reading input

Posted: Sat Jun 11, 2011 5:24 pm
by Chocolate
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 Ac All the Samples that you gave, But WA,WHY!!HELP!!!

Posted: Tue Aug 09, 2011 5:21 am
by zslwyuan
#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;
}

Re: 10278 - Fire Station

Posted: Mon Apr 30, 2012 1:01 am
by djsohrab2007
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:

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
The correct output is:

Code: Select all

1

2

3

4

5

6

7

8
Hope this helps someone, and best of luck!

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
Because question is minimize the maximum distance from any intersection to its nearest fire station.
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 ;
}
Thank you,

Re: 10278 - Fire Station

Posted: Fri May 04, 2012 8:30 pm
by brianfry713
For this input, there is already a fire station at 2:

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

Re: 10278 - Fire Station

Posted: Thu May 10, 2012 11:30 am
by djsohrab2007
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.

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;
}

Re: 10278 - Fire Station

Posted: Fri May 11, 2012 4:02 am
by brianfry713
Input:

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
AC output:

Code: Select all

1

4

Re: 10278 - Fire Station

Posted: Thu May 24, 2012 8:56 pm
by Ryan
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.

10278 - Fire Station

Posted: Wed Aug 06, 2014 10:41 am
by cyberdragon
Why WA?
http://ideone.com/CFplTS

Re: 10278 - Fire Station

Posted: Wed Aug 06, 2014 9:22 pm
by brianfry713
Input:

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
AC output 10

Re: 10278 - Fire Station

Posted: Sun Sep 21, 2014 12:21 pm
by Farsan
Is there anyway to solve the problem by running dijkstra's algo only once instead of placing firestation at every possible intersection?

Re: 10278 - Fire Station

Posted: Mon Sep 22, 2014 8:57 pm
by brianfry713
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."
All times are UTC+02:00
Page 4 of 4

Powered by phpBB® Forum Software © phpBB Limited