TnT/Multi_CodeNet4Repair huggingface dataset:
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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
abc = [LIST() for _ in range(M)]

def warshall_floyd(d):
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = [[INF for i in range(N)] for i in range(N)] 

for x, y, z in abc:
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0 
# print(warshall_floyd(d))
count = 0
for a, b, c in abc:
	for i in range(N):
		if d[i][a-1] + c == d[a-1][b-1]:
			break
	else:
		count += 1
print(count)

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
abc = [LIST() for _ in range(M)]

def warshall_floyd(d):
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = [[INF for i in range(N)] for i in range(N)] 

for x, y, z in abc:
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0 
warshall_floyd(d)
count = 0
for a, b, c in abc:
	for i in range(N):
		if d[i][a-1] + c == d[a-1][b-1]:
			break
	else:
		count += 1
print(count)

Verdicts: Wrong Answer

Accepted
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):
n, m = list(map(int, input().split()))

import numpy as np
dists = np.ones((n + 1, n + 1)) * (10 ** 6)
edges = []
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
    edges.append(a, b, c)
for i in range(1, n + 1):
    dists[i, i] = 0
for i in range(1, 1 + n):
    dists = np.minimum(dists, dists[i: i + 1] + dists[:, i: i + 1])
cnt = 0
for a, b, c in edges:
    if dists[a, b] < c:
        cnt += 1

print(cnt)


n, m = list(map(int, input().split()))

import numpy as np
dists = np.ones((n + 1, n + 1)) * (10 ** 6)
edges = []
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
    edges.append((a, b, c))
for i in range(1, n + 1):
    dists[i, i] = 0
for i in range(1, 1 + n):
    dists = np.minimum(dists, dists[i: i + 1] + dists[:, i: i + 1])
cnt = 0
for a, b, c in edges:
    if dists[a, b] < c:
        cnt += 1

print(cnt)


Verdicts: Runtime Error

Accepted
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):
import heapq

n, m = [int(i) for i in input().split()]
inf = 10**10
path = [[0] * n for _ in range(n)]
Q = [[inf] * n for _ in range(n)]
ans = 0
pathnum = []
ctr = 0

for i in range(m):
    a, b, c = map(lambda x: int(x)-1 ,input().split())    
    path[a][b] = path[b][a] = c+1
    pathnum.append((a,b))

for i in range(n):
    decided = [False for _ in range(n)]
    H = []
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    while ctr != n:
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                ctr += 1
                break
        for j in range(n):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

for i in pathnum:
    if Q[i[0]][i[1]] == inf:
        continue
    elif Q[i[0]][i[1]] != path[i[0]][i[1]]:
        ans += 1
print(ans)
    

import heapq

n, m = [int(i) for i in input().split()]
inf = 10**10
path = [[0] * n for _ in range(n)]
Q = [[inf] * n for _ in range(n)]
ans = 0
pathnum = []

for i in range(m):
    a, b, c = map(lambda x: int(x)-1 ,input().split())    
    path[a][b] = path[b][a] = c+1
    pathnum.append((a,b))

for i in range(n):
    decided = [False for _ in range(n)]
    H = []
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    for _ in range(n):
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                break
        for j in range(n):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

for i in pathnum:
    if Q[i[0]][i[1]] == inf:
        continue
    elif Q[i[0]][i[1]] != path[i[0]][i[1]]:
        ans += 1
print(ans)

Verdicts: Wrong Answer

Accepted
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):
n,m=map(int,input().split())
l=[list(map(int,input().split()))for i in range(m)]
dist=[[1<<29]*n for i in range(n)]
for i in range(n): dist[i][i]=0
for a in l:
  dist[a[0]-1][a[1]-1] = min(dist[a[0]-1][a[1]-1],a[2])
  dist[a[1]-1][a[0]-1] = min(dist[a[1]-1][a[0]-1],a[2])
print(dist)
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans=m
for a in l:
  flag=False
  for j in range(n): 
    if dist[j][a[0]-1]+a[2]==dist[j][a[1]-1]: flag=True
  if flag: ans-=1
print(ans)

n,m=map(int,input().split())
l=[list(map(int,input().split()))for i in range(m)]
dist=[[1<<29]*n for i in range(n)]
for i in range(n): dist[i][i]=0
for a in l:
  dist[a[0]-1][a[1]-1] = min(dist[a[0]-1][a[1]-1],a[2])
  dist[a[1]-1][a[0]-1] = min(dist[a[1]-1][a[0]-1],a[2])
