pku2394.cpp

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

#include <stdio.h>
#define SIZE 501
#define TheMax 1000000

int main()
{
	int F, P, C, M;
	int path[SIZE][SIZE];
	int use[SIZE], dis[SIZE];
	int i, j, u, s, e, w, min, k;
	int cow[101];
	
//	freopen("in.dat", "r", stdin);
	while (scanf("%d %d %d %d", &F, &P, &C, &M) != -1)
	{
		for (i = 0; i < F; i++)
		{
			for (j = 0; j < F; j++)
			{
				path[i][j] = TheMax;
			}
			path[i][i] = 0;
		}

		for (i = 0; i < P; i++)
		{
			scanf("%d %d %d", &s, &e, &w);
			if (path[s - 1][e - 1] > w)
			{
				path[s - 1][e - 1] = w;
				path[e - 1][s - 1] = w;
			}
		}

		for (i = 0; i < F; i++)
		{
			dis[i] = path[i][0];
			use[i] = 0;
		}

		use[0] = 1;

		for (j = 0; j < F; j++)
		{
			min = TheMax;
			u = -1;
			for (i = 0; i < F; i++)
			{
				if (use[i] == 0)
				{
					if (dis[i] < min)
					{
						min = dis[i];
						u = i;
					}
				}
			}
			use[u] = 1;
			for (i = 0; i < F; i++)
			{
				if (use[i] == 0 && dis[i] > dis[u] + path[u][i])
				{
					dis[i] = dis[u] + path[u][i];
				}
			}
		}

		for (i = 1, k = 0; i <= C; i++)
		{
			scanf("%d", &j);
			if (dis[j - 1] <= M)
			{
				cow[k] = i;
				k++;
			}
		}
		printf("%d\n", k);
		for (i = 0; i < k; i++)
		{
			printf("%d\n", cow[i]);
		}
	}
	
	return 0;
}