32152023-02-22 17:07:3512BotiMúzeumi őrökpython3Időlimit túllépés 28/40680ms31092 KiB
import heapq
from bisect import bisect

n, e, u = map(int, input().split())
os = [list(map(int, input().split())) + [idx] for idx in range(n)]
os.sort()
done = [False] * n
parent = [-1] * n

heap = [(cost, end, idx) for idx, (start, end, cost, _) in enumerate(os) if start == e]
heapq.heapify(heap)

while len(heap) > 0:
    # print(heap)
    # print(parent)
    cost, end, idx = heapq.heappop(heap)
    if done[idx]:
        continue
    done[idx] = True
    if end >= u:
        print(cost)
        l = []
        while idx != -1:
            l.append(os[idx][3] + 1)
            # print(os[idx])
            idx = parent[idx]
        l.reverse()
        print(len(l), *l)
        exit()
    for i in range(idx + 1, n):
        if os[i][0] > end + 1:
            break
        if done[i] or parent[i] != -1:
            continue
        parent[i] = idx
        heapq.heappush(heap, (cost + os[i][2], os[i][1], i))

print("-1")
RészfeladatÖsszpontTesztVerdiktIdőMemória
base28/40
1Elfogadva0/019ms11528 KiB
2Elfogadva0/0149ms17620 KiB
3Elfogadva1/118ms12076 KiB
4Elfogadva3/318ms12232 KiB
5Elfogadva2/218ms12596 KiB
6Elfogadva2/218ms12524 KiB
7Elfogadva2/218ms12644 KiB
8Elfogadva2/218ms13220 KiB
9Elfogadva2/218ms13404 KiB
10Időlimit túllépés0/2680ms30404 KiB
11Időlimit túllépés0/2667ms30636 KiB
12Elfogadva2/220ms14036 KiB
13Elfogadva2/278ms15972 KiB
14Részben helyes1/3104ms18156 KiB
15Elfogadva3/3128ms18996 KiB
16Időlimit túllépés0/2652ms30984 KiB
17Időlimit túllépés0/2666ms31092 KiB
18Részben helyes1/218ms14008 KiB
19Részben helyes1/218ms14228 KiB
20Elfogadva2/218ms14388 KiB
21Elfogadva2/218ms14488 KiB