# print(dist)
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans=m
for a in l:
  flag=False
  for j in range(n): 
    if dist[j][a[0]-1]+a[2]==dist[j][a[1]-1]: flag=True
  if flag: ans-=1
print(ans)


Verdicts: Wrong Answer

Accepted
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):
def warshall_floyd(d, V, M): 
    for k in range(V):
        for i in range(V):
            for j in range(V):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
                
    return d
    
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
dist = [[10 ** 5 for i in range(N)] for i in range(N)]

for l in L:
    l[0] -= 1
    l[1] -= 1
      
for i in range(M):
    dist[L[i][0]][L[i][1]] = L[i][2]
    dist[L[i][1]][L[i][0]] = L[i][2]

dist = warshall_floyd(dist, N, M)

res = M
for i in range(M):
    if dist[L[i][0]][L[i][1]] != L[i][2]:
        res -= 1
            
print(res)

def warshall_floyd(d, V, M): 
    for k in range(V):
        for i in range(V):
            for j in range(V):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
                
    return d
    
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
dist = [[10 ** 5 for i in range(N)] for i in range(N)]

for l in L:
    l[0] -= 1
    l[1] -= 1
      
for i in range(M):
    dist[L[i][0]][L[i][1]] = L[i][2]
    dist[L[i][1]][L[i][0]] = L[i][2]

dist = warshall_floyd(dist, N, M)

res = 0

for i in range(M):
    if dist[L[i][0]][L[i][1]] != L[i][2]:
        res += 1
            
print(res)

Verdicts: Wrong Answer

Accepted
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):
INF=100000000000


def floyd_warshall(dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if (dist[i][j] > dist[i][k]+dist[k][j]):
                    dist[i][j] = dist[i][k]+dist[k][j]
                    dist[j][i] = dist[i][k]+dist[k][j]

n,m = map(int,input().split())
dist=[[INF]*n for i in range(n)]
edges=[]

for i in range(m):
    ai,bi,ci=map(int,input().split())
    edges.append(tuple([ai-1,bi-1,ci]))
    dist[ai-1][bi-1]=ci
    dist[bi-1][ai-1]=ci

for i in range(n):
    dist[i][i] = 0

floyd_warshall(dist)

#print(dist)
count = 0
for edge in edges:
    ai,bi,ci=edge
    flag = 0
    for s in range(n):
        if dist[s][ai]+ci == dist[s][bi]:
            flag+=1

    if flag > 0:
        count+=1

print(count)

        
    
    
   

INF=100000000000


def floyd_warshall(dist):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

n,m = map(int,input().split())
dist=[[INF]*n for i in range(n)]
edges=[]

for i in range(m):
    ai,bi,ci=map(int,input().split())
    edges.append(tuple([ai-1,bi-1,ci]))
    dist[ai-1][bi-1]=ci
    dist[bi-1][ai-1]=ci

for i in range(n):
    dist[i][i] = 0

floyd_warshall(dist)

#print(dist)
ans = m
for edge in edges:
    ai,bi,ci=edge
    flag = 0
    for s in range(n):
        if dist[s][ai]+ci == dist[s][bi]:
            flag+=1

    if flag > 0:
        ans-=1

print(ans)

     

Verdicts: Wrong Answer

Accepted
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):
n,m = map(int,input().split())
dist = []
a = []
b = []
c = []

for i in range(m):
	a[i], b[i], c[i] = map(int,input().split())
	dist[a[i]-1][b[i]-1] = c[i]
	dist[b[i]-1][a[i]-1] = c[i]






for i in range(n):
	for j in range(n):
		for k in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

res = 0
for i in range(m):
	if c[i] > dist[a[i]-1][b[i]-1]:
		res += 1

print (res)


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

dist = [[10**10 for i in range(n)]for j in range(n)]
for i in range(n):
	dist[i][i] == 0

a = [0]*m
b = [0]*m
c = [0]*m

for i in range(m):
	a[i], b[i], c[i] = map(int,input().split())
	dist[a[i]-1][b[i]-1] = c[i]
	dist[b[i]-1][a[i]-1] = c[i]





for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


