#include #include using namespace std; struct Edge { int source; int target; int weight; }; struct Node { bool safe; int dist; list edges; }; Node * nodes; int towns, roads, bases, safeDist; int safeBases; list queue; void initPaths() { for (int i = 1; i < towns+1; ++i) { nodes[i].dist = 101; } } void relax(int source, int target, int weight) { if (nodes[target].dist > nodes[source].dist + weight) { int dist = nodes[target].dist; nodes[target].dist = nodes[source].dist + weight; if (dist >= safeDist && nodes[target].dist < safeDist && nodes[target].safe) { --safeBases; nodes[target].safe = false; } if (dist == 101) queue.push_back(target); } } void dijkstra(int base) { initPaths(); nodes[base].dist = 0; if (nodes[base].safe) { --safeBases; nodes[base].safe=false; } queue.push_back(base); while(!queue.empty()) { list::iterator min; int minDist = 101; for(list::iterator it = queue.begin(); it != queue.end(); ++it) if (minDist>nodes[*it].dist) { minDist = nodes[*it].dist; min=it; } queue.erase(min); int node = *min; list::iterator end = nodes[node].edges.end(); for(list::iterator it = nodes[node].edges.begin(); it != end; ++it) { if(node == (*it)->source) relax((*it)->source,(*it)->target, (*it)->weight); else relax((*it)->target,(*it)->source, (*it)->weight); } } } int main (){ scanf("%d %d %d %d", &towns, &roads, &bases, &safeDist); safeBases = towns; nodes = new Node[towns+1]; for(int i = 1; i < towns+1; ++i) nodes[i].safe=true; for (int i = 0; i < roads; ++i) { Edge * edge = new Edge(); scanf("%d %d %d", & edge->source, & edge->target, &edge->weight); nodes[edge->source].edges.push_back(edge); nodes[edge->target].edges.push_back(edge); } int base; for(int i = 0; i < bases; ++i){ scanf("%d", &base); dijkstra(base); printf("%d\n", safeBases); } return 0; }