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

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a = input()
    print(" ".join(a.split(",")))
    return


def B():
    k, s = LI()
    ans = 0
    for i in range(k + 1):
        for j in range(k + 1):
            if 0 <= s - (i + j) <= k:
                ans += 1
    print(ans)
    return


def C():
    sx, sy, tx, ty = LI()
    UD = ("U", "D")
    LR = ("R", "L")
    ans = UD[sy > ty] * (abs(sy - ty)) + LR[sx > tx] * (abs(sx - tx))
    ans += UD[ty > sy] * (abs(sy - ty)) + LR[tx > sx] * (abs(sx - tx))
    ans += LR[tx > sx] + UD[sy > ty] * (abs(sy - ty) + 1) + LR[sx > tx] * (abs(sx - tx) + 1) + UD[ty > sy]
    ans += LR[sx > tx] + UD[ty > sy] * (abs(sy - ty) + 1) + LR[tx > sx] * (abs(sx - tx) + 1) + UD[sy > ty]
    print(ans)
    return


def D():
    def dij(s):
        dist = [inf for i in range(n)]
        dist[s] = 0
        q = [[0, s]]
        while q:
            d, f = heappop(q)
            for t, cost in edg[f]:
                if d + cost < dist[t]:
                    dist[t] = d + cost
                    heappush(q, [dist[t], t])
        return dist
    n, m = LI()
    ans = defaultdict(int)
    edg = defaultdict(list)
    for _ in range(m):
        a, b, c = LI_()
        c += 1
        edg[a].append((b, c))
        edg[b].append((a, c))
        ans[(a, b)] = False
        ans[(b, a)] = False
    for i in range(n):
        dis = dij(i)
        q = deque()
        q.append(i)
        while q:
            f = q.popleft()
            for t, cost in edg[f]:
                if dis[t] - dis[f] == cost:
                    ans[(t, f)] = True
                    q.append(t)
    ans = list(ans.values())
    print(ans.count(False) // 2)
    return


if __name__ == '__main__':
    D()

Solution (Python):
N, M = [int(_) for _ in input().split()]
INF = 10 ** 10
costs = [[INF] * 101 for _ in range(101)]

for i in range(N + 1):
    costs[i][i] = 0
paths = []
for i in range(M):
    a, b, c = [int(_) for _ in input().split()]
    costs[a][b] = c
    costs[b][a] = c
    paths.append((a, b, c))

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

for i in range(1, N + 1):
    paths2 = paths.copy()
    for p in paths:
        
        if costs[i][p[0]] >= INF or costs[i][p[1]] >= INF: continue
        if costs[i][p[0]] + p[2] == costs[i][p[1]]:
            paths2.remove(p)
    paths = paths2
print(len(paths))

Solution (Python):







INF = 10 ** 9

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


G = [[] for _ in range(N)]
for i in range(M):
    l, r, s = map(int, input().split()) 
    
    G[l-1] += [[s, r-1, i]]
    G[r-1] += [[s, l-1, i]]



def dijksrea(s): 
    import heapq
    s -= 1 
    d[s] = 0 
    pque = []
    heapq.heappush(pque, [0, s]) 

    while len(pque) != 0: 
        p = heapq.heappop(pque) 
        v = p[1] 
        if d[v] < p[0]: 
            continue
        for i in range(len(G[v])): 
            e = G[v][i]
            if d[e[1]] > d[v] + e[0]: 
                d[e[1]] = d[v] + e[0]
                prev[e[1]] = [v, e[2]]
                heapq.heappush(pque, [d[e[1]], e[1]]) 






def restore(g): 
    g -= 1 
    path.append(g)
    edge_num.append(prev[g][1])
    g = prev[g][0]
    while g != -1:
        path.append(g)
        
        edge_num.append(prev[g][1])
        g = prev[g][0]
    path.reverse()
    return path

ans_lst = [False] * M 

for i in range(1, N):
    d = [INF] * N 
    prev = [[-1, -1] for _ in range(N)] 
    dijksrea(i) 
    for j in range(i + 1, N + 1):
        path = []
        edge_num = []
        restore(j)
        for k in edge_num[:-1]:
            ans_lst[k] = True
        
        
        

print (ans_lst.count(False))

Solution (Python):
N, M = map(int, input().split())
g = [[float('INF')] * (N + 1) for _ in range(N + 1)]
abc = []
for _ in range(M):
    a, b, c = map(int, input().split())
    abc.append((a, b, c))
    g[a][b] = c
    g[b][a] = c
for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = 0
for a, b, c in abc:
    if g[a][b] != c:
        ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
inf=10**10
dist=[[inf for _ in [0]*n] for _ in [0]*n]
for i in range(n):dist[i][i]=0
for a,b,c in abc:
    dist[a-1][b-1]=c
    dist[b-1][a-1]=c
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]))

