Problem:


Score : 400 points

Problem Statement

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.  

Constraints

2≤N≤100 

N-1≤M≤min(N(N-1)/2,1000) 

1≤a_i,b_i≤N 

1≤c_i≤1000

c_i is an integer.

The given graph contains neither self-loops nor double edges.

The given graph is connected.

Input

The input is given from Standard Input in the following format:

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

Output

Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.

Sample Input 1

3 3
1 2 1
1 3 1
2 3 3

Sample Output 1

1

In the given graph, the shortest paths between all pairs of different vertices are as follows:

The shortest path from vertex 1 to vertex 2 is: vertex 1 → vertex 2, with the length of 1.

The shortest path from vertex 1 to vertex 3 is: vertex 1 → vertex 3, with the length of 1.

The shortest path from vertex 2 to vertex 1 is: vertex 2 → vertex 1, with the length of 1.

The shortest path from vertex 2 to vertex 3 is: vertex 2 → vertex 1 → vertex 3, with the length of 2.

The shortest path from vertex 3 to vertex 1 is: vertex 3 → vertex 1, with the length of 1.

The shortest path from vertex 3 to vertex 2 is: vertex 3 → vertex 1 → vertex 2, with the length of 2.

Thus, the only edge that is not contained in any shortest path, is the edge of length 3 connecting vertex 2 and vertex 3, hence the output should be 1.

Sample Input 2

3 2
1 2 1
2 3 1

Sample Output 2

0

Every edge is contained in some shortest path between some pair of different vertices.



Sample input:
3 3
1 2 1
1 3 1
2 3 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
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
abc = []
for i in range(m):
    a, b, c = map(int, input().split())
    abc.append([a, b])
    dis[a-1][b-1] = c
    dis[b-1][a-1] = c
flag = [[False for i in range(n)] for j in range(n)]
def warshall_floyd(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis1 = dis[i][j]
                dis2 = dis[i][k] + dis[k][j]
                if dis1 < dis2:
                    flag[i][j] = True
                    flag[j][i] = True
                dis[i][j] = min(dis1, dis2)
    return
warshall_floyd(dis)
ans = 0
for i in range(m):
    a, b = abc[i][0], abc[i][1]
    if flag[a-1][b-1] == False:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq


def dijkstra(s):
    dist[s] = 0
    que = []
    heapq.heappush(que, (0, s))
    while len(que) != 0:
        p = heapq.heappop(que)
        v = p[1]
        if (dist[v] < p[0]):
            continue
        for e in graph[v]:
            if dist[e[0]] > dist[v] + e[1]:
                dist[e[0]] = dist[v] + e[1]
                prev[e[0]] = v
                heapq.heappush(que, (dist[e[0]], e[0]))


def get_path(t):
    path = []
    while t != -1:
        path.append(t)
        t = prev[t]
    path = path[::-1]
    return path


N, W = map(int, input().split())
graph = [[] for i in range(N)]
edges = {}
for i in range(W):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    graph[x].append((y, z))
    graph[y].append((x, z))
    edges[(x, y)] = True

for st in range(N):
    dist = [float("inf")] * N
    prev = [-1] * N
    dijkstra(st)
    for i in range(st, N):
        gp = get_path(i)
        for i in range(1, len(gp)):
            edges[(gp[i-1], gp[i])] = False
            
print(sum(edges.values()))

Submission status: Wrong Answer

Solution code:
import heapq
N, W = map(int, input().split())

graph = [[] for i in range(N)]

for i in range(W):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    graph[x].append((y, z))
    graph[y].append((x, z))

def Prim():
    used = [False]*N
    ans = 0
    edgelist = []
    for e in graph[0]:
        heapq.heappush(edgelist, e[::-1])
    used[0] = True 
    v = 1
    while v < N:
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        ans += minedge[0]
        v += 1
        used[minedge[1]] = True
        for e in graph[minedge[1]]:
            if not used[e[0]]:
                heapq.heappush(edgelist, e[::-1])
    return ans

print(W-Prim())

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())
graph = [[1000] * N for _ in range(N)]
before = []
for _ in range(M):
    a,b,c = (int(x) for x in input().split())
    before.append((a-1,b-1,c))
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

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

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

ans = 0
for x in before:
    if graph[x[0]][x[1]] != x[2]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())
