#include #include #include using namespace std; struct Road{ Road(int to, int len){ To = to; Lenght = len; } int To; int Lenght; }; struct Town{ Town(void){ base = false; isSafe = true; } bool base; bool isSafe; vector Roads; }; vector Towns; void Walk(Town *town, int lenght, int minVzdalenost){ // if (!town->isSafe) return; // printf("velikost cest %d",town->Roads.size()); // if (lenght < minVzdalenost){ town->isSafe = false; // if (town->base && lenght == 0) return; for (unsigned int i=0; i < town->Roads.size();i++){ // printf("jdu do %d",town->Roads[i].To); int newLength = lenght+town->Roads[i].Lenght; if (newLength < minVzdalenost){ Walk(Towns[town->Roads[i].To], newLength, minVzdalenost); } } /*} else { return; }*/ } int main(){ unsigned int pocetMest, pocetCest, pocetBazi, minVzdalenost; unsigned int from, to, delka, safeCount; while (1){ scanf("%d %d %d %d", &pocetMest, &pocetCest, &pocetBazi, &minVzdalenost); Towns.push_back(new Town()); for (unsigned int i=0; iRoads.push_back(Road(to, delka)); Towns[to]->Roads.push_back(Road(from, delka)); } unsigned int base; for(unsigned int i=0; ibase = true; Walk(Towns[base],0,minVzdalenost); safeCount = 0; for ( unsigned int i=1; i< Towns.size();i++){ if (Towns[i]->isSafe){ safeCount ++; } } printf("%d\n", safeCount); } printf("\n"); Towns.clear(); } return 0; }