#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; distance = 9999999; } bool base; unsigned int distance; vector Roads; }; vector Towns; void Walk(Town *town, int lenght, int minVzdalenost){ town->distance = lenght; for (unsigned int i=0; i < town->Roads.size();i++){ Town *newTown = Towns[town->Roads[i].To]; int newLength = lenght + town->Roads[i].Lenght; printf("old Distance %d new Dist %d\n",newTown->distance , newLength); if (newTown->distance > newLength){ //&& !newTown->base){ newTown->distance = newLength; Walk(newTown, newLength, 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]->distance >= minVzdalenost){ safeCount ++; } } printf("%d\n", safeCount); } printf("\n"); for (unsigned int i=0; i<=pocetMest; i++){ delete Towns[i]; } Towns.clear(); } return 0; }