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: Time Limit Exceeded

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

N, M = map(int, input().split())
graph = [dict() for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
used_edge = set()
for i in range(N):
    di = Dijkstra(graph, i)

    for j in range(N):
        if i == j:
            continue
        di.goal_point = j
        path = di.execute()
        for p in range(len(path)-1):
            used_edge.add((path[p], path[p+1]))
            used_edge.add((path[p+1], path[p]))
print(M-len(used_edge)//2)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
infty = int(1E9)
d = [[infty for i in range(n)] for j in range(n)]
edges = []

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

for _ in range(m):
  x, y, c = map(int, input().split())
  x -= 1; y -= 1
  edges.append((x, y, c))
  d[x][y] = d[y][x] = c

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

ans = 0
for e in edges:
  x, y, c = e;
  need = False
  for i in range(n):
    for j in range(n):
      if d[i][j] == d[i][x] + d[j][y] + c:
        need = True
        break
  ans += not need

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

length = {}
history = []

for _ in range(M):
    a, b, c = map(int, input().split())
    length[str(min(a, b)) + str(max(a, b))] = c

for i in range(1, N):
    for j in range(i+1, N+1):
        dic = {}
        if str(i) + str(j) in length:
            dic[str(i) + str(j)] = length[str(i) + str(j)]

        array1 = [k for k in range(1, N+1)]
        array1.remove(i)
        array1.remove(j)

        for k in range(1, len(array1)+1):
            array2 = list(permutations(array1, k))
            for l in array2:
                case = ''
                for m in l:
                    case += str(m)
                case = str(i) + case + str(j)
                num = 0
                flag = True
                for m in range(len(case)-1):
                    x = str(min(int(case[m]), int(case[m+1]))) + str(max(int(case[m]), int(case[m+1])))
                    if x in length:
                        num += length[x]
                    else:
                        flag = False
                        break

                if flag:
                    dic[case] = num

        min_case = min(dic, key=dic.get)
        for k in range(len(min_case)-1):
            x = str(min(int(min_case[k]), int(min_case[k+1]))) + str(max(int(min_case[k]), int(min_case[k+1])))
            if x not in history:
                history.append(x)

print(M - len(history))

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d



V, E=map(int,input().strip().split(' '))
inf=10**9
cost=[[inf]*V for i in range(V)]
edge=[]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
    edge.append([fr-1,to-1])
    
d=[]
for i in range(V):
    d.append(dijkstra(i))

cand=E
for i in range(E):
    fl=False
    for s in range(V):
        for t in range(V):
            if d[s][edge[i][0]]+cost[edge[i][0]][edge[i][1]]+d[edge[i][1]][t]==d[s][t]:
                cand-=1
                fl=True
                break
        if fl:
            break

print(cand)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
Islands=[[] for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1].append([b-1,c])
  Islands[b-1].append([a-1,c])
  Edge.append([a-1,b-1,c])
for m in range(M):
  a=Edge[m][0]
  b=Edge[m][1]
  c_m=Edge[m][2]
  List=[[a,0]]
  for l in List:
    c_base=l[-1]
    c=c_base
    if l[-2]==b:
      if c_m>c:
        S+=1
        break
    else:        
      for n in Islands[l[-2]]:
        if n[0] in l[0:-1]:
          pass
        else:
          c+=n[1]
          List.append(l[0:-1]+[n[0],c])  
          c=c_base
print(S)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
Islands=[[] for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1].append([b-1,c])
  Islands[b-1].append([a-1,c])
  Edge.append([a-1,b-1])
for m in range(M):
  a=Edge[m][0]
  b=Edge[m][1]
  for i in Islands[a]:
    if i[0]==b:
      c_m=i[1]
  List=[[a,0]]
  for l in List:
    c_base=l[-1]
    c=c_base
    if l[-2]==b:
      if c_m>c:
        S+=1
        break
    else:        
      for n in Islands[l[-2]]:
        if n[0] in l[0:-1]:
          pass
        else:
          c+=n[1]
          List.append(l[0:-1]+[n[0],c])  
          c=c_base
print(S)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy

def Dijk(s): #始点Sのダイクストラ, すべての行先への最短距離のリストを返す
    Cost = [float("inf") for i in range(N)]
    Cost[s] = 0
    Q = [[0, s]]
    V = [False for i in range(N)]
    while Q:
        Next = heapq.heappop(Q)
        V[Next[1]] = True
        for node in Edge[Next[1]]:
            if V[node[1]] == False:
                Cost[node[1]] = min(Next[0] +node[0], Cost[node[1]])
                heapq.heappush(Q, [Cost[node[1]], node[1]])
    return Cost


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

Ans = 0
Length = []
for i in range(N):
    Length.append(Dijk(i))

for s in Search:
    for i in range(N):
        if Length[i][s[0]] + s[2] == Length[i][s[1]]:
            break
    else:
        Ans += 1

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy

def Dijk(s, t):
    Cost = [-1 for i in range(N)]
    Cost[s] = 0
    Q = copy.deepcopy(Edge[s])
    for node in Q:
        Cost[node[1]] = node[0]
    V = [False for i in range(N)]
    V[s] = True
    while Q:
        Next = heapq.heappop(Q)
        V[Next[1]] = True
        for node in Edge[Next[1]]:
            if V[node[1]] == False:
                if Cost[node[1]] == -1:
                    Cost[node[1]] = Next[0] + node[0]
                else:
                    Cost[node[1]] = min(Next[0] +node[0], Cost[node[1]])
                heapq.heappush(Q, [Cost[node[1]], node[1]])
    return Cost[t]


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

Ans = 0
for s in Search:
    for i in range(N):
        if Dijk(i, s[0]) + s[2] == Dijk(i, s[1]):
            break
    else:
        Ans += 1

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

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

        if dist[src] < prov_cost:
            continue

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
INF = 10**10
n,m = map(int, input().split())
d = [[INF for _ in range(n)] for _ in range(n)]
el = []

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i==j:
                d[i][j] = 0

            d[i][j] = min(d[i][j], d[i][k]+d[k][j])

ret = 0
for ei in range(m):
    a = el[ei][0]
    b = el[ei][1]
    c = el[ei][2]
    flag = False
    for s in range(n):
        for t in range(n):
            if d[s][a]+c+d[b][t]==d[s][t]:
                flag = True
                break
        if flag:
            break
    if not flag:
        ret += 1
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = [int(i) for i in input().split()]

INF = int(1e18)
G = np.full((N, N), INF)
for i in range(N):
    G[i][i] = 0

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


rng = range(N)
for k in rng:
    for i in rng:
        for j in range(i + 1, N):
            x = G[i][k] + G[k][j]
            if G[i][j] > x:
                G[i][j] = G[j][i] = x;
                
ans = 0
for (a, b, c) in edge:
    flag = False
    for s in rng:
        if flag:
            break;
        for t in rng:
            flag = flag | (G[s][t] == G[s][a] + c + G[b][t])

    ans = ans + (flag == False)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = [int(i) for i in input().split()]

INF = int(1e18)
G = np.full((N, N), INF)
for i in range(N):
    G[i][i] = 0

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


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 (a, b, c) in edge:
    flag = False
    for s in range(N):
        for t in range(N):
            flag = flag | (G[s][t] == G[s][a] + c + G[b][t])

    ans = ans + (flag == False)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

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

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


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

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        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 main():
    n, m= map(int,input().split())
    g = Graph()

    inputs = [0]*m

    for i in range(m):
        lst = [int(i) for i in input().split()]
        inputs[i]=lst
        g.add_edge(lst[0], lst[1],lst[2])
        g.add_edge(lst[1], lst[0],lst[2])

    lst = [[0 for i in range(n+1)] for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i != j and lst[j][i] == 0:
                d = Dijkstra(g,i)
                lst[i][j] = d.shortest_distance(j)

    #print(lst)
    #print(inputs)

    ans = 0
    for i in range(m):
        if lst[min(inputs[i][0],inputs[i][1])][max(inputs[i][0],inputs[i][1])] < inputs[i][2]:
            ans+=1

    print(ans)

if __name__ == "__main__":
        main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

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

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


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

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        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 main():
    n, m= map(int,input().split())
    g = Graph()

    inputs = [0]*m

    for i in range(m):
        lst = [int(i) for i in input().split()]
        inputs[i]=lst
        g.add_edge(lst[0], lst[1],lst[2])
        g.add_edge(lst[1], lst[0],lst[2])

    lst = [[0 for i in range(n+1)] for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i != j:
                d = Dijkstra(g,i)
                lst[i][j] = d.shortest_distance(j)

    ans = 0
    for i in range(m):
        if lst[inputs[i][0]][inputs[i][1]] < inputs[i][2]:
            ans+=1

    print(ans)

if __name__ == "__main__":
        main()

Submission status: Time Limit Exceeded

Solution code:

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        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 main():
    n, m= map(int,input().split())
    g = Graph()

    inputs = [0]*m

    for i in range(m):
        lst = [int(i) for i in input().split()]
        inputs[i]=lst
        g.add_edge(lst[0], lst[1],lst[2])
        g.add_edge(lst[1], lst[0],lst[2])

    lst = [[0 for i in range(n+1)] for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i != j:
                d = Dijkstra(g,i)
                lst[i][j] = d.shortest_distance(j)

    ans = 0
    for i in range(m):
        if lst[inputs[i][0]][inputs[i][1]] < inputs[i][2]:
            ans+=1

    print(ans)

if __name__ == "__main__":
        main()

Submission status: Time Limit Exceeded

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        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]


n, m = map(int,input().split())
inputs =[]

for i in range(m):
    a, b,c = map(int,input().split())
    inputs.append((a,b,c))

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)

#print('最短経路: {}'.format(d.shortest_path(3)))
#print('最短距離: {}'.format(d.shortest_distance(3)))


lst = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        if i != j:
            d = Dijkstra(g, i)
            lst[i][j]= d.shortest_distance(j)

#print(lst)

ans =0
for i in range(m):
    if lst[inputs[i][0]][inputs[i][1]] < inputs[i][2]:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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())
abc = []
for i in range(m):
    abc.append(list(map(int, input().split())))

d = [[0 if i == j else sys.maxsize for j in range(n)] for i in range(n)]

for i in range(m):
    a, b, c = abc[i]
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c

d = warshall_floyd(d, n)

cnt = 0
for i in range(m):
    a, b, c = abc[i]

    flag = False
    for s in range(n):
        for t in range(n):
            if (d[s][a - 1] + c + d[b - 1][t]) == d[s][t]:
                flag = True
                break
        if flag:
            break
    if not flag:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
class MakeGraph:
    
    # 隣接行列もしくは隣接リストの初期化
    # node_num：ノード数
    # isMat：隣接行列(True) / 隣接リスト(False)
    def __init__(self, node_num:int, isMat:bool) -> None:
        self.n = node_num
        self.isMat = isMat

        # 隣接行列の初期化
        if self.isMat:
            INF = float("inf")
            self.graph = [[INF for _ in range(self.n)] for _ in range(self.n)]
    
        # 隣接リストの初期化
        else:
            self.graph = [[] for _ in range(self.n)]

    # エッジの追加
    # frm, to：起点ノード, 終点ノード
    # dist：frm→toへのコスト
    def add_undr_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        self.graph[to][frm] = dist
        
    def add_drct_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        
    def add_undr_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))
        self.graph[to].append((dist, frm))
        
    def add_drct_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))

                
    # 完成したグラフを取り出す
    def get_graph(self) -> list:
        return self.graph
    