res = 0
for i in range(m):
	if c[i] > dist[a[i]-1][b[i]-1]:
		res += 1

print(res)


Verdicts: Runtime Error

Accepted
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):
#!/usr/bin/env python3
import sys

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    import numpy as np    
    from scipy.sparse import csr_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    omat = csr_matrix((c, (a, b)), shape=(N+1, N+1), dtype=np.int32, directed=False)
    smat = floyd_warshall(omat)
    return ((omat-smat) > 0).sum() // 2


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    print(solve(N, M, a, b, c))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


#!/usr/bin/env python3
import sys

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    import numpy as np    
    from scipy.sparse import csr_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    omat = csr_matrix((c, (a, b)), shape=(N+1, N+1), dtype=np.int32)
    smat = floyd_warshall(omat, directed=False)
    return ((smat-omat) < 0).sum()


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    print(solve(N, M, a, b, c))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


Verdicts: Runtime Error

Accepted
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):
n, m = map(lambda x: int(x), input().split())
a = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
    a[i], b[i], c[i] = map(lambda x: int(x), input().split())

def dijkstra(graph, start, end):
    print('start:{}, end:{}'.format(start, end))
    cost = [1000*100 for _ in range(n+1)]
    fixed = [False for _ in range(n+1)]
    cost[start] = 0
    fixed[start] = True
    tmp_sta = start
    while True:
        tmp_min = 1000*100
        for i in graph[tmp_sta]:
            cost[i[0]] = min(cost[i[0]], cost[tmp_sta]+i[1])
        for i in range(1, n+1):
            if tmp_min > cost[i] and fixed[i] == False:
                tmp_min = cost[i]
                tmp_sta = i
        if tmp_sta == end:
            return tmp_min
        else:
            fixed[tmp_sta] = True
    
graph = {}
for i in range(1, n+1):
    graph[i] = []
for i in range(m):
    graph[a[i]].append((b[i], c[i]))
    graph[b[i]].append((a[i], c[i]))
print(graph)
    
ans = 0
for i in range(m):
    if c[i] > dijkstra(graph, a[i], b[i]):
        ans += 1
print(ans)

n, m = map(lambda x: int(x), input().split())
a = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
    a[i], b[i], c[i] = map(lambda x: int(x), input().split())

def dijkstra(graph, start):
    cost = [1000*100 for _ in range(n+1)]
    fixed = [False for _ in range(n+1)]
    cost[start] = 0
    fixed[start] = True
    tmp_sta = start
    while True:
        tmp_min = 1000*100
        for i in graph[tmp_sta]:
            cost[i[0]] = min(cost[i[0]], cost[tmp_sta]+i[1])
        for i in range(1, n+1):
            if tmp_min > cost[i] and fixed[i] == False:
                tmp_min = cost[i]
                tmp_sta = i
        if tmp_min == 1000*100:
            return cost
        else:
            fixed[tmp_sta] = True
    
graph = {}
for i in range(1, n+1):
    graph[i] = []
for i in range(m):
    graph[a[i]].append((b[i], c[i]))
    graph[b[i]].append((a[i], c[i]))

cost2d = [[]]
for i in range(1, n+1):
    cost2d.append(dijkstra(graph, i))

ans = 0
for i in range(m):
    if c[i] > cost2d[a[i]][b[i]]:
        ans += 1
print(ans)

Verdicts: Wrong Answer

Accepted
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 scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import dijkstra
n,m=map(int,input().split())
dis=[[float('inf') for i in range(n)]for j in range(n)]
for i in range(n):
    dis[i][i]=0
for i in range(m):
    a,b,t=map(int,input().split())
    dis[a-1][b-1]=t
    dis[b-1][a-1]=t
cost=dijkstra(dis,directed=False,unweighted=False)
cnt=0
for i,j,k in dis:
    if k>costs[i-1][j-1]:
        cnt+=1
print(cnt)


n, m = map(int, input().split())
INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]
tmp = []

for i in range(m):
    a, b, c = map(int, input().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c
    tmp.append((a - 1, b - 1, c))

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

ans = 0
for a, b, c in tmp:
    if c > graph[a][b]:
        ans += 1

print(ans)


Verdicts: Runtime Error

Accepted
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):

def warshall_floyd(d):
    
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n,w = map(int,input().split()) 
d = [[float('inf') for i in range(n+1)] for i in range(n+1)] 

