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 Graph():
    def __init__(self,vertex_num,node_num,naive_input,start_zero=True,direction=False):
        self.vertex_num=vertex_num
        self.node_num=node_num
        #nodeには入力時のインデックスも含む
        #[接続ノード , インッデクス]のarray
        node=[{} for _ in range(vertex_num)]
        for i in range(node_num):
            u,v,w=naive_input[i]
            if not start_zero:
                u-=1
                v-=1
            node[u][v]={"weight":w,"index":i}
            #node[v][u]={"weight":w,"index":i}
            if not direction:
                node[v][u]={"weight":w,"index":i}
                #node[u][v]["reverse"]={"weight":w,"index":i}
        self.node=node
        #それぞれの頂点の辺の数
        self.node_num_arr=list(map(lambda x:len(x),node))

    def djikstra(self,s=0):
        distance=[float("inf") for _ in range(self.vertex_num)]
        distance[s]=0
        #visitedにしたけど正確には訪問済みではなく最短距離確定済みが適切
        #いい名前教えて
        #visited_vertex=[False for _ in range(self.vertex_num)]
        #visited_vertex[s]=True
        visited_vertex={s}
        before_vertex=[float("inf") for _ in range(self.vertex_num)]
        node_index_arr=[float("inf") for _ in range(self.vertex_num)]
        while len(visited_vertex)<self.vertex_num:
            #will_visit_node=cal_will_visit_node(self.node,visited_vertex)
            min_distance_heap=[]
            for now_node_num in visited_vertex:
                for next_node_num in self.node[now_node_num].keys():
                    if next_node_num in visited_vertex:
                        continue
                    next_node=self.node[now_node_num][next_node_num]
                    cal_d=distance[now_node_num]+next_node["weight"]
                    if cal_d <distance[next_node_num]:
                        distance[next_node_num]=cal_d
                        before_vertex[next_node_num]=now_node_num
                        node_index_arr[next_node_num]=next_node["index"]
                    heapq.heappush(min_distance_heap,[distance[next_node_num],next_node_num])
            add_vertex=min_distance_heap[0][1]
            visited_vertex.add(add_vertex)
        return node_index_arr
        





n,m=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(m)]
G=Graph(n,m,a,start_zero=False)  
ans=[True for _ in range(m)]
for i in range(n):
    tmp=G.djikstra(i)
    for j in tmp:
        if j!=float("inf"):
            ans[j]=False

print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
dist = [[1e9 for i in range(N)] for j in range(N)]
E = []

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

for i in range(M):
  a,b,c = list(map(int,input().split()))
  a, b = a-1, b-1 # 0-indexed
  dist[a][b] = c
  dist[b][a] = c
  E.append([a,b,c])
  
# Warshal-Floyd
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 e in E:
  a,b,c = e
  flg = False
  for i in range(N):
    for j in range(N):
      if i == j : #or i == a or i == b or j == a or j == b:
        continue
      if dist[i][a] + c + dist[b][j] == dist[a][b]:
        #print(i,a,b,j)
       # print(dist[i][a], c, dist[b][j] , ":", dist[a][b])
        flg = True
        break
    if flg:
      break
  if not flg:
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())

import numpy as np
from scipy.sparse.csgraph import shortest_path

l = np.array([[float("inf") for i in range(n)] for j in range(n)])
ans = []
for _ in range(m):
   a,b,c = map(int,input().split())
   l[a-1][b-1] = c
   l[b-1][a-1] = c
   if a > b:
      ans.append((b,a))
   else:
      ans.append((a,b))

d, p = shortest_path(l, return_predecessors=True)


for pp in p:
   for idx, ppp in enumerate(pp):
      if idx < ppp:
         if (idx+1, ppp+1) in ans:
            ans.remove((idx+1, ppp+1))
      else:
         if (ppp+1, idx+1) in ans:
            ans.remove((ppp+1, idx+1))
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
import sys
input=sys.stdin.readline 

class Graph:
 
    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = set()
        self.edges = []
 
    def add_edge(self, a, b, weight=1):
        self.graph[a].append((b, weight))
        self.vertices |= {a, b}
        self.edges.append((a, b, weight))
 
    def get_vertices(self):
        return sorted(list(self.vertices))
 
    def num_of_vertices(self):
        return len(self.vertices)
 
    def get_edges(self):
        return self.edges
 
    def num_of_edges(self):
        return len(self.edges)
 
