2607.txt

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

Source

Problem Id:2607  User Id:fzk 
Memory:76K  Time:576MS
Language:C++  Result:Accepted

Source 

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

struct edge {
	int to;
	int v;
	edge *next;
}pool[100000];

int pn = 0, n;
edge *e[500];

void add( int from, int to, int v ) {
	pool[pn].to = to;
	pool[pn].v = v;
	pool[pn].next = e[from];
	e[from] = pool+pn;
	pn++;
}

int fs_num[100], fn, ans = 100000, r;
int dis[500];

int doit( int k ) {
	int i;
	bool sign[500] = { false };

	memset( dis, 0x0f, sizeof dis );
	priority_queue< pair<int,int>, vector<pair<int,int> > > q;

	for( i=0; i<fn; i++ ) {
		dis[ fs_num[i]-1 ] = 0;
		q.push( make_pair( 0, fs_num[i]-1 ) );
	}

//	if( dis[k] == 0 )
//		return r;

	dis[k] = 0;
	q.push( make_pair( 0, k ) );

	for( i=0; i<n; i++ ) {
		
		do {
			k = q.top( ).second;
			q.pop( );
		}while( sign[k] );

		sign[k] = true;

		if( dis[k] > ans )
			return dis[k];

		for( edge *p = e[k]; p; p = p->next ) {
			if( dis[p->to] > dis[k] + p->v ) {
				dis[p->to] = dis[k] + p->v;
				q.push( make_pair( -dis[p->to], p->to ) );
			}
		}
	}

	return dis[k];
}

int id[500];
bool cmp( int a, int b ) {
	return dis[a] > dis[b];
}

int main( ) {
	int i, a, b, c, k, t;

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

	for( i=0; i<fn; i++ )
		scanf( "%d", fs_num+i );

	while( scanf( "%d%d%d", &a, &b, &c ) == 3 ) {
		add( a-1, b-1, c );
		add( b-1, a-1, c );
	}
	
	for( i=0; i<n; i++ )
		id[i] = i;

	r = doit( fs_num[0] );
	sort( id, id+n, cmp );

	for( i=0; i<n; i++ )
		if( (t=doit( i )) < ans )// || t == ans && i < k )
			k = i, ans = t;

	printf( "%d\n", k+1 );

	return 0;
}