graph = [[1000] * N for _ in range(N)]
before = []
for _ in range(M):
    a,b,c = (int(x) for x in input().split())
    before.append((a-1,b-1,c))
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

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

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

ans = 0
for x in before:
    for i in range(N):      
        if graph[i][x[0]] + x[2] == graph[x[0]][x[1]]:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())
graph = [[1000] * N for _ in range(N)]
before = []
for _ in range(M):
    a,b,c = (int(x) for x in input().split())
    before.append((a-1,b-1,c))
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

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

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

ans = 0
for x in before:
    for i in range(N):      
        if graph[i][x[0]] + x[2] == graph[x[0]][x[1]]:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())
graph = [[1000] * N for _ in range(N)]
before = []
for _ in range(M):
    a,b,c = (int(x) for x in input().split())
    before.append((a-1,b-1,c))
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

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

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

ans = 0         
for x in before:
    if graph[x[0]][x[1]] != x[2]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        cost[i][i] = 0

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

    res = set()
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if cost[i][j] > cost[i][k] + cost[k][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]
                    if (k, i) not in res and (i, k) not in res:
                        res.add((i, k))
                    if (j, k) not in res and (k, j) not in res:
                        res.add((k, j))

    print(m - len(res))


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def dijkstra_heap(v, start, edge, remove):
    """
    ダイクストラ法
    :param v: 走査するグラフの頂点数
    :param start: 始点
    :param edge: 重み付き隣接リスト。[cost, node]の形で渡す
    :return: 始点から各頂点への最短距離
    """
    res = [f_inf] * v
    res[start] = 0
    checked = [False] * v
    checked[start] = True
    edge_list = []
    for u in edge[start]:
        if [start, u[1]] == remove or [u[1], start] == remove:
            continue
        heappush(edge_list, u)
    while len(edge_list):
        min_edge = heappop(edge_list)
        cost, node = min_edge
        if not checked[node]:
            res[node] = cost
            checked[node] = True
            for next_cost, next_node in edge[node]:
                if [node, next_node] == remove or [next_node, node] == remove:
                    continue
                if not checked[next_node]:
                    heappush(edge_list, [next_cost + cost, next_node])
    return res


def resolve():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    edge = []
    for _ in range(m):
        a, b, c = map(int, input().split())
        graph[a - 1].append([c, b - 1])
        graph[b - 1].append([c, a - 1])
        edge.append([a - 1, b - 1])

    res = 0
    dist_init = dijkstra_heap(n, 0, graph, [])
    for remove in edge:
        dist = dijkstra_heap(n, 0, graph, remove)
        if dist == dist_init:
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))
vs = [[False]*n for _ in range(n)]
for i in range(n):
    ds = [-1]*n
    hq = [(0,i,None)]
    while hq:
        c,idx,v = heapq.heappop(hq)
        if ds[idx] != -1:
            continue
        ds[idx] = c
        if v != None:
            vs[v[0]][v[1]] = True
        for j in g[idx]:
            if ds[j[0]] == -1:
                heapq.heappush(hq,(c+j[1],j[0],(idx,j[0])))
            elif ds[j[0]] == c+j[1]:
                vs[idx][j[0]] = True
res = 0
for i in range(n):
    for j in g[i]:
        if vs[i][j[0]] == False:
            res += 1
print(res//2)

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))
vs = [[False]*n for _ in range(n)]
for i in range(n):
    ds = [-1]*n
    hq = [(0,i,None)]
    while hq:
        c,idx,v = heapq.heappop(hq)
        if ds[idx] != -1:
            continue
        ds[idx] = c
        if v != None:
            vs[v[0]][v[1]] = True
        for j in g[idx]:
            if ds[j[0]] == -1:
                heapq.heappush(hq,(c+j[1],j[0],(idx,j[0])))
res = 0
for i in range(n):
    for j in g[i]:
        if vs[i][j[0]] == False:
            res += 1