cnt=0
for a,b,c in abc:
    if dist[a-1][b-1]!=c:
        cnt+=1
        
print(cnt)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,m = map(int,input().split())
w = [[float('inf')]*n for _ in range(n)]
x = [list(map(int,input().split())) for _ in range(m)]
for a,b,c in x:
    w[a-1][b-1] = c
    w[b-1][a-1] = c

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

ans = 0
for i in x:
    a,b,c = i
    if w[a-1][b-1] < c:
        ans += 1
print(ans)

Solution (Python):
import heapq
N, M = map(int, input().split())
es = [[] for _ in range(N)]

INF = float("inf")
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))


def djkstra(start, n, es):
    
    
    

    
    costs = [INF] * n
    costs[start] = 0
    checked = [False] * n 
    hq = [(0, start)] 
    heapq.heapify(hq)
    while hq: 
        cost, v = heapq.heappop(hq) 
        if checked[v]:
            continue 
        checked[v] = True
        costs[v] = cost
        for to, c in es[v]: 
            if costs[to] <= cost + c:
                continue 
            heapq.heappush(hq, (cost+c, to)) 
        
    return costs


min_cost = [[] for _ in range(N)]
for i in range(N):
    min_cost[i] = djkstra(i,N,es)

ans = 0
for i in range(len(es)):
    for to, c in es[i]:
        if min_cost[i][to] < c:
            
            
            ans += 1

