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.

Solution (Python):
N, M = map(int, input().split())
d = [[float('inf') for _ in range(N + 1)] for _ in range(N + 1)]
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c
    edges.append((a, b, c))

for i in range(1, N + 1):
    d[i][i] = 0
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])

ans = 0
for edge in edges:
    if edge[2] != d[edge[0]][edge[1]]:
        ans += 1

print(ans)

Solution (Python):
def main():
    inf =1000000000
    N,M = map(int,input().split())
    a,b,c = [],[],[]
    dist = [[0 if i ==j else inf for j in range(N)] for i in range(N)]
    for _ in range(M):
        x,y,z = map(int,input().split())
        a.append(x-1)
        b.append(y-1)
        c.append(z)

    for i in range(M):
        dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i])
        dist[b[i]][a[i]] = min(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 = M
    for i in range(M):
        if dist[a[i]][b[i]] == c[i]:
            ans -=1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N,M=[int(i) for i in input().split()]
edges=[[2**60 for i in range(N)] for j in range(N)]
for i in range(M):
    a,b,c=[int(i) for i in input().split()]
    a-=1
    b-=1
    edges[a][b]=edges[b][a]=c

mini=[[edges[i][j] for i in range(N)] for j in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            mini[i][j]=min(mini[i][j],mini[i][k]+mini[k][j])
res=0
for r in range(N):
    for l in range(r):
        
        if edges[l][r] != 2**60 and mini[l][r]<edges[l][r]:
            res+=1
print(res)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall


n, m = map(int, input().split())
d = [[0 if i == j else float('inf') for i in range(n)]
     for j in range(n)]
g = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    g[a].append((b, c))
    g[b].append((a, c))

gf = floyd_warshall(csgraph=d)


cnt = 0
for i in range(n):
    for j, cost in g[i]:
        used = False
        if i > j:
            continue
        for k in range(n):
            if gf[i][k] == cost + gf[k][j]:
                used = True
                break
        if used is False:
            cnt += 1
print(cnt)

Solution (Python):
N, M = map(int, input().split())

A = []
B = []
C = []

inf = 1*10**7
max_n = 110
G = [[inf] * max_n for i in range(max_n)]
for i in range(N):
    G[i][i] = 0


for i in range(M):
    a, b, c = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)
    G[A[i]][B[i]] = C[i]
    G[B[i]][A[i]] = C[i]

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

ans = 0
for i in range(M):
    if (G[A[i]][B[i]] < C[i]):
        ans += 1




print(ans)

Solution (Python):
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

N, M = map(int, input().split())
d = [[float('inf') for i in range(N)] for i in range(N)]
edges = []

for i in range(M):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    edges.append([a,b,c])

warshall_floyd(d)



cnt = 0
for edge in edges:
    if d[edge[0]][edge[1]] != edge[2]:
        cnt += 1

print(cnt)

Solution (Python):
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

INF = float('inf')

def sol():
    N, M = map(int, input().split())

    edges = []

    for _ in range(M):
        fr, to, cost = map(int, input().split())
        fr -= 1
        to -= 1
        edges.append((fr, to, cost))

    graph = [[INF] * N for _ in range(N)]
    for fr, to, cost in edges:
        graph[fr][to] = cost

    graph = csgraph_from_dense(graph, null_value=INF)

    dist = floyd_warshall(graph, directed=False)
    ans = (graph > dist).sum()
    print(ans)

sol()

Solution (Python):
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 d2[i][j] != 100000 and d[i][j]!=d2[i][j]:
      count+=1
print(count)

Solution (Python):


import heapq,sys
input=sys.stdin.readline
INF=float('inf')
heappush=heapq.heappush
heappop=heapq.heappop

n,m=map(int,input().split())
graph=[[] for _ in range(n)]
minway=[]
bridges=[]
ans=0
for _ in range(m):
    a,b,c=map(int,input().split())
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))
    bridges.append((a-1,b-1,c))

def dijkstra(graph,n,start):
    Q=[]
    distance=[]
    dappend=distance.append
    for i in range(n):
        dappend([INF,i])
    distance[start][0]=0
    for j in distance:
        heappush(Q,j)
    while Q!=[]:
        q=heappop(Q)
        for v,vl in graph[q[1]]:
            alt=vl+q[0]
            if alt<distance[v][0]:
                distance[v][0]=alt
                heappush(Q,[alt,v])
    return distance