W = []
for i in range(w):
    x,y,z = map(int,input().split())
    W.append((x,y,z))
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 
a = 1
for i in range(w):
    x,y,z = W[i][0],W[i][1],W[i][2]
    if d[x][y] < z:
        a += 1
ans = w - a
print(ans)



def warshall_floyd(d):
    
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n,w = map(int,input().split()) 
d = [[float('inf') for i in range(n+1)] for i in range(n+1)] 

W = []
for i in range(w):
    x,y,z = map(int,input().split())
    W.append((x,y,z))
    d[x][y] = z
    d[y][x] = z
for i in range(n+1):
    d[i][i] = 0 
a = 0
warshall_floyd(d)
for i in range(w):
    x,y,z = W[i][0],W[i][1],W[i][2]
    if d[x][y] < z:
        a += 1
print(a)

Verdicts: Wrong Answer

Accepted
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):
import sys
from copy import deepcopy
input = sys.stdin.readline
n,m=map(int,input().split())
d=[[100000]*n for _ in range(n)]
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
  a0,b0,c0=map(int,input().split())
  a[i]=a0-1
  b[i]=b0-1
  c[i]=c0
  d[a0-1][b0-1]=c0
  d[b0-1][a0-1]=c0
for i in range(n):
  d[i][i]=0
d2=deepcopy(d)
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j]=min(d[i][j],d[i][k]+d[k][j])
count=0
for i in range(n):
  for j in range(i):
    if d[i][j]!=d[i][j]:
      count+=1
print(count)


N, M = map(int, input().split())
d = [[1000000]*N for _ in range(N)]
d_dict = {}

inf = 0
for i in range(M):
  a, b, c = map(int, input().split())
  d[a-1][b-1] = c
  d[b-1][a-1] = c
  d_dict[(a-1, b-1)] = c
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])
  
ans = 0
for key in d_dict:
  if d[key[0]][key[1]] < d_dict[key]:
    ans += 1
    
print(ans)


Verdicts: Wrong Answer

Accepted
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):
def examD():
    N, M = LI()
    D = [[float("inf") for i in range(N)] for i in range(N)]
    
    XY = [[0,0]]*M
    for i in range(M):
        x, y, z = map(int, input().split())
        XY[i] = [x-1,y-1]
        D[x - 1][y - 1] = z
        D[y - 1][x - 1] = z
    for i in range(N):
        D[i][i] = 0  
    d = copy.deepcopy(D)
#    print(warshall_floyd(N, d))
    W = warshall_floyd(N, d)
    cur = int(0)
    for i in range(M):
        if D[XY[i][0]][XY[i][1]]>W[XY[i][0]][XY[i][1]]:
            cur += 1
    print(cur)

import sys
import copy
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()


def warshall_floyd(n,d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

def examD():
    N, M = LI()
    D = [[float("inf") for i in range(N)] for i in range(N)]
    
    XY = [[0,0]]*M
    for i in range(M):
        x, y, z = map(int, input().split())
        XY[i] = [x-1,y-1]
        D[x - 1][y - 1] = z
        D[y - 1][x - 1] = z
    for i in range(N):
        D[i][i] = 0  
    d = copy.deepcopy(D)
#    print(warshall_floyd(N, d))
    W = warshall_floyd(N, d)
    cur = int(0)
    for i in range(M):
        if D[XY[i][0]][XY[i][1]]>W[XY[i][0]][XY[i][1]]:
            cur += 1
    print(cur)

import sys
import copy
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()


Verdicts: Runtime Error

Accepted
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):
n,m = map(int,input().split())
INF = 10**18
d = [[INF]*n for _ in range(n)]
used = [[True]*n for _ in range(n)]
for i in range(n): d[i][i] = 0
for _ in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    used[a][b] = False
    used[b][a] = False

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] <= d[i][k] + d[k][j]:
                used[i][j] = True
                used[j][i] = True
            else:
                d[i][j] = d[i][k] + d[k][j]

cnt = 0
for i in range(n):
    for j in range(n):
        if used[i][j]: continue
        cnt += 1
print(cnt//2)

n,m = map(int,input().split())
INF = 10**18
d = [[INF]*n for _ in range(n)]
for i in range(n): d[i][i] = 0
a = [0]*m
b = [0]*m
c = [0]*m
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    a[i] = a
    b[i] = b
    c[i] = c
    d[a][b] = c
    d[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])