N,M = map(int, input().split())
ABC = []
for i in range(M):
    ABC.append(tuple(map(int, input().split())))
    
graphMaker = MakeGraph(N,True)
add_edge = graphMaker.add_undr_edge_mat
for a,b,c in ABC:
    add_edge(a-1, b-1, c)

graph = graphMaker.get_graph()
dist = graphMaker.get_graph()

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
            
ans = 0
for a,b,cost in ABC:
    a -= 1
    b -= 1
    flag = 1
    for frm in range(N):
        for to in range(N):
            if frm == to:
                continue

            if dist[frm][a]+cost+dist[b][to] == dist[frm][to]:
                flag = 0
                    
    ans += flag
  
print(ans)

Submission status: Time Limit Exceeded

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

class MakeGraph:
    
    # 隣接行列もしくは隣接リストの初期化
    # node_num：ノード数
    # isMat：隣接行列(True) / 隣接リスト(False)
    def __init__(self, node_num:int, isMat:bool) -> None:
        self.n = node_num
        self.isMat = isMat

        # 隣接行列の初期化
        if self.isMat:
            INF = float("inf")
            self.graph = [[INF for _ in range(self.n)] for _ in range(self.n)]
    
        # 隣接リストの初期化
        else:
            self.graph = [[] for _ in range(self.n)]

    # エッジの追加
    # frm, to：起点ノード, 終点ノード
    # dist：frm→toへのコスト
    def add_undr_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        self.graph[to][frm] = dist
        
    def add_drct_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        
    def add_undr_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))
        self.graph[to].append((dist, frm))
        
    def add_drct_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))

                
    # 完成したグラフを取り出す
    def get_graph(self) -> list:
        return self.graph


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