for k in range(n):
    minway.append(dijkstra(graph,n,k))

for l in bridges:
    x,y,z=l[0],l[1],l[2]
    flag=True
    for p in range(n):
        if minway[x][p][0]+z==minway[y][p][0] or minway[y][p][0]+z==minway[x][p][0]:
            flag=False
            break
    if flag:
        ans+=1

print(ans)

Solution (Python):
import heapq,sys
input=sys.stdin.readline
INF=float('inf')
heappush=heapq.heappush
heappop=heapq.heappop

n,m=map(int,input().split())
graph=[[] for _ in range(n)]
minway=[]
bridges=[]
ans=0
for _ in range(m):
    a,b,c=map(int,input().split())
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))
    bridges.append((a-1,b-1,c))

def dijkstra(graph,n,start):
    Q=[]
    distance=[]
    dappend=distance.append
    for i in range(n):
        dappend([INF,i])
    distance[start][0]=0
    for j in distance:
        heappush(Q,j)
    while Q!=[]:
        q=heappop(Q)
        for v,vl in graph[q[1]]:
            alt=vl+q[0]
            if alt<distance[v][0]:
                distance[v][0]=alt
                heappush(Q,[alt,v])
    return distance

for k in range(n):
    minway.append(dijkstra(graph,n,k))

for l in bridges:
    x,y,z=l[0],l[1],l[2]
    flag=True
    for p in range(n):
        if minway[x][p][0]+z==minway[y][p][0] or minway[y][p][0]+z==minway[x][p][0]:
            flag=False
            break
    if flag:
        ans+=1

print(ans)

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re




import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]



def solve(G):
    N = len(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

def main():
    N, M = l_inpl()
    G = create_grid(N, N, INF)

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

    a, b, c = [], [], []
    for _ in range(M):
        ai, bi, ci = l_inpl()
        ai, bi = ai-1, bi-1
        a.append(ai)
        b.append(bi)
        c.append(ci)
        G[ai][bi] = ci
        G[bi][ai] = ci
    
    G = solve(G)

    ans = M
    for i in range(M):
        flag = False
        for j in range(N):
            
            
            if G[j][a[i]]+c[i] == G[j][b[i]]:
                flag = True
        if flag:
            ans -= 1
    
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re




import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]



def solve(G):
    N = len(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

def main():
    N, M = l_inpl()
    G = create_grid(N, N, INF)

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

    a, b, c = [], [], []
    for _ in range(M):
        ai, bi, ci = l_inpl()
        ai, bi = ai-1, bi-1
        a.append(ai)
        b.append(bi)
        c.append(ci)
        G[ai][bi] = ci
        G[bi][ai] = ci
    
    G = solve(G)

    ans = M
    for i in range(M):
        flag = False
        for j in range(N):
            if G[j][a[i]]+c[i] == G[b[i]][j]:
                flag = True
        if flag:
            ans -= 1
    
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):

import sys

def WarshallFloyd(V: int, cost: "List[List[int]]"):
    """
    全ての頂点対の間の最短距離を求めます。
    ==============
    V: 頂点数
    cost: 隣接行列(辺が存在しない部分はINF)
    --------------
    cost: 最短距離の行列
    """
    INF = 1e18
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    INF = 1e18
    cost = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(M):
        cost[a[i] - 1][b[i] - 1] = c[i]
        cost[b[i] - 1][a[i] - 1] = c[i]
    for i in range(N):
        cost[i][i] = 0
    cost = WarshallFloyd(N, cost)
    
    counter = 0
    for i in range(M):
        flag = False
        for j in range(N):
            if cost[j][a[i]-1] + c[i] == cost[j][b[i]-1]:
                flag = True
        if not flag:
            counter += 1
    print(counter)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    c = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

Solution (Python):
n, m = [ int(v) for v in input().split() ]
shortest_distance = [ [ 10**8 for i in range(n) ] for j in range(n) ]
distance_path = [ [ [] for i in range(n) ] for j in range(n) ]

for i in range(m):
    a, b, c = [ int(v) for v in input().split() ]
    shortest_distance[a-1][b-1] = c
    shortest_distance[b-1][a-1] = c
    distance_path[a-1][b-1].append(i)
    distance_path[b-1][a-1].append(i)


