Problem p03305 (python)

Fixed submission:
import numpy as np
from heapq import heappush, heappop

n, m, s, t = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G[u].append((v, a, b))
    G[v].append((u, a, b))


def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (n+1)
    dist[start] = 0
    q = [(0, start)]
    while q:
        d, v = heappop(q)
        if dist[v] < d:
            continue
        for w, *a in G[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1, w))
    return dist


d1 = np.array(dijkstra(s, 0))
d2 = np.array(dijkstra(t, 1))

# print(d1)


d = []
for i in range(n+1):
    d.append(d1[i]+d2[i])


ans = []
B = 10**15
for i in range(n):
    B = min(B, d[n-i])
    ans.append(B)
ans = ans[::-1]

for i in range(n):
    print(10**15-ans[i])

Buggy submission (verdict: Runtime Error):
import sys
n, m, s, t = map(int, input().split())


# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph

# Library for INT_MAX


class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):

        # Initilaize minimum distance for next node
        min = sys.maxsize

        # Search not nearest vertex not in the
        # shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    # Funtion that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # u is always equal to src in first iteration
            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the
            # shotest path tree
            sptSet[u] = True

            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and \
                        sptSet[v] == False and \
                        dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        return dist


gy = [[0]*n for _ in range(n)]
gs = [[0]*n for _ in range(n)]

for _ in range(m):
    u, v, a, b = map(int, input().split())
    gy[u-1][v-1] = a
    gy[v-1][u-1] = a
    gs[u-1][v-1] = b
    gs[v-1][u-1] = b

# Driver program
Gy = Graph(n)
Gy.graph = gy

Gs = Graph(n)
Gs.graph = gs


dy = Gy.dijkstra(s-1)
ds = Gs.dijkstra(t-1)
# print(dy)

dist = []
for i in range(n):
    dist.append(dy[i]+ds[i])

ans = []
B = 10**15
for i in range(n):
    B = min(B, dist[n-1-i])
    ans.append(B)
ans = ans[::-1]

for i in range(n):
    print(10**15-ans[i])

Buggy submission (verdict: Runtime Error):
import sys
n, m, s, t = map(int, input().split())


# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph

# Library for INT_MAX


class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):

        # Initilaize minimum distance for next node
        min = sys.maxsize

        # Search not nearest vertex not in the
        # shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    # Funtion that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # u is always equal to src in first iteration
            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the
            # shotest path tree
            sptSet[u] = True

            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and \
                        sptSet[v] == False and \
                        dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        return dist


gy = [[0]*n for _ in range(n)]
gs = [[0]*n for _ in range(n)]

for _ in range(m):
    u, v, a, b = map(int, input().split())
    gy[u-1][v-1] = a
    gy[v-1][u-1] = a
    gs[u-1][v-1] = b
    gs[v-1][u-1] = b

# Driver program
Gy = Graph(n)
Gy.graph = gy

Gs = Graph(n)
Gs.graph = gs


dy = Gy.dijkstra(s-1)
ds = Gs.dijkstra(t-1)
# print(dy)

dist = []
for i in range(n):
    dist.append(dy[i]+ds[i])

for i in range(n):
    print(10**15-sorted(dist[i:])[0])

Buggy submission (verdict: Runtime Error):
import sys
n, m, s, t = map(int, input().split())


# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph

# Library for INT_MAX


class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):

        # Initilaize minimum distance for next node
        min = sys.maxsize

        # Search not nearest vertex not in the
        # shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    # Funtion that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # u is always equal to src in first iteration
            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the
            # shotest path tree
            sptSet[u] = True

            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and \
                        sptSet[v] == False and \
                        dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        return dist


gy = [[0]*n for _ in range(n)]
gs = [[0]*n for _ in range(n)]

for _ in range(m):
    u, v, a, b = map(int, input().split())
    gy[u-1][v-1] = a
    gy[v-1][u-1] = a
    gs[u-1][v-1] = b
    gs[v-1][u-1] = b

