Problem: You are given an undirected connected weighted graph with N vertices and M edges that contains neither self-loops nor double edges.   The i-th (1≤i≤M) edge connects vertex a_i and vertex b_i with a distance of c_i.   Here, a _self-loop_ is an edge where a_i = b_i (1≤i≤M), and _double edges_ are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).   A _connected graph_ is a graph where there is a path between every pair of different vertices.   Find the number of the edges that are not contained in any shortest path between any pair of different vertices.

Submission attempts (in order):

from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    heap = [(0,start)]
    
    
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

class MakeGraph:
    
    
    
    
    def __init__(self, node_num:int, isMat:bool) -> None:
        self.n = node_num
        self.isMat = isMat

        
        if self.isMat:
            INF = float("inf")
            self.graph = [[INF for _ in range(self.n)] for _ in range(self.n)]
    
        
        else:
            self.graph = [[] for _ in range(self.n)]

    
    
    
    def add_undr_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        self.graph[to][frm] = dist
        
    def add_drct_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        
    def add_undr_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))
        self.graph[to].append((dist, frm))
        
    def add_drct_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))

                
    
    def get_graph(self) -> list:
        return self.graph


N,M = map(int, input().split())
ABC = []
for i in range(M):
    ABC.append(tuple(map(int, input().split())))
    
    
graphMaker = MakeGraph(N,False)
add_edge = graphMaker.add_undr_edge_lst

for a,b,c in ABC:
    add_edge(a-1, b-1, c)

graph = graphMaker.get_graph()

dist = []
for i in range(N):
    dist_temp = dijkstra(graph, N, i)
    dist.append(dist_temp)
    
ans = 0
for i in range(N):
    for cost, node in graph[i]:
        if dist[i][node] != cost:
            ans += 1
            
            
print(ans)


class MakeGraph:
    
    
    
    
    def __init__(self, node_num:int, isMat:bool) -> None:
        self.n = node_num
        self.isMat = isMat

        
        if self.isMat:
            INF = float("inf")
            self.graph = [[INF for _ in range(self.n)] for _ in range(self.n)]
    
        
        else:
            self.graph = [[] for _ in range(self.n)]

    
    
    
    def add_undr_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        self.graph[to][frm] = dist
        
    def add_drct_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        
    def add_undr_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))
        self.graph[to].append((dist, frm))
        
    def add_drct_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))

                
    
    def get_graph(self) -> list:
        return self.graph


N,M = map(int, input().split())
ABC = []
for i in range(M):
    ABC.append(tuple(map(int, input().split())))
    
graphMaker = MakeGraph(N,True)
add_edge = graphMaker.add_undr_edge_mat
for a,b,c in ABC:
    add_edge(a-1, b-1, c)
    
graph = graphMaker.get_graph()
for i in range(N):
    graph[i][i] = 0

# WF
min_root = [[[] for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        min_root[i][j].append(j)
        
for i in range(N):
    for j in range(N):
        for k in range(N):
            if graph[i][j] >= graph[i][k]+graph[k][j]:
                graph[i][j] = graph[i][k]+graph[k][j]
                min_root[i][j].append(k)
       
for i in range(N):
    for j in range(N):
        min_root[i][j].append(i)
        

edge_list = []
for a,b,c in ABC:
    edge_list.append([a-1,b-1])
    

for i in range(N):
    for j in range(N):
        for k in range(len(min_root[i][j])-1):
            if i==j:
                continue
            
            if [min_root[i][j][k], min_root[i][j][k+1]] in edge_list:
                edge_list.remove([min_root[i][j][k], min_root[i][j][k+1]])
                
                
            elif [min_root[i][j][k+1], min_root[i][j][k]] in edge_list:
                edge_list.remove([min_root[i][j][k+1], min_root[i][j][k]])
                
                
print(len(edge_list))
                
        

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    heap = [(0,start)]
    
    
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

n,m = li()

edges = []
graph = [[] for _ in range(n)]
adj_mat = [[0]*n for _ in range(n)]

for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    edges.append((a,b,c))
    

for i in range(n):
    adj_mat[i] = dijkstra(graph, n, i)
    
    

ans = 0
for ai, bi, ci in edges:
    if adj_mat[ai][bi] < ci:
        ans += 1
        
print(ans)

Verdicts: Wrong Answer

Wrong Answer

Accepted