for k in range(n):
    for i in range(n):
        for j in range(n):
            if i != j:
                if shortest_distance[i][j] > shortest_distance[i][k] + shortest_distance[k][j]:
                    shortest_distance[i][j] = shortest_distance[i][k] + shortest_distance[k][j]
                    distance_path[i][j] = distance_path[i][k] + distance_path[k][j]


path_used = [ False for i in range(m) ]
for i in distance_path:
    for j in i:
        for k in j:
            path_used[k] = True
print(path_used.count(False))

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

def solve():
  n,m = (int(i) for i in input().split())
  route = [[float("INF")]*n for _ in range(n)]
  for i in range(n):
    route[i][i] = 0
    
  A = []
  B = []
  cost = []
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    route[a-1][b-1] = c
    route[b-1][a-1] = c
    A.append(a-1)
    B.append(b-1)
    cost.append(c)

  
  for k in range(n):
    for i in range(n):
      for j in range(n):
        route[i][j] = min(route[i][j],route[i][k]+route[k][j])
        
  ans = 0
  for i in range(m):
    if cost[i] > route[A[i]][B[i]]:
      ans += 1
  print(ans)
        
solve()

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  route = Graph()
  tmp = [[0]*n for _ in range(n)]
  
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    route.add_edge(a-1,b-1,c)
    route.add_edge(b-1,a-1,c)
    tmp[a-1][b-1] = 1

  
  for i in range(n):
    
    ds = Dijkstra(route,i)
    for j in range(n):
      if not i== j:
        query = ds.shortest_path(j)
        for k in range(len(query)-1):
            tmp[query[k]][query[k+1]] = 0
  ans = 0
  for i in range(n):
    ans += sum(tmp[i])
  print(ans)
        
solve()

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

def solve():
  n,m = (int(i) for i in input().split())
  route = Graph()
  tmp = [[0]*n for _ in range(n)]
  
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    route.add_edge(a-1,b-1,c)
    route.add_edge(b-1,a-1,c)
    tmp[a-1][b-1] = 1

  
  for i in range(n):
    
    ds = Dijkstra(route,i)
    for j in range(n):
      if not i== j:
        query = ds.shortest_path(j)
        for k in range(len(query)-1):
            tmp[query[k]][query[k+1]] = 0
  ans = 0
  for i in range(n):
    ans += sum(tmp[i])
  print(ans)
        
solve()

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

def solve():
  n,m = (int(i) for i in input().split())
  route = Graph()
  tmp = [[0]*n for _ in range(n)]
  
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    route.add_edge(a-1,b-1,c)
    route.add_edge(b-1,a-1,c)
    tmp[a-1][b-1] = 1

  
  for i in range(n):
    
    ds = Dijkstra(route,i)
    for j in range(n):
      if not i== j:
        query = ds.shortest_path(j)
        for k in range(len(query)-1):
            tmp[query[k]][query[k+1]] = 0
  ans = 0
  for i in range(n):
    ans += sum(tmp[i])
  print(ans)
        
solve()

Solution (Python):
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())


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)
    
    if d < w:
        count += 1

print(count)

Solution (Python):
from copy import deepcopy

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

