#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)
			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;
}

• Re:为什么会这样？？？？？？ (1133) others_code 2006-09-26 15:23:07
  • 恍然大悟，谢谢！ (1237) madongtest 2006-09-26 23:30:10