pku2263.cpp

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

#include <stdio.h>
#include <string.h>
#define size 210
char Name[size][20];
int load[size][size];
int N, R;
int cnt;

int GetID(char *s)
{
	int i;
	for (i = 0; i < cnt; i++)
	{
		if (!strcmp(s, Name[i]))
		{
			return i;
		}
	}
	strcpy(Name[cnt], s);
	cnt++;
	return cnt - 1;
}

int MIN(int x, int y)
{
	return x < y ? x : y;
}

int DIJ(int s, int e)
{
	int used[size];
	int maxd[size];
	int i, j, k, u, max;

	for (i = 0; i < N; i++)
	{
		maxd[i] = load[i][s];
		used[i] = 0;
	}
	maxd[s] = 20000;
	used[s] = 1;
	while (1)
	{
		max = 0;
		u = -1;
		for (i = 0; i < N; i++)
		{
			if (used[i] == 0 && maxd[i] > max)
			{
				max = maxd[i];
				u = i;
			}
		}
		if (u == -1)
		{
			break;
		}
		used[u] = 1;
		for (i = 0; i < N; i++)
		{
			if (!used[i] && maxd[i] < MIN(maxd[u], load[u][i]))
			{
				maxd[i] = MIN(maxd[u], load[u][i]);
			}
		}
	}
	return maxd[e];
}

int main()
{
	int i, d, id1, id2, T;
	char nm1[20], nm2[20];
	
	T = 0;
	while (scanf("%d %d", &N, &R) != -1 && (N + R))
	{
		memset(load, 0, sizeof(load));
		cnt = 0;
		for (i = 0; i < R; i++)
		{
			scanf("%s %s %d", nm1, nm2, &d);
			id1 = GetID(nm1);
			id2 = GetID(nm2);
			if (load[id1][id2] < d)
			{
				load[id1][id2] = load[id2][id1] = d;
			}
		}
		scanf("%s %s", nm1, nm2);
		id1 = GetID(nm1);
		id2 = GetID(nm2);
		printf("Scenario #%d\n%d tons\n\n", ++T, DIJ(id1, id2));
	}
	return 0;
}