print(ans//2)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,m = map(int,input().split())
edge = [[] for _ in range(n)]
w = [[float('inf')]*n for _ in range(n)]
x = []
for _ in range(m):
    a,b,c = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    w[a-1][b-1] = c
    w[b-1][a-1] = c
    x.append([a,b,c])

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

ans = 0
for i in x:
    a,b,c = i
    if w[a-1][b-1] < c:
        ans += 1
print(ans)

Solution (Python):



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



"""
以下実行例
"""


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n,m = [int(i) for i in input().split()]

"""隣接行列の初期化"""
dist = [[float("inf")]*n for _ in [0]*n]
for i in range(n):
    dist[i][i] = 0

e = []
for _ in range(m):
    a,b,t = [int(i) for i in input().split()]
    dist[a-1][b-1] = t
    dist[b-1][a-1] = t
    e.append((a-1,b-1,t))

Floyd_Warshall(dist)

ans = 0
for a,b,t in e:
    if t > dist[a][b]: ans += 1

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    inf = 10 ** 5 + 1
    length_data = [[inf for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(edge_num):
        a, b, c = data[i]
        length_data[a][b] = c
        length_data[b][a] = c

    for i in range(1, node_num + 1):
        for j in range(1, node_num + 1):
            for k in range(1, node_num + 1):
                length_data[j][k] = min(length_data[j][k], length_data[j][i] + length_data[i][k])

    ans = 0
    for i in range(edge_num):
        a, b, c = data[i]
        if c > length_data[a][b]:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    inf = 10 ** 5 + 1
    length_data = [[inf for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(edge_num):
        a, b, c = data[i]
        length_data[a][b] = c
        length_data[b][a] = c

    for i in range(1, node_num + 1):
        for j in range(1, node_num + 1):
            for k in range(1, node_num + 1):
                length_data[j][k] = min(length_data[j][k], length_data[j][i] + length_data[i][k])

    ans = 0
    for i in range(edge_num):
        a, b, c = data[i]
        if c > length_data[a][b]:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
import heapq


def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    graph_data = defaultdict(set)
    weight_data = defaultdict(int)

    for i in range(edge_num):
        a, b, c = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)
        weight_data[(a, b)] = c
        weight_data[(b, a)] = c

    

    inf = 10 ** 5 + 1

    length_data = [[inf for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(1, node_num + 1):
        visit_flg = [0 for i in range(node_num + 1)]
        visit_flg[i] = 1
        length_data[i][i] = 0
        
        
        
        
        heap_list = []
        for ele in graph_data[i]:
            weight = weight_data[(i, ele)]
            heapq.heappush(heap_list, (weight, ele, i))

        while len(heap_list) > 0:
            now_weight, now_ele, pre_ele = heapq.heappop(heap_list)
            
            if visit_flg[now_ele]:
                continue
            visit_flg[now_ele] = 1
            length_data[i][now_ele] = length_data[i][pre_ele] + weight_data[(pre_ele, now_ele)]
            
            for next_ele in graph_data[now_ele]:

                if visit_flg[next_ele]:
                    continue
                next_weight = weight_data[(now_ele, next_ele)] + length_data[i][now_ele]
                heapq.heappush(heap_list, (next_weight, next_ele, now_ele))

            
            
            
            
            
        

    

    ans = 0
    for i in range(edge_num):
        a, b, c = data[i]
        if c > length_data[a][b]:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*M]
INF = 10**9
d = [[INF]*N for _ in [0]*N]
for i in range(N):
    d[i][i] = 0
for a,b,c in ABC:
    d[a-1][b-1] = c
    d[b-1][a-1] = c
def Warshall_Floyd(d,N=None):
    if N==None : N = len(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])
Warshall_Floyd(d,N)
print(sum(d[a-1][b-1]!=c for a,b,c in ABC))

Solution (Python):

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


INF = 10 ** 10
dist = [[INF] * N for _ 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)

Solution (Python):
import itertools

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


used = [False] * M
INF = 10**20
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]
edges = []
for i in range(M):
    a,b,c = list(map(int,input().split(" ")))
    cost[a][b] = c
    cost[b][a] = c
    edges.append((a,b,c))
for i in range(1,N+1):
    cost[i][i] = 0
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):

            cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j])
            cost[j][i] = min(cost[j][i], cost[j][k] + cost[k][i])
ans = 0
for k,edge in enumerate(edges):
            a,b,c = edge
            if  cost[a][b] !=c:
                ans += 1
print(ans)

Solution (Python):
import itertools

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


used = [False] * M
INF = 10**20
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]
edges = []
for i in range(M):
    a,b,c = list(map(int,input().split(" ")))
    cost[a][b] = c
    cost[b][a] = c
    edges.append((a,b,c))
for i in range(1,N+1):
    cost[i][i] = 0
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j])

ans = 0
for k,edge in enumerate(edges):
            a,b,c = edge
            if  cost[a][b] !=c:
                ans += 1
print(ans)

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

n,m=map(int,input().split())
edge=[list(map(int,input().split())) for _ in range(m)]
g=[[float('inf')]*(n+1) for _ in range(n+1)]
for a,b,c in edge:
  g[a][b]=c
  g[b][a]=c
d=floyd_warshall(g)
ans=0
for a,b,c in edge:
  for i in range(1,n+1):
    if d[i][a]+c==d[a][b]:
      break
  else:
    ans+=1
print(ans)

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

Solution (Python):
N, M = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(M)]

inf = 1000000
L = [[0] * N for _ in range(N)]
C = [[inf] * N for _ in range(N)]
for i in range(M):
  a, b, c = abc[i]
  a -= 1
  b -= 1
  C[a][b] = c
  C[b][a] = c

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

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

n = 0
for i in range(N):
  for j in range(N):
    if L[i][j] == 1:
      n += 1

