Submission #1083129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083129		Rishi_Jaiswal	Commuter Pass (JOI18_commuter_pass)	Cpython 3	0 / 100	2063 ms	262144 KiB

commuter_pass

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]:
                paths[neighbour[0] - 1].append(path)
                heapq.heappush(priority_queue, (cost, neighbour[0], path))

    return costs[t - 1], paths[t - 1]

def commuter_pass(n, m, s, t, u, v, edges):
    graph = {}

    for i in range(1, n+1):
        graph.update({i : []})

    for a, b, c in edges:
        graph[a].append([b, c])
        graph[b].append([a, c])

    st_cost, st_paths = dijkstra(graph, s, t)
    
    min_cost = float('inf')
    for path in st_paths:
        min_su = min_sv = float("inf")

        for node in path:
            su_cost, su_paths = dijkstra(graph, node, u)
            min_su = min(su_cost, min_su)

            sv_cost, sv_paths = dijkstra(graph, node, v)
            min_sv = min(sv_cost, min_sv)

        min_cost = min(min_cost, min_su + min_sv)

    return min_cost



n, m = map(int, input().split())
s, t = map(int, input().split())
u, v = map(int, input().split())

edges = []

for _ in range(m):
    edge = list(map(int, input().split()))
    edges.append(edge)

# print(n, m)
# print(s, t)
# print(u, v)
# print(edges)

result = commuter_pass(n, m, s, t, u, v, edges)
print(result)

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