Új hozzászólás Aktív témák

• #1752 Sportman csendes tag

  Új Válasz 2007-03-08 08:53:36 #1752

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Sportman

  csendes tag

  Sziasztok, egy kis segitség kéne a következő feladat megoldásához:
  
  Egy titkosügynöknek van egy térképe, amelyen N katonai objektum van kijelölve. Kezdetben az ügynök az 1-essel jelölt saját objektumánál található és az N-el jelölt ellenséges objektumhoz kell eljutnia. Célja eléréséhez a létező utakat használja, mindenik út két különböző objektumot köt össze.
  Mivel küldetése titkos csak éjszaka mozoghat, ezért zseblámpára van szüksége. Erre a célre K tipusu lámpát használhat - a W tipusu lámpa (1<=W<=K) elemei W wattosok, a W watt elhasználása után a lámpa többé nem világít, szerencséjére egyes baráti katonai objektumukon teljesen ujratöltheti az elemeit, vigyáznia kell, hogy mielött két objektumot összekötő úton elindulna az elemeiben levő wattok száma legyen nagyobb vagy egyenlő, mint az illető útszakasz megtételéhez szükséges wattok száma.
  Ismerve az objektumok közti utakat és mindegyik út esetén a bejáráshoz szükséges időt és a zseblámpa által elhasznált wattok számát határozzátok meg azt a legkisebb számmal jellemzett lámpa tipust amely lehetővé teszi azt, hogy a célba éréséhez szükséges idő minimális legyen (a legkisebb fogyasztásu lámpa érdekel mindazon lámpa tipusok közül, amelyek minimális idő alatti célbajutást tesznek lehetővé).
  
  Bemenő adatok:
  A lampa.in szövegállomány első sorába az N és K egész számok vannak egy szóközzel elválasztva, a következő sorban N db egész szám található a {0,1} halmazból, ha az i-ik szám 1, akkor az i-ik objektum barátságos, vagyis feltöltheti az elemeket ha ehhez az objektumhoz ér, ha pedig 0, akkor az ügynök nem töltheti fel az elemeit ezen a helyen. Az első szám a sorban 1, az utolsó pedig 0.
  Az állomány harmadik sorában található M, az utak száma. A következő sor mindegyike 4 szóközzel elválasztott egész számot tartalmaz a,b,T,W. Az a és b az objektumok közt kétirányu út található, melynek megtételéhez T időra van szükség és W wattot használ el.
  
  Kimeneti adatok:
  A lampa.out szövegállományba irjunk két egész számot szóközzel elválasztva: Tmin és Wmin
  
  Példa:
  lámpa.in
  7 10
  1 0 1 0 0 0 0
  7
  1 2 10 3
  1 4 5 5
  2 3 10 3
  4 3 15 1
  3 6 4 2
  6 5 2 2
  5 7 1 0
  lampa.out
  27 6

Új hozzászólás Aktív témák