print(M - ((N * (N - 1) // 2) - (n // 2)))

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

INF = float('inf')

vec1 = [[INF] * N for _ in range(N)]
vec2 = [[INF] * N for _ in range(N)]

for _ in range(M) :
    a, b, c = map(int, input().split())
    vec1[a-1][b-1] = vec1[b-1][a-1] = vec2[a-1][b-1] = vec2[b-1][a-1] = c
    
for i in range(N) :
    vec1[i][i] = vec2[i][i] = 0
    
for k in range(N) :
    for i in range(N) :
        for j in range(N) :
            vec1[i][j] = min(vec1[i][j], vec1[i][k] + vec1[k][j])

ret = 0            
for i in range(N) :
    for j in range(i+1, N) :
        if vec2[i][j] != INF and vec1[i][j] != vec2[i][j] :
            ret += 1

print(ret)

Solution (Python):
def warshall_floyd(d,N):
    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])

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

warshall_floyd(d,N)
cnt = 0
for edge in edges:
    if d[edge[0]][edge[1]] != edge[2]:
        cnt += 1

print(cnt)

Solution (Python):
import heapq


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

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

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

        
        if dist[src] < prov_cost:
            continue

        
        for dest in range(num):
            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                      

    return dist


n, m = map(int, input().split())
mat = [[float('inf')] * n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c
for i in range(n):
    mat[i][i] = 0
mat2 = []
for i in range(n):
    mat2.append(dijkstra(mat, i))
ans = 0
for i in range(n):
    for j in range(i, n):
        if mat[i][j] != float('inf') and mat[i][j] != mat2[i][j]:
            ans += 1
print(ans)

Solution (Python):
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        
        
        
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        
        
        
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]


N, M = map(int, input().split())
graph = Dijkstra()
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c, directed=False)

usedPaths = collections.defaultdict(set)
for i in range(N):
    for j in range(i+1, N):
        path = graph.getDijkstraShortestPath(i, j)
        if len(path) == 2:
            usedPaths[path[0]].add(path[1])
            usedPaths[path[1]].add(path[0])
        else:
            for k, v in enumerate(path[:-1]):
                usedPaths[v].add(path[k + 1])
                usedPaths[path[k + 1]].add(v)

ans = M - sum([len(a) for a in list(usedPaths.values())])//2
print(ans)

Solution (Python):

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


dic_edge_dist = {(i, j) : float("inf") for i in range(1, N + 1) for j in range(1, N + 1)}
for i in range(1, N + 1):
    dic_edge_dist[(i, i)] = 0

list_edge = []

def warshall_floyd(dic_edge_dist):
    dic_shortest_dist = dic_edge_dist.copy()
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                dic_shortest_dist[(j, k)] = min(dic_shortest_dist[(j, k)], dic_shortest_dist[(j, i)] + dic_shortest_dist[(i, k)])
    return dic_shortest_dist


for _ in range(M):
    
    a, b, c = map(int, input().split())
    
    dic_edge_dist[(a, b)] = c
    dic_edge_dist[(b, a)] = c
    
    list_edge.append((min(a, b), max(a, b)))

dic_shortest_dist = warshall_floyd(dic_edge_dist)
    
edge_count = 0
for i, j in list_edge:
    for k in range(1, N + 1):
        if dic_shortest_dist[(k, i)] + dic_edge_dist[(i, j)] == dic_shortest_dist[(k, j)]:
            edge_count += 1
            break
        if dic_shortest_dist[(k, j)] + dic_edge_dist[(j, i)] == dic_shortest_dist[(k, i)]:
            edge_count += 1
            break

print(len(list_edge) - edge_count)

Solution (Python):
def warshall_floyd(d,n):
    
    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 = [int(x) for x in input().split()]
INF = float('inf')
edges = []
d = [[INF]*N for _ in range(N)]
for _ in range(M):
    a,b,c = [int(x) for x in input().split()]
    a-=1
    b-=1
    d[a][b]=c
    d[b][a]=c
    edges.append([a,b,c])

warshall_floyd(d,N)
cnt = 0
for e in edges:
    if(d[e[0]][e[1]]!=e[2]):
        cnt+=1
print(cnt)

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]

g = Graph()
N,M = list(map(int, input().split()))
INF = 10**9+7
A = [[INF if i!=j else 0 for i in range(N)] for j in range(N)]
S=[]
E=[]
W=[]