class Dijkstra:
 
    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, (0, 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):
 
        return self.dist[goal]
 
    def shortest_path(self, goal):
 
        path = []
        vertice = goal
        cnt = 0
        while vertice is not None:
            path.append(vertice)
            cnt += 1
            vertice = self.prev[vertice]
 
        return path, cnt

N, M = map(int, input().split())
G = Graph()
T = []
C = defaultdict(int)
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, c)
    G.add_edge(b, a, c)
    T.append(tuple(sorted([a, b])))

for i in range(1, N+1):
    for j in range(1, N+1):
        D = Dijkstra(G, i)
        P, L = D.shortest_path(j)
        for k in range(L-1):
            a, b = P[k], P[k+1]
            C[tuple(sorted([a, b]))] = 1

ans = 0
for a, b in T:
    if C[(a, b)] == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
import sys
input=sys.stdin.readline 

class Graph:
 
    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = set()
        self.edges = []
 
    def add_edge(self, a, b, weight=1):
        self.graph[a].append((b, weight))
        self.vertices |= {a, b}
        self.edges.append((a, b, weight))
 
    def get_vertices(self):
        return sorted(list(self.vertices))
 
    def num_of_vertices(self):
        return len(self.vertices)
 
    def get_edges(self):
        return self.edges
 
    def num_of_edges(self):
        return len(self.edges)
 
class Dijkstra:
 
    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, (0, 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):
 
        return self.dist[goal]
 
    def shortest_path(self, goal):
 
        path = []
        vertice = goal
        while vertice is not None:
            path.append(vertice)
            vertice = self.prev[vertice]
 
        return path[::-1]

N, M = map(int, input().split())
G = Graph()
T = []
C = defaultdict(int)
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, c)
    G.add_edge(b, a, c)
    T.append(tuple(sorted([a, b])))

for i in range(1, N+1):
    for j in range(1, N+1):
        D = Dijkstra(G, i)
        P = D.shortest_path(j)
        for k in range(len(P)-1):
            a, b = P[k], P[k+1]
            C[tuple(sorted([a, b]))] = 1

ans = 0
for a, b in T:
    if C[(a, b)] == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
 
class Graph:
 
    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = set()
        self.edges = []
 
    def add_edge(self, a, b, weight=1):
        self.graph[a].append((b, weight))
        self.vertices |= {a, b}
        self.edges.append((a, b, weight))
 
    def get_vertices(self):
        return sorted(list(self.vertices))
 
    def num_of_vertices(self):
        return len(self.vertices)
 
    def get_edges(self):
        return self.edges
 
    def num_of_edges(self):
        return len(self.edges)
 
class Dijkstra:
 
    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, (0, 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):
 
        return self.dist[goal]
 
    def shortest_path(self, goal):
 
        path = []
        vertice = goal
        while vertice is not None:
            path.append(vertice)
            vertice = self.prev[vertice]
 
        return path[::-1]

N, M = map(int, input().split())
G = Graph()
T = []
C = defaultdict(int)
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, c)
    G.add_edge(b, a, c)
    T.append(tuple(sorted([a, b])))

for i in range(1, N+1):
    for j in range(1, N+1):
        D = Dijkstra(G, i)
        P = D.shortest_path(j)
        for k in range(len(P)-1):
            a, b = P[k], P[k+1]
            C[tuple(sorted([a, b]))] = 1

ans = 0
for a, b in T:
    if C[(a, b)] == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
edges = []
G = [[10**8]*N for _ in range(N)]   # 1-indexed
for _ in range(M):
    A, B, C = map(int, input().split())
    # 無向グラフ
    G[A-1][B-1] = C
    G[B-1][A-1] = C
    edges.append((A-1, B-1, C))

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

ans = 0
for A, B, C in edges:
    flg = False
    for i in range(N):
        for j in range(N):
            if G[i][A]+C+G[B][j] == G[i][j]:
                flg = True
    if flg is False:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