print(res//2)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
G = np.array([tuple(map(int, input().split())) for _ in range(M)])
G[:, 0:-1] -= 1

matr = csr_matrix((G[:, 2], (G[:, 0], G[:, 1])), shape=(N, N))
way = floyd_warshall(matr, directed=False).astype(int).tolist()

ans = M
for i, j, d in G:
    for s, t in itertools.combinations(range(N), 2):
        if way[s][i] + d + way[j][t] == way[s][t]:
            ans -= 1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd

N,M = map(int,input().split())
check = dd(int)
edge = []
res = 0
dist = [[0]*N for _ in range(N)]
for i in range(M):
    p,q,c = map(int,input().split())
    dist[p-1][q-1] = c
    dist[q-1][p-1] = c
    edge.append((p-1,q-1,c))
    check[(p-1,q-1)] = 1

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

for now in edge:
    for s in range(N):
        for t in range(N):
            if dist[s][t] == dist[s][now[0]] + now[2] + dist[now[1]][t]:
                check[(now[0],now[1])] = 0
for v in check.values():
    res += v
print(res)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *ABC = map(int, read().split())
    G = [[INF] * N for _ in range(N)]
    edge = [0] * M
    for i, (a, b, c) in enumerate(zip(*[iter(ABC)] * 3)):
        edge[i] = (a - 1, b - 1)
        G[a - 1][b - 1] = G[b - 1][a - 1] = c
    for i in range(N):
        G[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]

    ans = 0
    for a, b in edge:
        used = False
        for i in range(N):
            if i in (a, b):
                continue
            if G[i][b] == G[i][a] + G[a][b] or G[i][a] == G[i][b] + G[b][a]:
                used = True
                break
        if not used:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *ABC = map(int, read().split())
    G = [[INF] * N for _ in range(N)]
    edge = [0] * M
    for i, (a, b, c) in enumerate(zip(*[iter(ABC)] * 3)):
        edge[i] = (a - 1, b - 1)
        G[a - 1][b - 1] = G[b - 1][a - 1] = c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]

    ans = 0
    for a, b in edge:
        used = False
        for i in range(N):
            if i in (a, b):
                continue
            if G[i][b] == G[i][a] + G[a][b] or G[i][a] == G[i][b] + G[b][a]:
                used = True
                break
        if not used:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *ABC = map(int, read().split())
    G = [[INF] * N for _ in range(N)]
    edge = [0] * M
    for i, (a, b, c) in enumerate(zip(*[iter(ABC)] * 3)):
        edge[i] = (a - 1, b - 1)
        G[a - 1][b - 1] = G[b - 1][a - 1] = c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]

    ans = 0
    for a, b in edge:
        used = False
        for i in range(N):
            if G[i][b] == G[i][a] + G[a][b] or G[i][a] == G[i][b] + G[b][a]:
                used = True
                break
        if not used:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
graph=[[] for _ in range(N)]
cost=[[float("inf")]*N for _ in range(N)]
for _ in range(M):
    a,b,c=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1][b-1]=c
    cost[b-1][a-1]=c