for i in range(M):
    s,e,w=list(map(int,input().split()))
    g.add_edge(s-1, e-1, w)
    g.add_edge(e-1, s-1, w)
    S.append(s-1)
    E.append(e-1)
    W.append(w)

for i in range(N):
    d = Dijkstra(g, i)
    for j in range(i+1,N):
        dist = d.shortest_distance(j)
        A[i][j] = dist
        A[j][i] = dist
        
ans=M
for i in range(M):
    shortest = False
    for j in range(N):
        if A[j][S[i]] + W[i] == A[j][E[i]]:
            shortest = True
    if shortest:
        ans-=1

print(ans)

Solution (Python):
import numpy as np
import copy
from collections import defaultdict
from heapq import heappush, heappop


def djkstra(adj_mat, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = np.argwhere(adj_mat[u] > 0).flatten()
        for v in vs:
            weight = adj_mat[u, v]
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))
    visited_edges = np.zeros_like(adj_mat, dtype=np.int32)

    for v in range(adj_mat.shape[0]):
        u = prev[v]
        if u is not None:
            visited_edges[u, v] = 1
            visited_edges[v, u] = 1

    return visited_edges


def main():
    N, M = map(int, input().split())
    adj_mat = np.zeros((N, N), dtype=np.int32)
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj_mat[a, b] = c
        adj_mat[b, a] = c

    visited_edge_count = np.sum(
        np.concatenate([djkstra(adj_mat, src)[np.newaxis, :, :] for src in range(N)], axis=0), axis=0)
    out = np.sum(np.logical_and(adj_mat > 0, visited_edge_count == 0)) // 2
    print(out)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
INF = 10**9
N, M = map(int, input().split())
d = [[INF] * (N+1) for i in range(N+1)]
for i in range(N+1):
    d[i][i] = 0
es = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b], d[b][a] = c, c
    es[i] = (a, b, c)
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 = M
for k in range(M):
    i, j, c = es[k]
    for s in range(1, N+1):
        if d[s][i] + c == d[s][j]:
            ans -= 1
            break
print(ans)

Solution (Python):
n,m = map(int,input().split())
D = []
ans = 0
for i in range(n):
    t = [float('inf')]*n
    t[i] = 0
    D.append(t)
L = []
for i in range(m):
    a,b,c = map(int,input().split())
    D[a-1][b-1] = c
    D[b-1][a-1] = c
    L.append([a,b,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])
for i in range(m):
    a,b,c = L[i][0],L[i][1],L[i][2]
    if D[a-1][b-1] != c:
        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())
abc=[]
d=[[10**9+7 for i in range(n)] for j in range(n)]
l=[[10**9+7 for i in range(n)] for j in range(n)]
for i in range(m):
    tmp=[int(j) for j in input().split()]
    abc.append(tmp)
    d[tmp[0]-1][tmp[1]-1]=tmp[2]
    d[tmp[1]-1][tmp[0]-1]=tmp[2]
    l[tmp[0]-1][tmp[1]-1]=tmp[2]
    l[tmp[1]-1][tmp[0]-1]=tmp[2]

for i in range(n):
    d[i][i]=0
    l[i][i]=0
d=warshall_floyd(d)

ans=0
for i in range(n):
    for j in range(n):
        if d[i][j]!=l[i][j] and l[i][j]!=10**9+7:
            ans+=1
print(ans//2)

Solution (Python):
N,M=list(map(int, input().split()))
graph=[]
for i  in range(M):
  graph.append(list(map(int, input().split())))

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



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

for n in range(N):

  for time in range(N):
    judge = 0
    for m in range(M):
      if dist[n][graph[m][0]-1]-dist[n][graph[m][1]-1] > graph[m][2]:
        dist[n][graph[m][0]-1]=dist[n][graph[m][1]-1]+graph[m][2]
        judge=1
      elif dist[n][graph[m][1]-1]-dist[n][graph[m][0]-1] > graph[m][2]:
        dist[n][graph[m][1]-1]=dist[n][graph[m][0]-1]+graph[m][2]
        judge=1
    if judge == 0:
      break

num = 0

for m in range(M):
  if dist[graph[m][0]-1][graph[m][1]-1] < graph[m][2]:
    num+=1
    

  
    
print(num)