ans = 0
for i in range(m):
    if d[a[i]][b[i]] < c[i]: ans += 1
print(ans)

n,m = map(int,input().split())
INF = 10**18
d = [[INF]*n for _ in range(n)]
for i in range(n): d[i][i] = 0
A = [0]*m
B = [0]*m
C = [0]*m
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    A[i] = a
    B[i] = b
    C[i] = c
    d[a][b] = c
    d[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])

ans = 0
for i in range(m):
    if d[A[i]][B[i]] < C[i]: ans += 1
print(ans)

Verdicts: Wrong Answer

Runtime Error

Accepted
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):
def dijkstra(m, s, t):
    INF = 1e10
    D = [INF] * N
    D[s] = 0
    Q = [v for v in range(N)]

    while Q:
        d = INF
        v = None
        for x in Q:
            if D[x] <= d:
                d = D[x]
                v = x
        Q.remove(v)

        for u, w in enumerate(m[v]):
            if D[u] > D[v] + w:
                D[u] = D[v] + w
    return D[t] 

N, M = map(int, input().split())

# N < 100
m = [[1e10]*N for i in range(N)]
E = [0] * M
for i in range(M):
    a, b, w = map(int, input().split())
    E[i] = a-1, b-1, w
    m[a-1][b-1] = w

count = 0
for a, b, w in E:
    d = dijkstra(m, a, b)
    if d < w:
        count += 1

print(count)


import heapq

def dijkstra(m, s, t):
    INF = 1e10
    D = [INF] * N
    D[s] = 0
    Q = [(0 if s == v else INF, v) for v in range(N)]
    heapq.heapify(Q)

    while Q:
        c, u = heapq.heappop(Q)
        if D[u] < c:
            continue
        for v, w in m[u]:
            if D[v] > D[u] + w:
                D[v] = D[u] + w
                heapq.heappush(Q, (D[u]+w, v))
    return D[t] 

N, M = map(int, input().split())

# N < 100
m = [[] for i in range(N)]
E = [0] * M
for i in range(M):
    a, b, w = map(int, input().split())
    E[i] = a-1, b-1, w
    m[a-1].append((b-1,w))
    m[b-1].append((a-1,w))

count = 0
for a, b, w in E:
    d = dijkstra(m, a, b)
    #print((a+1, b+1), d, "w=%d"%w)
    if d < w:
        count += 1

print(count)


Verdicts: Wrong Answer

Accepted
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):
import heapq

def dijkstra(adj, start, goal=None):
    n = len(adj)
    dist = [float("inf") for i in range(n)]
    prev = [float("inf") for i in range(n)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
        prov_cost, src = heapq.heappop(q)

        if dist[src] < prov_cost:
            continue

        for dest in range(n):
            cost = adj[src][dest]
            if cost != float("inf") and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost
                heapq.heappush(q, (dist[dest], dest))
                prev[dest] = src

    if goal is not None:
        return get_path(goal, prev)
    else:
        return dist

def get_path(goal, prev):
    path = [goal]
    dest = goal
    while prev[dest] != float("inf"):
        path.append(prev[dest])
        dest = prev[dest]
    return list(reversed(path))

n, m = map(int, input().split())
adj = [[float("inf") for i in range(n)] for i in range(n)]
path = []
for i in range(m):
    a, b, c = map(int, input().split())
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
    path.append(set([a - 1, b - 1]))
print(adj)
for i in range(n):
    for j in range(n):
        if i != j:
            saitan = dijkstra(adj, i, j)
            for k in range(len(saitan) - 1):
                ss = set(saitan[k:k + 2])
                if ss in path:
                    path.remove(ss)
print(len(path))

import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        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
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
shortest = []
for i in range(n):
     shortest.append(dijkstra(adj, n, i))
ans = 0
for i in range(n):
    for cost, j in adj[i]:
        if cost > shortest[i][j]:
            ans += 1
print(ans // 2)


Verdicts: Wrong Answer

Accepted
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):
# cadidates of no shortest paths
n, m = map(int, input().split())

d = [[float("inf") for i in range(n + 1)] for i in range(n + 1)]
edge_data=[]
connect={i:[] for i in range(1,n+1)}
for i in range(m):
    x, y, z = map(int, input().split())
    
    d[x][y] = z
    d[y][x] = z
    connect[x].append(y)
    connect[y].append(x)    
    edge_data.append((x,y,z))
for i in range(n + 1):
    d[i][i] = 0  


def warshall_floyd(d):
    
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

warshall_floyd(d)


cnt=0
for some in edge_data:
    x,y,zsome[0],some[1],some[2]
    if d[x][y]<z:
        cnt+=1
print(cnt)


# cadidates of no shortest paths
n, m = map(int, input().split())

d = [[float("inf") for i in range(n + 1)] for i in range(n + 1)]
edge_data=[]
connect={i:[] for i in range(1,n+1)}
for i in range(m):
    x, y, z = map(int, input().split())
    
    d[x][y] = z
    d[y][x] = z
    connect[x].append(y)
    connect[y].append(x)    
    edge_data.append((x,y,z))
for i in range(n + 1):
    d[i][i] = 0  


def warshall_floyd(d):
    
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

warshall_floyd(d)


cnt=0
for some in edge_data:
    x,y,z=some[0],some[1],some[2]
    if d[x][y]<z:
        cnt+=1
print(cnt)


Verdicts: Runtime Error

Accepted
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):
n,w = map(int,input().split()) 
from collections import defaultdict
D=defaultdict(list)
def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j]>d[i][k]+d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    D[(i,j)]=D[(i,k)]+D[(k,j)][1:]
    return d