def dijkstra(S,N,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[S]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
    
    return d

dist=[]
for s in range(N):
    dist.append(dijkstra(s,N,cost))

checked=[[False]*N for _ in range(N)]
ans=0
for s in range(N-1):
    for i in range(s,N):
        for j in graph[i]:
            if checked[i][j]:
                continue
            checked[i][j]=True
            checked[j][i]=True

            if dist[s][i]+cost[i][j]==dist[s][j]:
                continue
            else:
                ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
  n, m = map(int, input().split())
  road = [[100000]*n for _ in range(n)]
  count = [[-1]*n for i in range(n)]
  for _ in range(m):
    a, b, c = map(int, input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
    count[a-1][b-1] = 0
    count[b-1][a-1] = 0
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if road[i][k]+road[k][j] < road[i][j]:
          if count[i][j] == 0:
            count[i][j] = 1
          road[i][j] = road[i][k]+road[k][j]
  print(count)
  ans = 0
  for i in range(n):
    ans += count[i].count(1)
  print(ans//2)
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
  n, m = map(int, input().split())
  road = [[100000]*n for _ in range(n)]
  for _ in range(m):
    a, b, c = map(int, input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
  count = [[0]*n for i in range(n)]
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if road[i][k]+road[k][j] < road[i][j]:
          if road[i][j] != 100000:
            count[i][j] = 1
          road[i][j] = road[i][k]+road[k][j]
  
  ans = 0
  for i in range(n):
    ans += sum(count[i])
  print(ans//2)
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
  n, m = map(int, input().split())
  road = [[100000]*n for _ in range(n)]
  for _ in range(m):
    a, b, c = map(int, input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
  ans = 0
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if road[i][k]+road[k][j] < road[i][j]:
          if road[i][j] != 100000:
            ans += 1
          road[i][j] = road[i][k]+road[k][j]
  print(ans//2)
  
  
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
joined = [0] * n

from heapq import heappop, heappush
E = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    heappush(E, (c, a, b))

ans = 0
for _ in range(m):
    c, a, b = heappop(E)

    if joined[a] == 1 and joined[b] == 1:
        ans += 1
    else:
        joined[a] = 1
        joined[b] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M = getNM()
query = [getList() for i in range(M)]

dist = [[float('inf')] * N for i in range(N)]
for i in range(N):
    dist[i][i] = 0
for i in range(M):
    a, b, c = query[i]
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

def warshall_floyd(dist):
    for k in range(N):
        # i:start j:goal k:中間地点でループ回す
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

warshall_floyd(dist)
ng_dist = [0] * M

for i in range(N):
    for j in range(i + 1, N):
        for l in range(M):
            s, t, c = query[l]
            opt = dist[i][s - 1] + c + dist[t - 1][j]
            if opt == dist[i][j]:
                ng_dist[l] = 1

cnt = 0
for i in ng_dist:
    if i == 0:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    used = set()
    for i in range(N):
        H = []
        for b, c in G[i]:
            heapq.heappush(H, (c, i, b))
        todo = set(range(N))
        todo.remove(i)
        while todo:
            c, a, b = heapq.heappop(H)
            if b not in todo:
                continue
            if a < b:
                used.add((a, b))
            else:
                used.add((b, a))
            todo.remove(b)
            for d, cc in G[b]:
                if d in todo:
                    heapq.heappush(H, (c + cc, b, d))
    return M - len(used)

print(main())

Submission status: Wrong Answer

Solution code:
def warshall_floyd(graph):
    n_nodes = len(graph)

    froms = []
    for i in range(len(graph)):
        froms.append([])
        for j in range(len(graph[i])):
            if i == j:
                froms[i].append(0)
            elif graph[i][j] < float("inf"):
                froms[i].append(i)
            else:
                froms[i].append(None)

    for k in range(n_nodes):
        for i in range(n_nodes):
            for j in range(n_nodes):
                adj_cost = graph[i][k] + graph[k][j]
                if adj_cost < graph[i][j]:
                    graph[i][j] = adj_cost
                    froms[i][j] = froms[k][j]
    
    has_negative_loop = False
    for i in range(n_nodes):
        if graph[i][i] < 0:
            has_negative_loop = True
            break

    return graph, froms, has_negative_loop

def restore_path(froms, start, goal):
    path = []
    cur = goal
    while cur != start:
        prev = froms[start][cur]
        path.append(prev)
        cur = prev
    path.append(start)
    path.reverse()
    return path

def resolve():
    N, M = list(map(int, input().split()))
    graph = [[float("inf") for _ in range(N)] for __ in range(N)]
    import copy
    exists = [[False for _ in range(N)] for __ in range(N)]
    for i in range(M):
        a, b, c = list(map(int, input().split()))
        graph[a-1][b-1] = c
        graph[b-1][a-1] = c
        exists[a-1][b-1] = True
        exists[b-1][a-1] = True
    costs, froms, _ = warshall_floyd(graph)

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            path = restore_path(froms, i, j)
            src = 0
            for dst in range(1, len(path)):
                exists[path[src]][path[dst]] = False
                exists[path[dst]][path[src]] = False
                src = dst
    
    print(sum(sum(exists, []))//2)



if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
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 i == k or j == k: continue
            if d[i][j] <= d[i][k] + d[k][j]:
                used[i][j] = True
                used[j][i] = True
# for i in range(n): print(used[i])
cnt = 0
for i in range(n):
    for j in range(n):
        if used[i][j]: continue
        cnt += 1
print(cnt//2)

Submission status: Wrong Answer

Solution code:
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]
# for i in range(n): print(used[i])
cnt = 0
for i in range(n):
    for j in range(n):
        if used[i][j]: continue
        cnt += 1
print(cnt//2)

Submission status: Wrong Answer

Solution code:
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

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]:
                if d[i][j] != INF:
                    used[i][j] = False
                    used[j][i] = False
                d[i][j] = d[i][k] + d[k][j]
# for i in range(n): print(used[i])
cnt = 0
for i in range(n):
    for j in range(n):
        if used[i][j]: continue
        cnt += 1
print(cnt//2)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
from copy import deepcopy
def main():
    N, M = map(int, input().split())
    to = [{} for _ in range(N)]
    edges = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        to[a][b] = c
        to[b][a] = c
        edges.append((a, b))
    
    INF = 10**9
    cost = [INF]*N
    def dijkstra(s):
        q = []
        heappush(q, (0, 0))
        cost[0] = 0
        while q:
            now_cost, now = heappop(q)
            for nv, length in to[now].items():
                nv_cost = now_cost + length
                if nv_cost < cost[nv]:
                    cost[nv] = nv_cost
                    heappush(q, (nv_cost, nv))
    
    dijkstra(0)
    original = deepcopy(cost)
    ans = 0
    for a, b in edges:
        c = to[a].pop(b)
        to[b].pop(a)

        cost = [INF]*N
        dijkstra(0)
        if cost == original:
            ans += 1

        to[a][b] = c
        to[b][a] = c
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[[]for _ in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  a,b=a-1,b-1
  g[a].append((c,b,i))
  g[b].append((c,a,i))
no_used=[1]*m
from heapq import heapify,heappop,heappush
def dks(t0):
  todo=[[0,t0,-1]]
  heapify(todo)
  seen=[0]*n
  while todo:
    d,t,i=heappop(todo)
    if seen[t]==1:continue
    seen[t]=1
    if i>-1:no_used[i]=0
    l=g[t]
    for d_,t_,i_ in l:
      if seen[t_]==0:
        heappush(todo,[d+d_,t_,i_])
for i in range(n):
  dks(i)
print(sum(no_used))

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
#import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n,m=map(int,input().split())
inf=10**9
nextm=[[inf]*n for _ in range(n)]
res=set()

for i in range(n):
    nextm[i][i]=0
for i in range(m):
    to,f,weight=map(int,input().split())
    nextm[to-1][f-1]=weight
    nextm[f-1][to-1]=weight
    res.add(max(to-1,f-1)*10000+min(to-1,f-1))

for k in range(n):
    for i in range(n):
        for j in range(n):
            if nextm[i][j]>nextm[i][k]+nextm[k][j]:
                nextm[i][j]=nextm[i][k]+nextm[k][j]
                if (max(i,j)*10000+min(i,j)) in res:
                    res.remove(max(i,j)*10000+min(i,j))
                res.add(max(i,k)*10000+min(i,k))
                res.add(max(j,k)*10000+min(j,k))
print(m-len(res))

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    cos = []
    row = []
    col = []
    for _ in range(m):
        a,b,c = map(int,ipt().split())
        row.append(a-1)
        col.append(b-1)
        cos.append(c)
    csr = csr_matrix((cos,(row,col)),shape=(n,n))
    d = dijkstra(csr,directed=False)
    ans = 0
    for i in range(m):
        csr = csr_matrix((cos[:i:]+cos[i+1::],(row[:i:]+row[i+1::],col[:i:]+col[i+1::])),shape=(n,n))
        di = dijkstra(csr,directed=False)
        if (di == d).all():
            ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    cos = []
    row = []
    col = []
    for _ in range(m):
        a,b,c = map(int,ipt().split())
        row.append(a-1)
        row.append(b-1)
        col.append(b-1)
        col.append(a-1)
        cos.append(c)
        cos.append(c)
    csr = csr_matrix((cos,(row,col)),shape=(n,n))
    d = dijkstra(csr)
    ans = 0
    for i in range(m):
        csr = csr_matrix((cos[:2*i:]+cos[2*i+2::],(row[:2*i:]+row[2*i+2::],col[:2*i:]+col[2*i+2::])),shape=(n,n))
        di = dijkstra(csr)
        if (di == d).all():
            ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,input().split()))
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
l=[np.array([0]*N) for i in range(N)]
for i in range(M):
   tmp=(list(map(int,input().split())))
   l[tmp[0]-1][tmp[1]-1]=tmp[2]
   l[tmp[1]-1][tmp[0]-1]=tmp[2]
l2=csr_matrix(l)
l2=floyd_warshall(l2)
print(l,l2)
ans=0
for i in range(N):
   for j in range(i):
      if l[i][j] != l2[i][j] and l[i][j] != 0:
         ans+=1
print(ans)