#include<stdio.h>
#define SIZE 505
#define MAX 10000000

int map[SIZE][SIZE],len[SIZE],n;
void dij(int s)
{
	int i,k;
	for(i = 1; i <= n; i++)
		len[i] = map[s][i];
	//map[s][s] = 0; <-----------  如果加上这句，就RE。为什么?(map[i][i]=0表示节点i已被访问)
	len[s] = 0;
	for(k = 1; k <= n; k++){
		int min = MAX,e;
		for(i = 1; i <= n; i++)
			if(map[i][i] && min > len[i]){
				e = i;
				min = len[i];
			}
		map[e][e] = 0;~~~~~\ 这两句，应该if在前。当min==MAX时e是没有被赋值的，会re. 之所以去掉map[s][s]=0不re,是因为去掉以后没有min=MAX的情况发生，因为这之前外层循环k<=n已经结束了。
		if(min == MAX)~~~~~/
			return;
		for(i = 1; i <= n; i++)
			if(map[i][i] && len[i] > len[e] + map[i][e])
				len[i] = len[e]+map[i][e];
	}
}
int main()
{
	int p,c,m,i,j,x,y,z,out[110];
	scanf("%d%d%d%d",&n,&p,&c,&m);
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++)
			map[i][j] = MAX;
	for(i = 0; i < p; i++){
		scanf("%d%d%d",&x,&y,&z);
		if(map[x][y] > z)
			map[x][y] = map[y][x] = z;
	}
	dij(1);
	y = 0;
	for(i = 1; i <= c; i++){
		scanf("%d",&x);
		if(len[x] <= m)
			out[y++] = i;
	}
	printf("%d\n",y);
	for(i = 0; i < y; i++)
		printf("%d\n",out[i]);
	return 0;
}

• 恍然大悟，谢谢！ (1237) madongtest 2006-09-26 23:30:10