Submission #1083129

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1083129	2024-09-02 15:55:31	Rishi_Jaiswal	Commuter Pass (JOI18_commuter_pass)	Cpython 3	0 / 100	2063 ms	262144 KiB

commuter_pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import heapq
def dijkstra(graph, s, t):
    visited = [False for _ in range(len(graph))]
    costs = [float('inf') for _ in range(len(graph))]
    paths = [[] for _ in range(len(graph))]
    priority_queue = []
    heapq.heappush(priority_queue, (0, s, [s]))
    costs[s - 1] = 0
    paths[s - 1] = [s]
    while priority_queue:
        current_cost, current_node, current_path = heapq.heappop(priority_queue)
        if current_cost > costs[current_node - 1]:
            continue
        visited[current_node - 1] = True
        for neighbour in graph[current_node]:
            cost = current_cost + neighbour[1]
            path = current_path + [neighbour[0]]
            if cost < costs[neighbour[0] - 1]:
                costs[neighbour[0] - 1] = cost
                paths[neighbour[0] - 1].append(path)
                heapq.heappush(priority_queue, (cost, neighbour[0], path))
            elif cost == costs[neighbour[0] - 1]:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45