Lennot

#!/usr/bin/env python3

# halvin lentoyhteys kaupungista 1 -> n, parilliset lennot ilmaisia

# esimerkkitapaus:
'''
Syöte:
4 6
1 2 5
2 3 8
2 1 4
3 1 6
3 4 1
4 2 3

Tuloste:
6
'''

from heapq import heappush, heappop
from collections import defaultdict

def main():
    n, m = map(int, input().split())
    reitit = defaultdict(dict)

    for i in range(m):
        a, b, c = map(int, input().split())
        a_reitit = reitit.setdefault(a, {})
        if b not in a_reitit or a_reitit[b] > c:
            a_reitit[b] = c

    seur = []
    heappush(seur, (0, 1, False))  # (yhthinta, sijainti, seuraava ilmainen)

    saav_parill = [None] * (n + 1)  # yhteishinnat, joilla tultu kohteeseen parillisella lennolla
    saav_parill[1] = 0
    saav_paritt = [None] * (n + 1)  # yhteishinnat, joilla tultu kohteeseen paritomalla lennolla

    maalissa = False

    while seur:
        yht, i, ilmainen = heappop(seur)
        for kohde, hinta in reitit[i].items():
            if ilmainen:
                if saav_parill[kohde] is None or saav_parill[kohde] > yht:
                    saav_parill[kohde] = yht
                    # lisätään jatkoon
                    heappush(seur, (yht, kohde, False))
            else:
                kohdehinta = yht + hinta
                if saav_paritt[kohde] is None or saav_paritt[kohde] > kohdehinta:
                    saav_paritt[kohde] = kohdehinta
                    # lisätään jatkoon
                    heappush(seur, (kohdehinta, kohde, True))

    print(min(x for x in (saav_parill[n], saav_paritt[n]) if x is not None))

if __name__ == '__main__':
    main()

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: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED