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 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):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        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):
        """
        0-indexedであることに注意
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        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)

Submission status: Time Limit Exceeded

Solution code:
# 頂点の数（N）および辺の数（M）を入力する
N, M = map(int, input().split())

# 頂点の隣接リスト（list_adjlist）を設定する
list_adjlist = [[] for _ in range (N + 1)]
# 辺の長さを格納する辞書（dic_edge_dist）を設定する
dic_edge_dist = {}
# 辺の長さの合計（sum_edge）を設定する
sum_edge= 0

# 各辺について、、
for _ in range(M):
    # 頂点および辺の長さを入力する
    a, b, c = map(int, input().split())
    # list_adjlistに辺を追加する
    list_adjlist[a].append(b)
    list_adjlist[b].append(a)
    # dic_edge_distに辺の長さを格納する
    dic_edge_dist[(min(a, b), max(a, b))] = c
    # sum_edgeに辺の長さを加える
    sum_edge += c

def get_shortest_dist(start, end, list_adjlist, dic_edge_dist, sum_edge):
    # 最短距離（shortest_dist）を設定する
    shortest_dist = sum_edge
    # 経路のリスト（list_path）を設定する
    list_path = [([start], 0)]
    # list_pathが空でない限り、、
    while list_path != []:
        # list_pathの先頭の経路（path）とその距離（dist）を取り出す
        path, dist = list_path.pop(0)
        # pathから到達できる各頂点について、、
        for node in list_adjlist[path[-1]]:
            # その頂点までを含めた経路の距離が、shortest_distより短かった場合、、
            if dist + dic_edge_dist[(min(path[-1], node), max(path[-1], node))] < shortest_dist:
                # その頂点が終点である場合、、
                if node == end:
                    # shortest_distを更新する
                    shortest_dist = dist + dic_edge_dist[(min(path[-1], node), max(path[-1], node))]
                # その頂点が終点以外で未訪問の頂点だった場合、、        
                elif node not in path:
                    # その頂点までを含めた経路およびその距離を、list_pathに追加する
                    list_path.append((path + [node], dist + dic_edge_dist[(min(path[-1], node), max(path[-1], node))]))
    # shortest_distを返す
    return shortest_dist

dic_shortest_dist = {}
for start in range(1, N):
    for end in range(start + 1, N + 1):
        dic_shortest_dist[(start, end)] = get_shortest_dist(start, end, list_adjlist, dic_edge_dist, sum_edge)
        
edge_count = 0
for edge, dist in dic_edge_dist.items():
    for node in range(1, N + 1):
        if node in edge:
            continue
        if dist == dic_shortest_dist[edge]:
            edge_count += 1
            break
        if dic_shortest_dist[(min(node, edge[0]), max(node, edge[0]))] + dist == dic_shortest_dist[(min(node, edge[1]), max(node, edge[1]))]:
            edge_count += 1
            break
        elif dic_shortest_dist[(min(node, edge[0]), max(node, edge[0]))] == dic_shortest_dist[(min(node, edge[1]), max(node, edge[1]))] + dist:
            edge_count += 1
            break
            
print(len(dic_edge_dist) - edge_count)

Submission status: Time Limit Exceeded

Solution code:
# 頂点の数（N）および辺の数（M）を入力する
N, M = map(int, input().split())

# 全ての辺を格納するリスト（list_all_edge）を設定する
list_all_edge = []
# 頂点の隣接リスト（list_adjlist）を設定する
list_adjlist = [[] for _ in range(N + 1)]
# 辺の長さを格納する辞書（dic_distance）を設定する
dic_distance = {}
# 辺の長さの合計（sum_distance）を設定する
sum_distance = 0
dic_list_shortest_path = {}

# 各辺の組み合わせについて、、
for _ in range(M):
    # 頂点および辺の長さを入力する
    a, b, c = map(int, input().split())
    # list_all_edgeに辺を追加する
    list_all_edge.append((min(a, b), max(a, b)))
    # list_adjlistに追加する
    list_adjlist[a].append(b)
    list_adjlist[b].append(a)
    # dic_distanceに辺の長さを格納する
    dic_distance[(a, b)] = c
    dic_distance[(b, a)] = c
    # sum_distanceに辺の長さを加える
    sum_distance += c



def get_shortest_path(start, end, list_adjlist, dic_distance, sum_distance, dic_list_shortest_path):
    # 最短距離（shortest_distance）を設定する
    shortest_distance = sum_distance
    # 最短経路リスト（list_shortest_path）を設定する
    list_shortest_path = []
    # 経路のリスト（list_path）を設定する
    list_path = [([start], 0)]
    # list_pathが空でない限り、、
    while list_path != []:
        # list_pathの先頭の経路（path）とその距離（distance）を取り出す
        path, distance = list_path.pop(0)
        # pathから到達できる各頂点について、、
        for node in list_adjlist[path[-1]]:
            # その頂点が終点である場合、、
            if node == end:
                # 終点までを含めた経路の距離が、shortest_disranceより短かった場合、、
                if distance + dic_distance[(path[-1], node)] < shortest_distance:
                    # shortest_distanceを更新する
                    shortest_distance = distance + dic_distance[(path[-1], node)]
                    # list_shortest_pathを更新する
                    list_shortest_path = [path + [node]]
                # 終点までを含めた経路の距離が、shortest_distanceと等しかった場合、、
                elif distance + dic_distance[(path[-1], node)] == shortest_distance:
                    # list_shortest_pathに追加する
                    list_shortest_path.append(path + [node])
            # その頂点が終点以外で未訪問の頂点だった場合、、        
            elif node not in path:
                # その頂点までを含めた経路の距離が、shortest_distanceより短かった場合、、
                if distance + dic_distance[(path[-1], node)] < shortest_distance:
                    # その頂点までを含めた経路およびその距離を、list_pathに追加する
                    list_path.append((path + [node], distance + dic_distance[(path[-1], node)]))
    # list_shortest_pathを返す
    for shortest_path in list_shortest_path:
        for i, u in enumerate(shortest_path[: -1]):
            for j, v in enumerate(shortest_path[i + 1 :]):
                if u < v:
                    start = u
                    end = v
                    path = shortest_path[i : i + j + 2]
                else:
                    start = v
                    end = u
                    path = shortest_path[i : i + j + 2][: : -1]
                if (start, end) not in dic_list_shortest_path:
                    dic_list_shortest_path[(start, end)] = [path]
                elif path not in dic_list_shortest_path[(start, end)]:
                    dic_list_shortest_path[(start, end)].append(path)
    return dic_list_shortest_path


# 最短経路のリスト（list_shortest_path）から、通過する辺を返す関数を定義する
def get_edge(list_shortest_path):
    # 経路上の辺を格納するリスト（list_edge）を設定する
    list_edge = []
    # list_shortest_path内の各最短経路（shortest_path）について、、
    for shortest_path in list_shortest_path:
        # 始点（start）を設定する
        start = shortest_path[0]
        # 最短経路上の始点を除いた各頂点（node）について、、
        for node in shortest_path[1:]:
            # list_edgeに辺を追加する
            list_edge.append((min(start, node), max(start, node)))
            start = node
    # list_edgeを返す
    return list_edge



for start in range(1, N, 1):
    for end in range(N, start, -1):
        if (start, end) not in dic_list_shortest_path:
            dic_list_shortest_path = get_shortest_path(start, end, list_adjlist, dic_distance, sum_distance, dic_list_shortest_path)
            
set_edge = set()            
            
for list_shortest_path in dic_list_shortest_path.values():
    set_edge |= set(get_edge(list_shortest_path))

print(len(set(list_all_edge) - set_edge))

Submission status: Time Limit Exceeded

Solution code:
# 頂点の数（N）および辺の数（M）を入力する
N, M = map(int, input().split())

# 全ての辺を格納するリスト（list_all_edge）を設定する
set_all_edge = set()
# 頂点の隣接リスト（list_adjlist）を設定する
list_adjlist = [[] for _ in range(N + 1)]
# 辺の長さを格納する辞書（dic_distance）を設定する
dic_distance = {}
# 辺の長さの合計（sum_distance）を設定する
sum_distance = 0

# 各辺の組み合わせについて、、
for _ in range(M):
    # 頂点および辺の長さを入力する
    a, b, c = map(int, input().split())
    # list_all_edgeに辺を追加する
    set_all_edge |= set([(a, b), (b, a)])
    # list_adjlistに追加する
    list_adjlist[a].append(b)
    list_adjlist[b].append(a)
    # dic_distanceに辺の長さを格納する
    dic_distance[(min(a, b), max(a, b))] = c
    # sum_distanceに辺の長さを加える
    sum_distance += c

# 2つの頂点間の最短経路のリストを返す関数を定義する
def get_shortest_path(start, end, list_adjlist, dic_distance, sum_distance):
    # 最短距離（shortest_distance）を設定する
    shortest_distance = sum_distance
    # 最短経路リスト（list_shortest_path）を設定する
    list_shortest_path = []
    # 経路のリスト（list_path）を設定する
    list_path = [([(None, start)], 0)]
    # list_pathが空でない限り、、
    while list_path != []:
        # list_pathの先頭の経路（path）とその距離（disrance）を取り出す
        path, distance = list_path.pop(0)
        # pathから到達できる各頂点について、、
        for node in list_adjlist[path[-1][1]]:
            # その頂点が終点である場合、、
            if node == end:
                # 終点までを含めた経路の距離が、shortest_disranceより短かった場合、、
                if distance + dic_distance[(min(path[-1][1], node), max(path[-1][1], node))] < shortest_distance:
                    # shortest_distanceを更新する
                    shortest_distance = distance + dic_distance[(min(path[-1][1], node), max(path[-1][1], node))]
                    # list_shortest_pathを更新する
                    list_shortest_path = [path + [(path[-1][1], node)]]
                # 終点までを含めた経路の距離が、shortest_distanceと等しかった場合、、
                elif distance + dic_distance[(min(path[-1][1], node), max(path[-1][1], node))] == shortest_distance:
                    # list_shortest_pathに追加する
                    list_shortest_path.append(path + [(path[-1][1], node)])
            # その頂点が終点以外で未訪問の頂点だった場合、、        
            elif node not in path:
                # その頂点までを含めた経路の距離が、shortest_distanceより短かった場合、、
                if distance + dic_distance[(min(path[-1][1], node), max(path[-1][1], node))] < shortest_distance:
                    # その頂点までを含めた経路およびその距離を、list_pathに追加する
                    list_path.append((path + [(path[-1][1], node)], distance + dic_distance[(min(path[-1][1], node), max(path[-1][1], node))]))
    # 
    set_edge = set()
    for shortest_path in list_shortest_path:
        for edge in shortest_path:
            set_edge |= set([edge, edge[::-1]])
    # list_shortest_pathを返す
    return set_edge

# 1〜N-1までの各頂点を始点（start）として、、
for start in range(1, N):
    # start+1〜Nまでの各頂点を終点（end）として、、
    for end in range(start + 1, N + 1):
        # startからendまでの最短経路のリスト（list_shortest_path）を得る
        set_edge = get_shortest_path(start, end, list_adjlist, dic_distance, sum_distance)
        set_all_edge -= set_edge


# どの2頂点間の最短経路にも含まれない辺の数を返す
print(len(set_all_edge) // 2)

Submission status: Time Limit Exceeded

Solution code:
# 頂点の数（N）および辺の数（M）を入力する
N, M = map(int, input().split())

# 全ての辺を格納するリスト（list_all_edge）を設定する
list_all_edge = []
# 頂点の隣接リスト（list_adjlist）を設定する
list_adjlist = [[] for _ in range(N + 1)]
# 辺の長さを格納する辞書（dic_distance）を設定する
dic_distance = {}
# 辺の長さの合計（sum_distance）を設定する
sum_distance = 0

# 各辺の組み合わせについて、、
for _ in range(M):
    # 頂点および辺の長さを入力する
    a, b, c = map(int, input().split())
    # list_all_edgeに辺を追加する
    list_all_edge.append((min(a, b), max(a, b)))
    # list_adjlistに追加する
    list_adjlist[a].append(b)
    list_adjlist[b].append(a)
    # dic_distanceに辺の長さを格納する
    dic_distance[(a, b)] = c
    dic_distance[(b, a)] = c
    # sum_distanceに辺の長さを加える
    sum_distance += c

# 2つの頂点間の最短経路のリストを返す関数を定義する
def get_shortest_path(start, end, list_adjlist, dic_distance, sum_distance):
    # 最短距離（shortest_distance）を設定する
    shortest_distance = sum_distance
    # 最短経路リスト（list_shortest_path）を設定する
    list_shortest_path = []
    # 経路のリスト（list_path）を設定する
    list_path = [([start], 0)]
    # list_pathが空でない限り、、
    while list_path != []:
        # list_pathの先頭の経路（path）とその距離（disrance）を取り出す
        path, distance = list_path.pop(0)
        # pathから到達できる各頂点について、、
        for node in list_adjlist[path[-1]]:
            # その頂点が終点である場合、、
            if node == end:
                # 終点までを含めた経路の距離が、shortest_disranceより短かった場合、、
                if distance + dic_distance[(path[-1], node)] < shortest_distance:
                    # shortest_distanceを更新する
                    shortest_distance = distance + dic_distance[(path[-1], node)]
                    # list_shortest_pathを更新する
                    list_shortest_path = [path + [node]]
                # 終点までを含めた経路の距離が、shortest_distanceと等しかった場合、、
                elif distance + dic_distance[(path[-1], node)] == shortest_distance:
                    # list_shortest_pathに追加する
                    list_shortest_path.append(path + [node])
            # その頂点が終点以外で未訪問の頂点だった場合、、        
            elif node not in path:
                # その頂点までを含めた経路の距離が、shortest_distanceより短かった場合、、
                if distance + dic_distance[(path[-1], node)] < shortest_distance:
                    # その頂点までを含めた経路およびその距離を、list_pathに追加する
                    list_path.append((path + [node], distance + dic_distance[(path[-1], node)]))
    # list_shortest_pathを返す
    return list_shortest_path
 
# 最短経路のリスト（list_shortest_path）から、通過する辺を返す関数を定義する
def get_edge(list_shortest_path):
    # 経路上の辺を格納するリスト（list_edge）を設定する
    list_edge = []
    # list_shortest_path内の各最短経路（shortest_path）について、、
    for shortest_path in list_shortest_path:
        # 始点（start）を設定する
        start = shortest_path[0]
        # 最短経路上の始点を除いた各頂点（node）について、、
        for node in shortest_path[1:]:
            # list_edgeに辺を追加する
            list_edge.append((min(start, node), max(start, node)))
            # nodeを次の始点とする
            start = node
    # list_edgeを返す
    return list_edge

# 辺を格納するリスト（list_edge）を設定する
list_edge = []
# 1〜N-1までの各頂点を始点（start）として、、
for start in range(1, N):
    # start+1〜Nまでの各頂点を終点（end）として、、
    for end in range(start + 1, N + 1):
        # startからendまでの最短経路のリスト（list_shortest_path）を得る
        list_shortest_path = get_shortest_path(start, end, list_adjlist, dic_distance, sum_distance)
        # startからendまでの最短経路に含まれる辺を、list_edgeに追加する
        list_edge.extend(get_edge(list_shortest_path))

# どの2頂点間の最短経路にも含まれない辺の数を返す
print(len(set(list_all_edge) - set(list_edge)))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
distance=[[99999999 for i in range(n)] for i in range(n)]
for i in range(n):
  distance[i][i]=0
for i in range(m):
  distance[l[i][0]-1][l[i][1]-1]=l[i][2]
  distance[l[i][1]-1][l[i][0]-1]=l[i][2]

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

ct=m
for k in range(m):
  for i in range(n):
    for j in range(n):
      if i!=j:
        if distance[i][j]==distance[i][l[k][0]-1]+l[k][2]+distance[l[k][1]-1][j]:
          ct-=1
          break
    else:
      continue
    break
print(ct)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M=map(int,input().split())
R=[]
G=[[] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    G[a].append((b,c))
    G[b].append((a,c))
    R.append((a,b,c))
Q=[[0]*N for i in range(N)]
INF=10**9
for i in range(N):
    stack=[]
    g=[INF for i in range(N)]
    g[i]=0
    for b,c in G[i]:
        heapq.heappush(stack,(g[i]+c,i,b))
    used=[[0]*N for i in range(N)]
    while(stack):
        c,a,b=heapq.heappop(stack)
        g[b]=min(g[b],c)
        used[a][b]=1
        used[b][a]=1
        for j in G[b]:
            if used[b][j[0]]:
                continue
            heapq.heappush(stack,(g[b]+j[1],b,j[0]))
    for j in range(i+1,N):
        Q[i][j]=g[j]
ans=0
for a,b,c in R:
    if b<a:
        a,b=b,a
    if Q[a][b]<c:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
    
edges = ABC[:]

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = 1000*1000*10
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path

#print(edges)
# 無効グラフなので逆向きのエッジも作る
rev_edges = [ (b,a,c) for a,b,c in edges ]
graph = Graph(edges + rev_edges)

rest_edges = set()
for a in range(1, N+1):
    for b in range(a+1, N+1):
        rest_edges.add((a, b))

shotest_set = set()
for a in range(1, N+1):
    for b in range(a+1, N+1):
        if (a,b) not in rest_edges:
            continue
        shortest = graph.dijkstra(a, b)
        shortest = list(shortest)
        #print(shortest)
        last_n = shortest[-1]
        for x, y in zip(shortest[:-1],shortest[1:]):
            x, y = min(x, y), max(x, y)
            shotest_set.add((x,y))
            
            del_x, del_y = min(x, last_n), max(x, last_n)
            rest_edges.discard((del_x, del_y))

#print(edges)
#print(shotest_set)
print(len(edges) - len(shotest_set))

Submission status: Time Limit Exceeded

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

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

edges = ABC[:]

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = 1000*1000*10
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path

#print(edges)
# 無効グラフなので逆向きのエッジも作る
rev_edges = [ (b,a,c) for a,b,c in edges ]
graph = Graph(edges + rev_edges)

shotest_set = set()
for a in range(1, N+1):
    for b in range(a+1, N+1):
        shortest = graph.dijkstra(a, b)
        shortest = list(shortest)
        #print(shortest)
        for x, y in zip(shortest[:-1],shortest[1:]):
            x, y = min(x, y), max(x, y)
            shotest_set.add((x,y))

#print(edges)
#print(shotest_set)
print(len(edges) - len(shotest_set))

Submission status: Time Limit Exceeded

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

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
    
edges = ABC[:]

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = 1000*1000*10
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path

#print(edges)
# 無効グラフなので逆向きのエッジも作る
rev_edges = [ (b,a,c) for a,b,c in edges ]
graph = Graph(edges + rev_edges)

shotest_set = set()
for a in range(1, N+1):
    for b in range(a+1, N+1):
        shortest = graph.dijkstra(a, b)
        shortest = list(shortest)
        #print(shortest)
        for x, y in zip(shortest[:-1],shortest[1:]):
            x, y = min(x, y), max(x, y)
            shotest_set.add((x,y))

#print(edges)
#print(shotest_set)
print(len(edges) - len(shotest_set))