dist = [[-1 for i in range(n+1)] for j in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
    hist = [i]
    while True:
        hist_tmp = []
        for h in hist:
            for j in range(m):
                if a[j] == h and (dist[i][b[j]] == -1 or dist[i][b[j]] > dist[i][a[j]] + c[j]):
                    dist[i][b[j]] = dist[i][a[j]] + c[j]
                    hist_tmp.append(b[j])
                elif b[j] == h and (dist[i][a[j]] == -1 or dist[i][a[j]] > dist[i][b[j]] + c[j]):
                    dist[i][a[j]] = dist[i][b[j]] + c[j]
                    hist_tmp.append(a[j])
        if hist_tmp == []:
            break
        else:
            hist = copy.copy(hist_tmp)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import copy
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    D = [[float("inf")]*(N+1) for i in range(N+1)]
    ID = [[float("inf")]*(N+1) for i in range(N+1)]
    NEX = [[set() for j in range(N+1)] for i in range(N+1)]
    
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = c
        D[b][a] = c
        ID[a][b] = i
        ID[b][a] = i
        NEX[a][b].add(b)
        NEX[b][a].add(a)
        
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                if D[i][j] > D[i][k]+D[k][j]:
                    D[i][j] = D[i][k]+D[k][j]
                    NEX[i][j] = copy.deepcopy(NEX[i][k])
                elif D[i][j] == D[i][k]+D[k][j] and i!=j and j!=k and k!=i and D[i][j]<float("inf"):
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
    S = set()
    for i in range(1,N+1):
        for j in range(1,N+1):
            if i != j:
                for l in NEX[i][j]:
                    S.add(ID[i][l])
                #print(i,j,D[i][j],NEX[i][j])
    #print(S)            
    print(M-len(S))
            
    
    
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
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
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 edge in range(m):
  flag=False
  for j in range(n):
    for k in range(n):
      if d[j][a[edge]]+c[edge]==d[j][b[edge]]:
        flag=True
        break
    if flag:
      break
  else:
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
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
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 edge in range(m):
  flag=False
  for j in range(n):
    for k in range(n):
      if d[j][a[edge]]+c[edge]+d[b[edge]][k]==d[j][k]:
        flag=True
        break
    if flag:
      break
  else:
    count+=1
print(count)

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 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):
    for j in range(n):
      if not i== j:
        #iを始点としてjに着く経路
        ds = Dijkstra(route,i)
        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()

Submission status: Time Limit Exceeded

Solution code:
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 enumerate(m[u]):
            if D[v] > D[u] + w:
                D[v] = D[u] + w
                heapq.heappush(Q, (D[u]+w, v))
    return D[t] 

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

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

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(m, s, t):
    INF = 1e10
    D = [INF] * N
    D[s] = 0
    Q = [v for v in range(N)]

    while Q:
        d = INF
        u = None
        for x in Q:
            if D[x] < d:
                d = D[x]
                u = x
        Q.remove(u)
        for v, w in enumerate(m[u]):
            if D[v] > D[u] + w:
                D[v] = D[u] + w
    return D[t] 

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

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

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

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq


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

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        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):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        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(1, N):
        if i != j:
            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)

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq


class Dijkstra():
    def __init__(self, N):
        self.N = N
        self.e = [[float('inf') for i in range(self.N)] for i in range(N)]

    def add(self, u, v, d, directed=False):
        if directed is False:
            self.e[u][v] = d
            self.e[v][u] = d
        else:
            self.e[u][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 = [float('inf') for i in range(self.N)]
        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 enumerate(self.e[u]):
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    def getDijkstraPath(self, s, t):
        # sからtへの最短経路の経路復元
        prev = [s] * self.N  # 最短経路の直前の頂点
        d = [float("inf")] * self.N
        used = [False] * self.N
        d[s] = 0

        while True:
            v = -1
            for i in range(self.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(self.N):
                if d[i] > d[v] + self.e[v][i]:
                    d[i] = d[v] + self.e[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())
graph = Dijkstra(N)
paths = []
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, N):
        path = graph.getDijkstraPath(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())]) - N)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq


class Dijkstra():
    def __init__(self, N):
        self.N = N
        self.e = [[float('inf') for i in range(self.N)] for i in range(N)]

    def add(self, u, v, d, directed=False):
        if directed is False:
            self.e[u][v] = d
            self.e[v][u] = d
        else:
            self.e[u][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 = [float('inf') for i in range(self.N)]
        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 enumerate(self.e[u]):
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    def getDijkstraPath(self, s, t):
        # sからtへの最短経路の経路復元
        prev = [s] * self.N  # 最短経路の直前の頂点
        d = [float("inf")] * self.N
        used = [False] * self.N
        d[s] = 0

        while True:
            v = -1
            for i in range(self.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(self.N):
                if d[i] > d[v] + self.e[v][i]:
                    d[i] = d[v] + self.e[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())
graph = Dijkstra(N)
paths = []
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c, directed=False)
    paths.append([a-1, b-1])

usedPaths = collections.defaultdict(set)
for i in range(N):
    for j in range(i, N):
        path = graph.getDijkstraPath(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())]) - N)//2
print(ans)