#include #include #define N 10005 #define M 100005 int hrana[M][3]; int deg[N]; int color[N]; int index[N+1]; int vrchol[N+1]; /* hrany susediace s danym vrcholom*/ int hrany[M*2]; int vahy[M*2]; int n, m, z, max; int budovy[N]; int zakladne[N]; int sucty[N]; int pocet; /* dfs */ void DFS(int v) { int i; int akt_hrana = 0; int akt_vaha = 0; color[v] = 1; /*printf("**** ahoj vrchol: %d\n", v+1);*/ for(i = index[v]; i < index[v+1]; i++) { akt_hrana = hrany[i]; akt_vaha = vahy[i]; /* printf("navsteva hrana %d-%d (dlzka: %d)\n", v+1, akt_hrana+1, akt_vaha); */ if(color[akt_hrana] == 0) { sucty[akt_hrana] = sucty[v]+ akt_vaha; /* znicime mesto */ if( sucty[akt_hrana] < max) { if(budovy[akt_hrana] == 1) pocet = pocet -1; budovy[akt_hrana] = 0; } DFS(akt_hrana); } } } int main(void) { int v1, v2, w; int x, y; int tmp; int i, a, teror; char c; scanf("%d %d %d %d", &n, &m, &z, &max); while (n != 0) { pocet = n; for(i=0; i < n; i++) { deg[i] = 0; budovy[i] = 1; zakladne[i] = 0; } /* hrany */ for(i=0; i < m; i++) { scanf("%d %d %d", &v1, &v2, &w); hrana[i][0] = v1-1; hrana[i][1] = v2-1; hrana[i][2] = w; deg[v1-1]++; deg[v2-1]++; } tmp=0; /* indexy */ for(i=0; i < n+1; i++) { index[i] = tmp; vrchol[i] = index[i]; tmp = tmp + deg[i]; } /* zapiseme si body */ for(i=0; i < m; i++) { x = hrana[i][0]; y = hrana[i][1]; hrany[vrchol[y]] = x; hrany[vrchol[x]] = y; vahy[vrchol[y]++] = hrana[i][2]; vahy[vrchol[x]++] = hrana[i][2]; } hrany[2*m] = -1; /* for(i=0; i < n+1; i++) printf("index[%d] = %d\n", i, index[i]); for(i=0; i < 2*m+1; i++) printf("hrany[%d] = %d, vaha: %d\n", i, hrany[i], vahy[i]); */ for (a=0; a < z; a++) { scanf("%d", &teror); /* ideme na DFS */ for(i=0; i < n; i++) { sucty[i] = 0; color[i] = 0; } zakladne[teror-1] = 1; sucty[teror-1] = 0; if(budovy[teror-1] == 1) { pocet--; budovy[teror-1] = 0; } DFS(teror-1); /* for(i=0; i < n; i++) printf("budovy[%d] = %d\n", i+1, budovy[i]); for(i=0; i < n; i++) printf("sucty[%d] = %d\n", i+1, sucty[i]); */ printf("%d\n", pocet); } c = getchar(); c = getchar(); scanf("%d %d %d %d", &n, &m, &z, &max); printf("\n"); } return 0; }