# WF        
#for k in range(N):
#    for i in range(N):
#        for j in range(N):
#            if graph[i][j] > graph[i][k]+graph[k][j]:
#                graph[i][j] = graph[i][k]+graph[k][j]
 
graph = floyd_warshall(graph)   
 
# 辺集合
edge_list = []
for a,b,c in ABC:
    edge_list.append([a-1,b-1, c])   

ans = 0
for i,j,cost in edge_list:
    flag = 1
    for frm in range(N):
        for to in range(N):
            if frm == to:
                continue

            if graph[frm][i]+cost+graph[j][to] == graph[frm][to]:
                flag = 0
                    
    ans += flag
  
print(ans)

Submission status: Time Limit Exceeded

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

class MakeGraph:
    
    # 隣接行列もしくは隣接リストの初期化
    # node_num：ノード数
    # isMat：隣接行列(True) / 隣接リスト(False)
    def __init__(self, node_num:int, isMat:bool) -> None:
        self.n = node_num
        self.isMat = isMat

        # 隣接行列の初期化
        if self.isMat:
            INF = float("inf")
            self.graph = [[INF for _ in range(self.n)] for _ in range(self.n)]
    
        # 隣接リストの初期化
        else:
            self.graph = [[] for _ in range(self.n)]

    # エッジの追加
    # frm, to：起点ノード, 終点ノード
    # dist：frm→toへのコスト
    def add_undr_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        self.graph[to][frm] = dist
        
    def add_drct_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        
    def add_undr_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))
        self.graph[to].append((dist, frm))
        
    def add_drct_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))

                
    # 完成したグラフを取り出す
    def get_graph(self) -> list:
        return self.graph


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

# WF        
#for k in range(N):
#    for i in range(N):
#        for j in range(N):
#            if graph[i][j] > graph[i][k]+graph[k][j]:
#                graph[i][j] = graph[i][k]+graph[k][j]
 
res = floyd_warshall(graph)
graph = list(res)   
 
# 辺集合
edge_list = []
for a,b,c in ABC:
    edge_list.append([a-1,b-1, c])   

ans = 0
for i,j,cost in edge_list:
    flag = 1
    for frm in range(N):
        for to in range(N):
            if frm == to:
                continue

            if graph[frm][i]+cost+graph[j][to] == graph[frm][to]:
                flag = 0
                    
    ans += flag
  
print(ans)