pku1797.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#define SIZE 1000

int path[SIZE][SIZE];
int we[SIZE], s[SIZE];

int Min(int a, int b)
{
	return (a < b) ? a : b;
}

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

int main()
{
	int t, ti, n, e, i, j, x, y, w, min, u, max;

//	freopen("in.dat", "r", stdin);
	scanf("%d", &t);

	for (ti = 1; ti <= t; ti++)
	{
		scanf("%d%d", &n, &e);

		
		
		
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < n; j++)
			{
				path[i][j] = 0;
			}
			s[i] = 0;
		}

		for (i = 0; i < e; i++)
		{
			scanf("%d%d%d", &x, &y, &w);
			path[x - 1][y - 1] = w;
			path[y - 1][x - 1] = w;
		}
		
		for (i = 1; i < n; i++)
		{
			we[i] = path[i][0];
		}
		
		s[0] = 1;
		
		for (i = 1; i < n; i++)
		{
			max = 0;
			u = -1;

			for (j = 0; j < n; j++)
			{
				if (s[j] == 0)
				{
					if (we[j] > max)
					{
						max = we[j];
						u = j;
					}
				}
			}

			s[u] = 1;
			
			for (j = 0; j < n; j++)
			{
				if (s[j] == 0 && path[u][j] != 0)
				{
					if (we[j] < Min(path[u][j], we[u]))
					{
						we[j] = Min(path[u][j], we[u]);
					}
				}
			}
		}

		printf("Scenario #%d:\n%d\n\n", ti, we[n - 1]);
	}
	return 0;
}