INF = 10000000
D = [[INF for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    D[a-1][b-1] = c
    D[b-1][a-1] = c

F = deepcopy(D)
for k in range(N):
    for i in range(N):
        for j in range(N):
            F[i][j] = min(F[i][j], F[i][k]+F[k][j])
a = 0
for i in range(N):
    for j in range(N):
        if D[i][j] == F[i][j]:
            a += 1
a //= 2
print(M-a)

Solution (Python):
def main():
    def dijkstra_back(s,t):
        prev = [s] * n
        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 i in range(n):
                if d[i] > d[v] + cost[v][i]: 
                    d[i] = d[v] + cost[v][i]
                    prev[i] = v
        path = [t]
        while prev[t] != s:
            path.append(prev[t])
            prev[t] = prev[prev[t]]
        path.append(s)
        path = path[::-1]
        return path
    
    n,m = map(int,input().split())
    route = [tuple(map(int,input().split())) for _ in range(m)]
    INF = float('inf')
    cost = [[INF for i in range(n)] for i in range(n)] 
    for i in route:
        cost[i[0]-1][i[1]-1] = i[2]
        cost[i[1]-1][i[0]-1] = i[2]
    
    used_ways = set([])
    for i in range(n):
        for j in range(n):
            if i < j:
                way = dijkstra_back(i,j)
                for k in range(len(way)-1):
                    used_ways.add(tuple(sorted([way[k],way[k+1]])))
    route_set = set([])
    for i in route:
        route_set.add(tuple(sorted([i[0]-1,i[1]-1])))
    print(len(route_set-used_ways))

if __name__ == '__main__':
    main()

Solution (Python):
import collections
dic=collections.defaultdict(int)
n,m=map(int,input().split())
INF=float("inf")
d=[[INF for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    d[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    a,b=sorted([a,b])
    dic[(a,b)]=1
    d[a][b]=c
    d[b][a]=c
ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            t=min(d[j][k],d[j][i]+d[i][k])
            if d[j][k]>t:
                d[j][k]=t
                t=tuple(sorted([j,k]))
                if dic[t]:
                    ans+=1
                    dic[t]=0
print(ans)

Solution (Python):
N, M = map(int, input().split())
D = [[float("inf")]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
abcs = []
for i in range(M):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  abcs.append((a, b, c))
  D[a][b] = c
  D[b][a] = c
for k in range(N):
  for a in range(N):
    for b in range(N):
      D[a][b] = min(D[a][b], D[a][k]+D[k][b])

r = 0
for m in range(M):
  a, b, c = abcs[m]
  if c > D[a][b]:
    r += 1
print(r)

Solution (Python):
def sol():
    N, M = map(int, input().split())

    minDist = [[float('inf') for _ in range(N)] for _ in range(N)]
    edges = set([])

    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        minDist[a][b] = c
        minDist[b][a] = c
        edges.add((min(a, b), max(a, b)))

    noEdge = set([])

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if minDist[i][j] > minDist[i][k] + minDist[k][j]:
                    minDist[i][j] = minDist[i][k] + minDist[k][j]
                    noEdge.add((min(i, j), max(i, j)))

    nessEdge = edges - noEdge
    print(M - len(nessEdge))

sol()

Solution (Python):
import scipy.sparse.csgraph
L=lambda:list(map(int,input().split()))
n,m=L()
s=[n*[float("inf")]for _ in range(n)]
d=[L()for _ in range(m)]
for a,b,c in d:s[a-1][b-1]=s[b-1][a-1]=c
x=scipy.sparse.csgraph.floyd_warshall(s)
print(sum(c!=x[a-1][b-1]for a,b,c in d))

Solution (Python):
import scipy.sparse.csgraph;L=lambda:list(map(int,input().split()));n,m=L();s=[n*[float("inf")]for _ in range(n)];d=[L()for _ in range(m)]
for a,b,c in d:s[a-1][b-1]=s[b-1][a-1]=c
x=scipy.sparse.csgraph.floyd_warshall(s);print(sum(c!=x[a-1][b-1]for a,b,c in d))

Solution (Python):


from heapq import heappop, heappush

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


g = [[] for i in range(N)]
e = []
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))
    e.append((a-1, b-1, c))

def dijkstra(nodeCnt, start, edges):

    
    costs = [-1 for i in range(nodeCnt)]

    
    done = [False for i in range(nodeCnt)]

    
    q = []

    costs[start] = 0
    heappush(q, (0, start))

    while len(q) > 0:
        
        doneNode = heappop(q)[1]

        
        done[doneNode] = True

        
        for to,edge_cost in edges[doneNode]:
            cost = costs[doneNode] + edge_cost
            if costs[to] < 0 or cost < costs[to]:
                costs[to] = cost
                if to not in q:
                    heappush(q, (cost, to))

    return costs

dist = [dijkstra(N, i, g) for i in range(N)]




ans = 0
for i, j, cost in e:
    isUsed = False
    for s in range(N):
        if dist[s][i] + cost == dist[s][j]:
            isUsed = True
            break
    if not isUsed:
        ans += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N, M = map( int, input().split())
    d = dict()
    for i in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = c
    V = [[1000000]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for (s,t), c in d.items():
        V[s][t] = V[t][s] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if V[i][k] + V[k][j] < V[i][j]:
                    V[i][j] = V[i][k] + V[k][j]
    ans = 0
    for (s,t), c in d.items():
        check = False
        for k in range(N**2):
            i = k//N
            j = k%N
            if V[i][s] + c + V[t][j] == V[i][j]:
                check = True
                break
        if check == False:
            ans += 1

    print(ans)
                
if __name__ == '__main__':
    main()