done=[[-1]*n for _ in range(n)]
d = [[float("inf")]*n for i in range(n)] 

for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
    D[(x-1,y-1)]=[x-1,y-1]
    D[(y-1,x-1)]=[y-1,x-1]
    done[x-1][y-1]=0
    done[y-1][x-1]=0
for i in range(n):
    d[i][i] = 0 
warshall_floyd(d)
for l in D.values():
    for i in range(1,len(l)):
        a=l[i-1]
        b=l[i]
        done[a][b]=1
        done[b][a]=1
import numpy as np
done=np.array(done)
ans=(done==0).sum()
#print(D)
#print(done)
print(ans)

n,w = map(int,input().split()) 
from collections import defaultdict
D=defaultdict(list)
def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j]>d[i][k]+d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    D[(i,j)]=D[(i,k)]+D[(k,j)][1:]
    return d
done=[[-1]*n for _ in range(n)]
d = [[float("inf")]*n for i in range(n)] 

for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
    D[(x-1,y-1)]=[x-1,y-1]
    D[(y-1,x-1)]=[y-1,x-1]
    done[x-1][y-1]=0
    done[y-1][x-1]=0
for i in range(n):
    d[i][i] = 0 
warshall_floyd(d)
for l in D.values():
    for i in range(1,len(l)):
        a=l[i-1]
        b=l[i]
        done[a][b]=1
        done[b][a]=1
import numpy as np
done=np.array(done)
ans=(done==0).sum()
#print(D)
#print(done)
print(ans//2)

Verdicts: Wrong Answer

Accepted
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):
import sys
import numpy as np
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0]*N
b = [0]*N
c = [0]*N
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -=1
    b[i] -=1

MAX = 10**10
dist = np.zeros((N,N))
dist += MAX

for i in range(N):
    dist[i,i] = 0

for i in range(M):
    dist[a[i], b[i]] = c[i]
    dist[b[i], a[i]] = c[i]

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i, j] = min(dist[i,j], dist[i,k] + dist[k,j])

ans = 0
for i in range(M):
    if dist[a[i], b[i]] < c[i]:
        ans += 1

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0]*M
b = [0]*M
c = [0]*M
for i in range(M):
    input_data = input().split()
    a[i], b[i], c[i] = map(int, input_data)
    a[i] -=1
    b[i] -=1

MAX = 10**10
dist = [[MAX for j in range(N)] for i in range(N)]
#dist += MAX

for i in range(N):
    dist[i][i] = 0

for i in range(M):
    dist[a[i]][b[i]] = c[i]
    dist[b[i]][a[i]] = c[i]

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = 0
for i in range(M):
    if dist[a[i]][b[i]] < c[i]:
        ans += 1

print(ans)

Verdicts: Runtime Error

Accepted
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):
n, m = map(int, input().split())

d = np.ones((n, n)) * 1001

es = []
for i in range(m):
    es.append(list(map(int, input().split())))

