#include <iostream>
using namespace std;

const int SIZE = 1001;
const int INFINITE = 10000000;
int graph[SIZE][SIZE], n, m, vertex[SIZE];
bool visited[SIZE];

class HeapNode
{
public:
	int key;
	int num;
	HeapNode ()
	{
	}
	HeapNode ( int m, int n )
	{
		key = m;
		num = n;
	}
};

class MyHeap
{
private:
	HeapNode nodes[SIZE];
	int size;
private:
	void swap ( int i, int j )
	{
		HeapNode t = nodes[i];
		nodes[i] = nodes[j];
		nodes[j] = t;
	}

	int parent ( int node )
	{
		return node / 2;
	}

	int left ( int node )
	{
		return node * 2;
	}

	int right ( int node )
	{
		return node * 2 + 1; 
	}
public:
	void heapfy ( int );
	bool push ( HeapNode );
	HeapNode* pop ();

	bool isempty ()
	{
		return size < 1;
	}

	void setsize ( int size )
	{
		this->size = size;
	}
};

bool MyHeap::push ( HeapNode value )
{
	if ( size == SIZE - 1 )
		return false;

	nodes[++size] = value;
	int i = size;

	while ( i > 1 && nodes[parent( i )].key < nodes[i].key )
	{
		swap ( i, parent ( i ) );
		i = parent ( i );
	}

	return true;
}

HeapNode* MyHeap::pop ()
{
	if ( size < 1 )
		return NULL;
	HeapNode *min = new HeapNode ( nodes[1].key, nodes[1].num );

	nodes[1] = nodes[size];
	size--;
	heapfy ( 1 );

	return min;
}

void MyHeap::heapfy ( int p )
{
	int l = left ( p ), r = right ( p ), greater;

	if ( l <= size && nodes[l].key > nodes[p].key )
		greater = l;
	else
		greater = p;

	if ( r <= size && nodes[r].key > nodes[greater].key )
		greater = r;
	
	if ( greater != p )
	{
		swap ( greater, p );
		heapfy ( greater );
	}
}

int min ( int a, int b )
{
	return a > b ? b : a; 
}

MyHeap heap;

int main ()
{
	int s, i, j, k;
	for ( k = 1, scanf ( "%d", &s ); k <= s; k++ )
	{
		printf ( "Scenario #%d:\n", k );
		scanf ( "%d%d", &n, &m );

		for ( i = 1; i <= n; i++ )
		{
			vertex[i] = -1;
			for ( j = 1; j <= n; j++ )
				graph[i][j] = INFINITE;
		}

		for ( j = 0; j < m; j++ )
		{
			int from, to, weight;
			scanf ( "%d%d%d", &from, &to, &weight );
			graph[from][to] = graph[to][from] = weight;
		}

		if ( n == 1 )
		{
			printf ( "0\n\n" );
			continue;
		}

		memset ( visited, false, sizeof ( visited ) );
		heap.setsize ( 0 );
		HeapNode *node = new HeapNode ( INFINITE, 1 );
        heap.push ( *node );
		delete node;

        j = 0;
		while ( j < n && !heap.isempty () )
		{
			HeapNode *node = heap.pop ();
            j++;
			visited[node->num] = true;

			for ( i = 1; i <= n; i++ )
				if ( graph[node->num][i] < INFINITE && !visited[i] )
				{
					int value = min ( graph[node->num][i], node->key );

					if ( vertex[i] < value )
					{
						vertex[i] = value;

						HeapNode *topush = new HeapNode ( vertex[i], i );
				
						heap.push ( *topush );
						delete topush;
					}
				}
			delete node;
		}

		j = vertex[2];
		for ( i = 3; i <= n; i++ )
			if ( j > vertex[i] )
				j = vertex[i];
		printf ( "%d\n\n", j );
	}

	return 0;
}

• 一段时间再写，这次用了STL，可是还是WA了。。。达人助我。。。 (1503) yogafrank 2008-12-08 22:37:27