Problem p03305 (python)

Fixed submission:
from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.readline


class Dijkstra:
    def __init__(self):
        self.edge = defaultdict(list)

    def add(self, u, v, d):
        self.edge[u].append([v, d])
        self.edge[v].append([u, d])

    def search(self, start):
        distance = defaultdict(lambda: float("inf"))
        distance[start] = 0
        queue = []
        heappush(queue, (0, start))
        seen = set()
        while queue:
            k, u = heappop(queue)
            if u in seen:
                continue
            seen.add(u)

            for v, d in self.edge[u]:
                if v in seen:
                    continue
                new_d = k + d
                if distance[v] > new_d:
                    distance[v] = new_d
                    heappush(queue, (new_d, v))
        return distance


n, m, s, t = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in uvab:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(s)
result_b = graph2.search(t)
ans_list = [float('inf')]

for i in range(n, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for ans in ans_list[n:0:-1]:
    print(10 ** 15 - ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
import heapq


class Dijkstra:
    def __init__(self):
        self.edge = defaultdict(list)

    def add(self, u, v, d):
        self.edge[u].append([v, d])
        self.edge[v].append([u, d])

    def search(self, start):
        distance = defaultdict(lambda: float("inf"))
        distance[start] = 0
        queue = []
        heapq.heappush(queue, (0, start))
        seen = set()
        while queue:
            k, u = heapq.heappop(queue)
            if u in seen:
                continue
            seen.add(u)

            for v, d in self.edge[u]:
                if v in seen:
                    continue
                if distance[v] > k + d:
                    distance[v] = k + d
                    heapq.heappush(queue, (k + d, v))
        return distance


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

for u, v, a, b in UVAB:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(s)
result_b = graph2.search(t)
ans_list = [float('inf')]

for i in range(n, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for i in range(len(ans_list[1:])):
    print(10 ** 15 - ans_list[-(i + 1)])

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
import heapq


class Dijkstra:
    def __init__(self):
        self.edge = defaultdict(list)

    def add(self, u, v, d):
        self.edge[u].append([v, d])
        self.edge[v].append([u, d])

    def search(self, start):
        distance = defaultdict(lambda: float("inf"))
        distance[start] = 0
        queue = []
        heapq.heappush(queue, (0, start))
        seen = set()
        while queue:
            k, u = heapq.heappop(queue)
            if u in seen:
                continue
            seen.add(u)

            for v, d in self.edge[u]:
                if v in seen:
                    continue
                if distance[v] > k + d:
                    distance[v] = k + d
                    heapq.heappush(queue, (k + d, v))
        return distance


n, m, s, t = map(int, input().split())
uvab = [list(map(int, input().split())) for i in range(M)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in UVAB:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(s)
result_b = graph2.search(t)
ans_list = [float('inf')]

for i in range(n, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for i in range(len(ans_list[1:])):
    print(10 ** 15 - ans_list[-(i + 1)])

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
import heapq

 
class Dijkstra():
    def __init__(self):
        self.e = defaultdict(list)
 
    def add(self, u, v, d, directed=False):
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])
 
    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]
 
    def Dijkstra_search(self, s):
        d = defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
 
            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))
 
        return d


N, M, S, T = map(int, input().split())
UVAB = [list(map(int, input().split())) for i in range(M)]
graph1 = Dijkstra()
graph2 = Dijkstra()
 
for u, v, a, b in UVAB:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(S)
result_b = graph2.search(T)
 
ans_list = [float('inf')]
 
for i in range(N, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for i in range(len(ans_list[1:])):
    print(10**15 - ans_list[-(i+1)])

Buggy submission (verdict: Runtime Error):
from collections import defaultdict


class Dijkstra():
    def __init__(self):
        self.e = defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        0-indexedでなくてもよいことに注意
        s = 始点
        return: 始点から各点までの最短経路
        """
        d = defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:  # defaultではFalseとなる
                continue

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d


N, M, S, T = map(int, input().split())
UVAB = [list(map(int, input().split())) for i in range(M)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in UVAB:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(S)
result_b = graph2.search(T)

ans_list = [float('inf')]

for i in range(N, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for i in range(len(ans_list[1:])):
    print(10**15 - ans_list[-(i+1)])