2834.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:2834  User Id:fzk 
Memory:300K  Time:0MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> e[10010], dest;
int n, m;
vector< pair<int,int> > jon, cely;

void input( ) {
	int a, b;

	scanf( "%d", &n );
	scanf( "%d", &m );

	while( m-- ) {
		scanf( "%d%d", &a, &b );
		e[a].push_back( b );
		e[b].push_back( a );
	}

	scanf( "%d", &m );
	while( m-- ) {
		scanf( "%d", &a );
		dest.push_back( a );
	}

	scanf( "%d", &m );
	while( m-- ) {
		scanf( "%d%d", &a, &b );
		cely.push_back( make_pair( a, b ) );
	}

}
int dis[10010];

void BFS( ) {
	int i, q[10010], qh = 0, qe = 0, s;

	memset( dis, -1, sizeof dis );

	dis[0] = 0;
	q[qh++] = 0;

	while( qe < qh ) {
		s = q[qe++];
		for( i=0; i<e[s].size(); i++ ) {
			if( dis[e[s][i]] < 0 ) {
				dis[e[s][i]] = dis[s] + 5;
				q[qh++] = e[s][i];
			}
		}
	}
}

void doit( ) {
	int i, j, sum = 0;
	
	BFS( );
	
	jon.push_back( make_pair( 0, 0 ) );
	
	for( i=0; i<dest.size(); i++ ) {
		if( dis[ dest[i] ] > 0 ) {
			jon.push_back( make_pair( dest[i], sum+=dis[dest[i]] ) );
			jon.push_back( make_pair( 0, sum+=dis[dest[i]] ) );
		}
		else {
			jon.push_back( make_pair( dest[i], 1<<31 ) );
			break;
		}
	}

	i=0, j=0;
	for( j=0; j<cely.size(); j++ ) {
		while( i<jon.size() && jon[i].second < cely[j].second )
			i++;
		if( i<jon.size() && jon[i] == cely[j] )
			break;
		if( i == jon.size() && cely[j].first == 0 && cely[j].second >= jon[i-1].second )
			break;
	}

	if( j < cely.size() )
		printf( "%d\n", cely[j].second );
	else
		printf( "Being expected..\n" );

}

int main( ) {
	input( );
	doit( );
	return 0;
}