#include #include int main(int argc, char **argv) { int cities, edges, bases, mindist; int city1, city2, dist, base; int i, j, k, dd, available; while(scanf("%d %d %d %d", &cities, &edges, &bases, &mindist) == 4) { if(cities == 0 && edges == 0 && bases == 0 && mindist == 0) break; available = cities; int* matrix = (int*) malloc(sizeof(int)*cities*cities); int* eliminated = (int*) malloc(sizeof(int)*cities); for(i = 0; i < cities; i++) { eliminated[i] = 0; for(j = 0; j < cities; j++) matrix[i*cities+j] = i == j ? 0 : 100000; } for(i = 0; i < edges; i++) { scanf("%d %d %d", &city1, &city2, &dist); city1--; city2--; matrix[city1*cities+city2] = dist; matrix[city2*cities+city1] = dist; } for(i = 0; i < cities; i++) { for(j = 0; j < cities; j++) { for(k = 0; k < cities; k++) { dd = matrix[j*cities+i] + matrix[i*cities+k]; if(dd < matrix[j*cities+k]) { matrix[j*cities+k] = dd; } } } } for(i = 0; i < bases; i++) { scanf("%d", &base); base--; for(j = 0; j < cities; j++) { // printf("%d:%d\n", j, matrix[j][base]); if(matrix[j*cities+base] < mindist && eliminated[j] == 0) { // printf("eliminated %d:%d\n", j, matrix[j][base]); eliminated[j] = 1; available--; } } printf("%d\n", available); } printf("\n"); free(matrix); free(eliminated); } return 0; }