for (i, j, w) in es:
    d[i - 1][j - 1] = w
    d[j - 1][i - 1] = w


for k in range(n):
    for i in range(n):
        for j in range(n):
            l = d[i][k] + d[k][j]
            if d[i][j] > l:
                d[i][j] = l

c = 0
for (i, j, w) in es:
    if d[i - 1][j - 1] < w:
        c += 1

print(c)


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

d = [[1001] * n for i in range(n)]

es = []
for i in range(m):
    es.append(list(map(int, input().split())))

for (i, j, w) in es:
    d[i - 1][j - 1] = w
    d[j - 1][i - 1] = w


for k in range(n):
    for i in range(n):
        for j in range(n):
            l = d[i][k] + d[k][j]
            if d[i][j] > l:
                d[i][j] = l

c = 0
for (i, j, w) in es:
    if d[i - 1][j - 1] < w:
        c += 1

print(c)

Verdicts: Runtime Error

Accepted
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):
N, M = map(int, input().split())
INF = 10**9

edges = []

for i in range(M):
    edges.append(list(map(int, input().split())))

dist = [[INF for j in range(N)] for i in range(N)]

for i in range(N):
    dist[i][i] = 0

for i in range(M):
    a, b, c = edges[i]
    a, b = a - 1, b - 1
    dist[a][b] = c[i]
    dist[b][a] = c[i]
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])

res = M
for i in range(M):
    a, b, c = edges[i]
    a, b = a - 1, b - 1
    shortest = False
    for j in range(N):
        if dist[j][a] + c == dist[j][b]:
            shortest = True
            break
    if shortest:
        res -= 1

print(res)


N, M = map(int, input().split())
INF = 10**9

edges = []

for i in range(M):
    edges.append(list(map(int, input().split())))

dist = [[INF for j in range(N)] for i in range(N)]

for i in range(N):
    dist[i][i] = 0

for i in range(M):
    a, b, c = edges[i]
    a, b = a - 1, b - 1
    dist[a][b] = c[i]
    dist[b][a] = c[i]
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])

res = M
for i in range(M):
    a, b, c = edges[i]
    a, b = a - 1, b - 1
    shortest = False
    for j in range(N):
        if dist[j][a] + c == dist[j][b]:
            shortest = True
            break
    res -= 1

print(res)


N, M = map(int, input().split())
INF = 10**9

edges = []

for i in range(M):
    edges.append(list(map(int, input().split())))

dist = [[INF for j in range(N)] for i in range(N)]

for i in range(N):
    dist[i][i] = 0

for i in range(M):
    a, b, c = edges[i]
    a, b = a - 1, b - 1
    dist[a][b] = c
    dist[b][a] = c
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])

res = M
for i in range(M):
    a, b, c = edges[i]
    a, b = a - 1, b - 1
    shortest = False
    for j in range(N):
        if dist[j][a] + c == dist[j][b]:
            shortest = True
            break
    if shortest:
        res -= 1

print(res)


Verdicts: Runtime Error

Runtime Error

Accepted
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):
V, E = [int(_) for _ in input().split()]
G = {}
for i in range(V):
    G[i] = {}
    G[i][i] = 0

for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  
    t -= 1  
    G[s][t] = c
    G[t][s] = c

INF = 10**10

edges_used = set()
for i in range(V):
    D = [INF] * V
    D[i] = 0  
    used = [False] * V
    used[i] = True
    prev = {}
    while True:
        for j in G[i].keys():
            if D[i] + G[i][j] < D[j]:
                D[j] = D[i] + G[i][j]
                prev[j] = i
        v = -1
        for j in range(V):
            if not used[j] and (v == -1 or D[j] < D[v]):
                v = j
        if v == -1:
            break
        else:
            used[v] = True
            i = v
    for key, value in prev.items():
        if key > value:
            key, value = value, key
        edges_used.add((key + 1, value + 1))

print(edges_used)
print(E - len(edges_used))

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
N, M, *ABC = [int(_) for _ in open(0).read().split()]
ABC = np.array(ABC)
F = floyd_warshall(
    csr_matrix((ABC[2::3], (ABC[::3], ABC[1::3])), (N + 1, N + 1)), 0)
print(np.sum(F[ABC[::3], ABC[1::3]] != ABC[2::3]))


Verdicts: Wrong Answer

Accepted