# Driver program
Gy = Graph(n)
Gy.graph = gy

Gs = Graph(n)
Gs.graph = gs


dy = Gy.dijkstra(s-1)
ds = Gs.dijkstra(t-1)
# print(dy)

dist = []
for i in range(n):
    dist.append(dy[i]+ds[i])

for i in range(n):
    print(10**15-sorted(dist[i:])[0])

Buggy submission (verdict: Runtime Error):
import sys
n, m, s, t = map(int, input().split())


# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph

# Library for INT_MAX


class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):

        # Initilaize minimum distance for next node
        min = sys.maxsize

        # Search not nearest vertex not in the
        # shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    # Funtion that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # u is always equal to src in first iteration
            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the
            # shotest path tree
            sptSet[u] = True

            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and \
                        sptSet[v] == False and \
                        dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        return dist


gy = [[0]*n for _ in range(n)]
gs = [[0]*n for _ in range(n)]

for _ in range(m):
    u, v, a, b = map(int, input().split())
    gy[u-1][v-1] = a
    gy[v-1][u-1] = a
    gs[u-1][v-1] = b
    gs[v-1][u-1] = b

# Driver program
Gy = Graph(n)
Gy.graph = gy

Gs = Graph(n)
Gs.graph = gs


dy = Gy.dijkstra(s-1)
ds = Gs.dijkstra(t-1)
# print(dy)

dist = []
for i in range(n):
    dist.append(dy[i]+ds[i])

for i in range(n):
    print(10**15-int(min(dist[i:])))

Buggy submission (verdict: Runtime Error):
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

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

gy = np.zeros((n, n))
gs = np.zeros((n, n))
for _ in range(m):
    u, v, a, b = map(int, input().split())
    gy[u-1][v-1] = a
    gy[v-1][u-1] = a
    gs[u-1][v-1] = b
    gs[v-1][u-1] = b


Gy = csgraph_from_dense(gy)
dy = dijkstra(Gy, indices=s-1)

Gs = csgraph_from_dense(gs)
ds = dijkstra(Gs, indices=t-1)

dist = []
for i in range(n):
    dist.append(dy[i]+ds[i])

for i in range(n):
    print(10**15-int(min(dist[i:])))

Buggy submission (verdict: Runtime Error):
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

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

gy = np.zeros((n, n))
gs = np.zeros((n, n))
for _ in range(m):
    u, v, a, b = map(int, input().split())
    gy[u-1][v-1] = a
    gy[v-1][u-1] = a
    gs[u-1][v-1] = b
    gs[v-1][u-1] = b


Gy = csgraph_from_dense(gy)
dy = dijkstra(Gy, indices=s-1)

Gs = csgraph_from_dense(gs)
ds = dijkstra(Gs, indices=t-1)

dist = []
for i in range(n):
    dist.append(dy[i]+ds[i])

for i in range(n):
    print(10**15-int(min(dist[i:])))

Buggy submission (verdict: Runtime Error):
# soundhound2018_summer_qual_d
import networkx as nx
n, m, s, t = map(int, input().split())


Gy = nx.Graph()   # Yen
Gy.add_nodes_from(range(1, n+1))

Gs = nx.Graph()   # Snuuk
Gs.add_nodes_from(range(1, n+1))


for _ in range(m):
    u, v, a, b = map(int, input().split())
    Gy.add_edge(u, v, weight=a)
    Gs.add_edge(u, v, weight=b)

shortest_length_from_s = nx.shortest_path_length(Gy, source=s, weight='weight')
shortest_length_to_t = nx.shortest_path_length(Gs, target=t, weight='weight')


dist = [-1]
for i in range(1, n+1):
    dist.append(shortest_length_from_s[i]+shortest_length_to_t[i])
# print(dist)

for i in range(1, n+1):
    print(10**15-min(dist[i:]))