<prompt> Kuna mti yaani, grafu iliyounganishwa, isiyoelekezwa isiyo na mizunguko mtandao wa nchi wa muundo unaojumuisha n miji iliyo na nambari kutoka 0 hadi n - 1 na barabara n - 1 haswa. Mji mkuu ni mji 0. Umepewa safu kamili ya 2D barabara ambapo barabarai ai, bi inaashiria kuwa kuna barabara ya njia mbili inayounganisha miji ai na bi.Kuna mkutano wa wawakilishi wa kila jiji. Mkutano huo uko katika mji mkuu.Kuna gari katika kila mji. Unapewa viti kamili vinavyoonyesha idadi ya viti katika kila gari.Mwakilishi anaweza kutumia gari katika jiji lake kusafiri au kubadilisha gari na kupanda na mwakilishi mwingine. Gharama ya kusafiri kati ya miji miwili ni lita moja ya mafuta.Rejesha _idadi ya chini kabisa ya lita za mafuta kufikia mji mkuu_.Mfano wa 1:Ingizo: barabara 0,1,0,2,0,3, viti 5Pato: 3Maelezo:- Mwakilishi1 huenda moja kwa moja kwa mji mkuu na lita 1 ya mafuta.- Mwakilishi2 huenda moja kwa moja kwa mji mkuu na lita 1 ya mafuta.- Mwakilishi3 huenda moja kwa moja kwa mji mkuu na lita 1 ya mafuta.Inagharimu lita 3 za mafuta kwa kiwango cha chini.Inaweza kuthibitishwa kuwa 3 ni idadi ya chini ya lita za mafuta zinazohitajika.Mfano wa 2:Ingizo: barabara 3,1,3,2,1,0,0,4,0,5, 4,6, viti 2Pato: 7Maelezo:- Mwakilishi2 huenda moja kwa moja kwa jiji la 3 na lita 1 ya mafuta.- Mwakilishi2 na mwakilishi3 huenda pamoja kwa jiji 1 na lita 1 ya mafuta.- Mwakilishi2 na mwakilishi3 kwenda pamoja hadi mji mkuu na lita 1 ya mafuta.- Mwakilishi1 huenda moja kwa moja kwa mji mkuu na lita 1 ya mafuta.- Mwakilishi5 huenda moja kwa moja kwa mji mkuu na lita 1 ya mafuta.- Mwakilishi6 huenda moja kwa moja kwa jiji la 4 na lita 1 ya mafuta.- Mwakilishi4 na mwakilishi6 kwenda pamoja katika mji mkuu na lita 1 ya mafuta.Inagharimu lita 7 za mafuta kwa kiwango cha chini.Inaweza kuthibitishwa kuwa 7 ni idadi ya chini ya lita za mafuta zinazohitajika.Mfano wa 3:Ingizo: barabara , viti 1Pato: 0Maelezo: Hakuna wawakilishi wanaohitaji kusafiri hadi mji mkuu.Vikwazo: 1 n 105 barabara.urefu n - 1 barabarai.urefu 2 0 ai, bi n ai ! bi barabara inawakilisha mti halali. 1 viti 105  <response>: kutoka kwa makusanyo leta defaultdict, dequedef min_fuelbarabara, viti: n lenzibarabara 1 grafu defaultdictorodha kwa barabara katika barabara: grafubarabara0.ambatanishabarabara1 grafubarabara1.ambatanishabarabara0 umbali -1 n q deque0 umbali 0 0 wakati q: mji q.popleft kwa jirani katika graphcity: ikiwa umbalijirani -1: umbalijirani umbalimji 1 q.ongeza jirani jumla_mafuta 0 kwa jiji katika masafa1, n: total_fuel umbalimji - 1 viti - 1 1 rudisha jumla_mafuta 