gondolkozz egy kicsit. veszed azt a par pontot amit erinteni kell, kiszamolod a koztuk levo ut koltseget, osszekotod a pontokat es rairod a kiszamolt koltsegeket az elekre - es ott van az utazo ugynok problema. egy kulonbseggel, hogy nem kell jelen esetben visszaerni a kezdopontba - de ez nem lenyeges, mert ha igy megoldod X ido alatt, akkor vegigprobalgatva minden kezdo es vegponttal megoldhatod X*n^2 ido alatt az utazo ugynok problemat, amibol kovetkezik, hogy X sem fog menni polinomialis ido alatt.
szerk120: persze senki sem mondta, hogy polinomialis ido alatt kell (vagy lehet) megoldani, es en meg nem mondom azt, hogy dijkstra-val vagy akarmi hasonlo algoritmus felhasznalasaval ne lehetne megoldani. csak annyit mondok, hogy ez egy jol ismert problema.
- Use the Source Luke ! -