Lennot

# -*- coding: cp1252 -*-

kaupungit, lentojenmaara = [int(x) for x in raw_input().split(" ")]
lennot0=[]
hmax=0
for i in range(lentojenmaara):
    lennot0.append([int(x) for x in raw_input().split(" ")]) #siirretään data taulukkoon
    hmax+=lennot0[i][2] #lento ei maksa enempää kuin kaikki hinnat yhteensä

#hmax = hmax/2 #KOKEILU
hmin = min(lennot0[2])

k=1 #täytyy lähteä 1:stä
lennot=[]
for i in range(kaupungit):
    lennot.append([])
for lento in lennot0:
    lennot[lento[0]-1].append(lento)


    
def valitseLento(a,b,reitti,h,hmax):
    for i in range(len(lennot[a-1])):
        dh = 0 #Lennon hinnan muuttuja
        if len(reitti)%2 != 0: #Jos maksullinen (=pariton lento)
            dh = lennot[a-1][i][2] #Lennon hinta      
        if h + dh <= hmax: #Kai ollaan vielä järkevissä summissa? --> matka jatkuu
            h += dh #Jos budjetti riittää, maksetaan
            a2 = lennot[a-1][i][1] #uudeksi lähtöpaikaksi määränpää, "lento" tapahtuu
            if a2!=b: #Jos lennon määränpää ei ole maali
                reitti.append(a2) #lisätään sijainti(ent. määränpää) reittilistaan
                try: hmax = valitseLento(a2,b,reitti,h,hmax)
                except: hmax=hmax #KOKEILU
                del reitti[-1] #palataan taaksepäin, poistetaan viimeinen sijainti
                h -= dh #Vähennetään maksettu matka (tai ei mitään)
            else: #Jos lennon määränpää on maali --> ratkaisu
                hmax = h #halvin hinta tähän asti
                #DEBUG reitti.append(a2)
                #D print reitti, hmax
                #D del reitti[-1]
                return hmax
                
            
    #Kun matkakohteita ei enää löydy, loop loppuu

    return hmax


#alaraja min(hinnat)

        
h=0
reitti=[1]
#DEBUG print hmax
hinta=valitseLento(1,kaupungit,reitti,h,hmax)
print hinta

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED