Source

Problem Id:2831  User Id:sail6 
Memory:104K  Time:0MS
Language:C++  Result:Wrong Answer

Source 

#include<iostream.h>


struct edge
{
	int  fromvex ;
	int  endvex ;
	int  weight ;
} ;

struct Node
{
	
	int  fromvex ;
	int  endvex ;
	int  weight ;
} ;



//const  int  maxEdgeNum = 1010;
Node node [3100] ;////////// 50 
typedef   edge edgeset [3100] ;/////////////////50

///const  int  MaxvertexNum = 1010 ;

typedef int  adjmatrix [3100] [ 3100] ;///////5050 
adjmatrix  GA  ;
adjmatrix  GA1  ;

const int  Maxvalue = 1000010 ;


int Prim ( adjmatrix  GA , edgeset  &CT , int  n )
{
	int i , j , k , min , t , m , w ;
	for(i = 0 ; i < n - 1 ; i ++ )
	{
		CT [ i ] . fromvex = 0 ;
		CT [ i ] . endvex = i + 1 ;
		CT [ i ] . weight = GA [ 0 ] [ i + 1 ]  ;
	}
	for ( k = 1 ; k < n ; k ++ )
	{
		min =  Maxvalue ;
		m  =   k-1;
		for( j = k - 1 ; j < n - 1 ; j ++ )
		{
			if ( CT [j] . weight < min)
			{
				min = CT [j] . weight ;
				m = j ;
				
			}
		}
		edge  temp = CT [ k - 1 ] ;
		CT [ k - 1 ] = CT [ m ] ;
		CT [ m ] = temp ;
		j = CT [ k - 1 ] . endvex ;
		for ( i = k ; i < n -1 ; i ++ )
		{
			t = CT [i] . endvex ;
			w = GA [ j ] [ t ];
			if ( w < CT [ i ] .weight )
			{
				CT [ i ] .weight = w ;
				CT [ i ] .fromvex = j ;
			}
			
		}
		
	}
	
	
	return 0; 
}

edgeset  CT1  ;


int main ( )
{
	int  N , M , Q ;
	cin >> N >> M >> Q ;
	int  i , j ;
	int  a , b , c ;
	
	
	edgeset  CT ; 
	
	for ( i = 0 ; i < N ; i ++ )
	{
		for ( j = 0 ; j < N ; j ++ )
		{
			GA [ i ] [ j ] = Maxvalue ;
		}
		
	}
	
	for ( i = 0 ; i < M ; i ++ )
	{
		cin >> a >> b >> c ;
		node [ i ] . fromvex = a - 1 ;
		node [ i ] .endvex = b - 1 ;
		node [ i ]. weight = c ;
		//	cout << i << ' ' << node [ i ] . fromvex << ' ' << node [ i ] .endvex << ' ' << 	node [ i ]. weight << endl << endl ;
		
		if ( c < 	GA [ a - 1 ] [ b - 1 ] )
		{
			GA [ a - 1 ] [ b - 1 ] = c ;
			GA [ b - 1 ] [ a - 1] = c ;
		}
		
	}
	/*	for ( i = 0 ; i < N ; i ++ )
	{
	for ( j = 0 ; j < N ; j ++ )
	{
	cout << GA [ i ] [ j ]<<' ';
	}
	cout<<endl;
}*/
	Prim (   GA ,   CT , N ) ;
//	int weight1 = 0 , weight2 = 0 ;

	int max=0;
	for( i=0 ;i<N-1;i++)
	{
		if( CT[i].weight>max)
		{
			max=CT[i].weight;
		}
	}
	
	int  k , w ;
	//edgeset  CT1 ; 
	
	for ( i = 0 ; i < Q ; i ++ )
	{
	/*	for ( int ii = 0 ; ii < N ; ii ++ )
	{
	for ( j = 0 ; j < N ; j ++ )
	{
				GA1 [ ii ] [ j ] =  GA [ ii ] [ j ] ;
				}
				//cout<<endl;
				}
				
				  cin >> k >> w ;
				  a = node [ k - 1 ] . fromvex ;
				  b = node [ k - 1 ] . endvex ;
				  
					GA1 [ a  ] [ b  ] = GA1 [ b ] [ a ] = w ;
					
					  /*	for (  ii = 0 ; ii < N ; ii ++ )
					  {
					  for ( j = 0 ; j < N ; j ++ )
					  {
					  cout << GA1 [ ii ] [ j ]<<' ';
					  }
					  cout<<endl;
					  }
					  cout<<endl<<endl;
					  Prim (   GA1 ,  CT1 , N ) ;
					  weight2=0;
					  for(j=0;j<N-1;j++)
					  {
					  weight2+=CT1[j].weight;
					  }
					  
						int  flag = 0 ;
						for ( j = 0 ; j < N - 1 ; j ++ )
						{
						if ( a == CT1 [ j ].fromvex && b == CT1 [j].endvex && w == CT1 [ j ].weight &&weight1>=weight2||b == CT1 [ j ].fromvex && a == CT1 [j].endvex && w == CT1 [ j ].weight &&weight1>=weight2)
						{
						flag=1;
						break;
						}
	}*/
		cin>>k>>w;
		a = node [ k - 1 ] . fromvex ;
		b = node [ k - 1 ] . endvex ;
		int J;
		int flag=0;
		for(j=0;j<N-1;j++)
		{
			if((a==CT[j].fromvex&&b==CT[j].endvex)||(b==CT[j].fromvex&&a==CT[j].endvex))
			{
				flag=1;
				J=j;
				
				break;
				
			}
		}
		
		if (flag==0 && w<=max )///////////////flag==1
		{
			cout << "Yes" << endl ;
		}
		else
			
		{
			if(flag==1&&w<=CT[J].weight)
			{
				
				
					cout << "Yes" << endl ;
				
			}
			else
			{
				cout << "No" << endl ;
			}
		}
	}
	return 0;	
	
}