2395.txt

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

#include <iostream>
#include <fstream>
#include <memory>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

//#define _D_

const int MAXN = 2001;

int n, m;
int chart[MAXN][MAXN];
bool flag[MAXN];
vector<int> heap;

bool cp(const int l, const int r)
{
	return chart[l >> 16][l & 0xFFFF] > chart[r >> 16][r & 0xFFFF];
}

void solve()
{
	int i, a, b, c;
	memset(chart, 0, sizeof(int) * MAXN * MAXN);
	for (i = 0; i < m; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		if (a - b && (c < chart[a][b] || 0 == chart[a][b]))
		{
			chart[a][b] = c;
			chart[b][a] = c;
		}
	}
	memset(flag, false, sizeof(bool) * MAXN);
	flag[1] = true;
	for (i = 1; i <= n; i++)
	{
		if (chart[1][i])
		{
			heap.push_back((1 << 16) + i);
			push_heap(heap.begin(), heap.end(), cp);
		}
	}
	int mcost = 0;
	while (!heap.empty())
	{
		int a = heap.front() >> 16;
		int b = heap.front() & 0xFFFF;
		flag[b] = true;
		pop_heap(heap.begin(), heap.end(), cp);
		heap.pop_back();
		while (!heap.empty() && flag[heap.front() & 0xFFFF])
		{
			pop_heap(heap.begin(), heap.end(), cp);
			heap.pop_back();
		}
		for (i = 1; i <= n; i++)
		{
			if (chart[b][i] && !flag[i])
			{
				heap.push_back((b << 16) + i);
				push_heap(heap.begin(), heap.end(), cp);
			}
		}
		if (chart[a][b] > mcost)
			mcost = chart[a][b];
	}
	printf("%d\n", mcost);
}

int main()
{
	scanf("%d%d", &n, &m);
	solve();
	return 0;
}