10278 - Fire Station

[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

[ymgve]

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.

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

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

[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

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

[djsohrab2007]

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,

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

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

[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

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

[cyberdragon]

Why WA?
http://ideone.com/CFplTS

[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

[Farsan]

Is there anyway to solve the problem by running dijkstra's algo only once instead of placing firestation at every possible intersection?

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