Problem p03305 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import sys
from heapq import heappop, heappush
from itertools import accumulate


def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float('inf')):

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) \
                    if adj_matrix else edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


# n, m, s, t = map(int, input().split())
# trains = [list(map(int, l.strip().split())) for l in sys.stdin.readlines()]

# yen_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#              for _ in range(n)]
# snuke_edges = [[float('inf') if __ != _ else 0 for __ in range(n)]
#                for _ in range(n)]
# for i, j, yen, snuke in trains:
#     yen_edges[i - 1][j - 1] = yen
#     yen_edges[j - 1][i - 1] = yen
#     snuke_edges[i - 1][j - 1] = snuke
#     snuke_edges[j - 1][i - 1] = snuke

# yen_cost = dijkstra(n, yen_edges, s - 1, adj_matrix=True)
# snuke_cost = dijkstra(n, snuke_edges, t - 1, adj_matrix=True)
# costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

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

yen_edges = [[] for _ in range(n)]
snuke_edges = [[] for _ in range(n)]
for l in sys.stdin.readlines():
    u, v, yen, snuke = map(int, l.strip().split())
# for _ in range(m):
#     u, v, yen, snuke = map(int, input().split())
    yen_edges[u - 1].append((v - 1, yen))
    yen_edges[v - 1].append((u - 1, yen))
    snuke_edges[u - 1].append((v - 1, snuke))
    snuke_edges[v - 1].append((u - 1, snuke))

yen_costs = dijkstra(n, yen_edges, s - 1)
snuke_costs = dijkstra(n, snuke_edges, t - 1)

final_costs = list(accumulate([yen + snuke for yen, snuke in zip(yen_costs, snuke_costs)][::-1], min))[::-1]
asset = 10**15
for final_cost in final_costs:
    print(asset - final_cost)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import math


def dijkstra(graph, start=0):

    num = len(graph)
    remains = [node for node in range(num)]
    dists = [math.inf if node != start else 0 for node in range(num)]

    while remains:
        min_index = min(remains, key=lambda x: dists[x])
        remains.remove(min_index)

        target_edges = graph[min_index]
        for index, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_index] + dist
                if dists[index] > dist_from_edge:
                    dists[index] = dist_from_edge

    return dists


n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = dijkstra(yen_graph, start=s - 1)
snuke_cost = dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import math


def dijkstra(graph, start=0, goal=None, verbose=0):
    '''
    sample input:
    graph = [[0, 2, 5, 4, 0, 0], # node 0
             [2, 0, 0, 3, 6, 0], # node 1
             [5, 0, 0, 2, 0, 6], # node 2
             [4, 3, 2, 0, 2, 0], # node 3
             [0, 6, 0, 2, 0, 4], # node 4
             [0, 0, 6, 0, 4, 0]  # node 5
    ]
    (
    1. distance from a node itself should be 0,
    2. if there is no edge between nodes, the distance between them should be 0
    3. weights can be negative
    )
    '''

    num = len(graph)
    remains = [node for node in range(num)]
    dists = [math.inf if node != start else 0 for node in range(num)]
    prevs = [-1 for node in range(num)]
    if goal is None:
        goal = num - 1

    while remains:
        min_index = min(remains, key=lambda x: dists[x])
        remains.remove(min_index)

        target_edges = graph[min_index]
        for index, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_index] + dist
                if dists[index] > dist_from_edge:
                    dists[index] = dist_from_edge
                    prevs[index] = min_index

    return dists


n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_cost = dijkstra(yen_graph, start=s - 1)
snuke_cost = dijkstra(snuke_graph, start=t - 1)
costs = [yen + snuke for yen, snuke in zip(yen_cost, snuke_cost)]

for i in range(n):
    asset = 10**15
    asset -= min(costs[i:])
    print(asset)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import math


def dijkstra(graph, start=0, goal=None, verbose=0):
    '''
    sample input:
    graph = [[0, 2, 5, 4, 0, 0], # node 0
             [2, 0, 0, 3, 6, 0], # node 1
             [5, 0, 0, 2, 0, 6], # node 2
             [4, 3, 2, 0, 2, 0], # node 3
             [0, 6, 0, 2, 0, 4], # node 4
             [0, 0, 6, 0, 4, 0]  # node 5
    ]
    (
    1. distance from a node itself should be 0,
    2. if there is no edge between nodes, the distance between them should be 0
    3. weights can be negative
    )
    '''

    num = len(graph)
    remains = [node for node in range(num)]
    dists = [math.inf if node != start else 0 for node in range(num)]
    prevs = [-1 for node in range(num)]
    if goal is None:
        goal = num - 1

    while remains:
        min_index = min(remains, key=lambda x: dists[x])
        remains.remove(min_index)

        target_edges = graph[min_index]
        for index, dist in enumerate(target_edges):
            if dist != 0:
                dist_from_edge = dists[min_index] + dist
                if dists[index] > dist_from_edge:
                    dists[index] = dist_from_edge
                    prevs[index] = min_index

    min_route = []
    prev = goal
    cnt = 0
    while prev != start:
        min_route.append(prev)
        prev = prevs[prev]

        cnt += 1
        if prev == -1 or cnt > num:
            raise NoRouteError(
                'There is no possible route in this graph \ngraph: {} \nstart: {} \ngoal: {}'.
                format(graph, start, goal))

    else:
        min_route.append(prev)
    min_route = min_route[::-1]
    min_dist = dists[goal]

    if verbose:
        print('---route---')
        for node in min_route[:-1]:
            print('{} -> '.format(node), end='')
        else:
            print(min_route[-1])

        print('---distance---')
        print(min_dist)

    return dists, min_route


class NoRouteError(Exception):
    pass


n, m, s, t = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(m)]

yen_graph = [[0] * n for _ in range(n)]
snuke_graph = [[0] * n for _ in range(n)]
for i, j, yen, snuke in trains:
    yen_graph[i - 1][j - 1] = yen
    yen_graph[j - 1][i - 1] = yen
    snuke_graph[i - 1][j - 1] = snuke
    snuke_graph[j - 1][i - 1] = snuke

yen_dist, min_route = dijkstra(yen_graph, start=s - 1)
snuke_dist, min_route = dijkstra(snuke_graph, start=t - 1)

for i in range(n):
    asset = 10**15
    asset -= min(
        [yen + snuke for yen, snuke in zip(yen_dist[i:], snuke_dist[i:])])
    print(asset)