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

rest_edges = set([(a,b) for a,b,c in edges])
for a in range(1, N+1):
    for b in range(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)
            #print(x, y)
            rest_edges.discard((x,y))
            
print(len(rest_edges))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
import copy

inf = float('inf')

def findedge(E, vv):
    e = (min(vv), max(vv))
    if e in E:
        return e
    return None


def dijkstra(V, E, L, s, g):
    D = [0 if v == s else inf for v in V]

    prev = [None for v in V]
    Q = [(0, s)]
    heapq.heapify(Q)

    while len(Q) > 0:
        du, u = heapq.heappop(Q)
        # print('pop: ', u, du)
        for v in V:
            e = findedge(E, (u, v))
            if not e:
                continue
            alt = du + L[e]
            # print('edge: ', e)

            if D[v] > alt:
                D[v] = alt
                prev[v] = u
                heapq.heappush(Q, (D[v], v))
    
    # print(prev)
    return D[g]


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    V = list(range(N))
    E = set()
    L = dict()
    
    for i in range(M):
        e = tuple(sorted([a[i], b[i]]))
        E.add(e)
        L[e] = c[i]

    count = 0
    E2 = copy.deepcopy(E)
    for e in E:
        if dijkstra(V, E2, L, e[0], e[1]) < L[e]:
            count += 1
            E2.remove(e)

    print(count)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    c = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))-1
        b[i] = int(next(tokens))-1
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

wf = [[float('inf')] * n for _ in range(n)]
for a, b, c in d:
    wf[a][b] = wf[b][a] = c
for i in range(n):
    wf[i][i] = 0

for k, i, j in itertools.product(range(n), repeat=3):
    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

ans = 0
for a, b, c in d:
    used = False
    for i, j in itertools.product(range(n), repeat=2):
        if wf[i][a] + c + wf[b][j] == wf[i][j] or wf[i][b] + c + wf[a][j] == wf[i][j]:
            used = True
    
    if not used:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Dijkstra: # 最短経路問題
    def __init__(self, route_map, start_point, goal_point=None):
        self.route_map = route_map #
        self.start_point = start_point # スタート位置
        self.goal_point = goal_point

    def execute(self):
        import heapq
        num_of_city = len(self.route_map) # ノード数
        dist = [float("inf") for _ in range(num_of_city)] # startからの距離を格納する
        prev = [float("inf") for _ in range(num_of_city)] # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる

        dist[self.start_point] = 0 # スタート位置までのコストは0
        heap_q = [] # 優先度つきキュー
        heapq.heappush(heap_q, (0, self.start_point)) # タプル(0,スタート位置)をheap_qに追加
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q) # 直前にheap_qに入れたタプルから取り出す(src＝ソース)

            if dist[src] < prev_cost: # もし、スタート位置からsrcまでの距離がprev_costより小さいなら問題ないのでok
                continue

            for dest, cost in self.route_map[src].items(): # destはsrcから行ける頂点(目的地)
                if cost != float("inf") and dist[dest] > dist[src] + cost: # もし、destに有限のコストで行けて、srcからdestに行くのがスタートからの現状の最短距離になるなら、
                    dist[dest] = dist[src] + cost # 更新する
                    heapq.heappush(heap_q, (dist[dest], dest)) # 更新したのでheap_qに入れておく。次のノードに移動した時に取り出して無駄な変更がないか確認する
                    prev[dest] = src
        if self.goal_point is not None: # ゴールまでの最短経路を返す
            return self.get_path(self.goal_point, prev)
        else: # スタートから各頂点までの最短距離を格納したリストを返す
            return dist

    def get_path(self, goal, prev):  # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる
        global edge_num
        global used_edge
        path = [goal]
        dest = goal
        
        while prev[dest] != float("inf"): # prev[start]はfloat("inf")になり、停止する
            used_edge[edge_num[prev[dest]][dest]] += 1
            path.append(prev[dest]) # 後ろから戻っていく
            dest = prev[dest]

        return list(reversed(path)) # 逆から辿ったので順を元に戻す

import sys
input = sys.stdin.readline


N,M = map(int,input().split())
route_map = [dict() for _ in range(N)]
edge_num = [dict() for _ in range(N)]
for i in range(M): # M == エッジの数
    u, v, cost = map(int, input().split()) # cost は 辺　u -> v の重み(距離,コスト)
    u, v = u - 1, v - 1
    route_map[u][v] = cost # route_mapの第u番目のdictに{v:cost}が入る
    route_map[v][u] = cost # route_mapの第v番目のdictに{u:cost}が入る
    edge_num[u][v] = i # redge_numの第u番目のdictに{v:i}が入る
    edge_num[v][u] = i # redge_numの第v番目のdictに{u:i}が入る


used_edge = [0 for _ in range(M)]
checked_node = [[0 for _ in range(N)] for __ in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        if checked_node[i][j] != 0:
            continue
        dijkstra_result1 = Dijkstra(route_map, i, j).execute()
        dijkstra_result2 = Dijkstra(route_map, N-1-i, N-1-j).execute()
        for k in range(len(dijkstra_result1)-1):
            for l in range(k+1,len(dijkstra_result1)):
                checked_node[dijkstra_result1[k]][dijkstra_result1[l]] += 1
        for k in range(len(dijkstra_result2)-1):
            for l in range(k+1,len(dijkstra_result2)):
                checked_node[dijkstra_result2[k]][dijkstra_result2[l]] += 1

ans = used_edge.count(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Dijkstra: # 最短経路問題
    def __init__(self, route_map, start_point, goal_point=None):
        self.route_map = route_map #
        self.start_point = start_point # スタート位置
        self.goal_point = goal_point

    def execute(self):
        import heapq
        num_of_city = len(self.route_map) # ノード数
        dist = [float("inf") for _ in range(num_of_city)] # startからの距離を格納する
        prev = [float("inf") for _ in range(num_of_city)] # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる

        dist[self.start_point] = 0 # スタート位置までのコストは0
        heap_q = [] # 優先度つきキュー
        heapq.heappush(heap_q, (0, self.start_point)) # タプル(0,スタート位置)をheap_qに追加
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q) # 直前にheap_qに入れたタプルから取り出す(src＝ソース)

            if dist[src] < prev_cost: # もし、スタート位置からsrcまでの距離がprev_costより小さいなら問題ないのでok
                continue

            for dest, cost in self.route_map[src].items(): # destはsrcから行ける頂点(目的地)
                if cost != float("inf") and dist[dest] > dist[src] + cost: # もし、destに有限のコストで行けて、srcからdestに行くのがスタートからの現状の最短距離になるなら、
                    dist[dest] = dist[src] + cost # 更新する
                    heapq.heappush(heap_q, (dist[dest], dest)) # 更新したのでheap_qに入れておく。次のノードに移動した時に取り出して無駄な変更がないか確認する
                    prev[dest] = src
        if self.goal_point is not None: # ゴールまでの最短経路を返す
            return self.get_path(self.goal_point, prev)
        else: # スタートから各頂点までの最短距離を格納したリストを返す
            return dist

    def get_path(self, goal, prev):  # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる
        global edge_num
        global used_edge
        path = [goal]
        dest = goal
        
        while prev[dest] != float("inf"): # prev[start]はfloat("inf")になり、停止する
            used_edge[edge_num[prev[dest]][dest]] += 1
            path.append(prev[dest]) # 後ろから戻っていく
            dest = prev[dest]

        return list(reversed(path)) # 逆から辿ったので順を元に戻す

import sys
input = sys.stdin.readline


N,M = map(int,input().split())
route_map = [dict() for _ in range(N)]
edge_num = [dict() for _ in range(N)]
for i in range(M): # M == エッジの数
    u, v, cost = map(int, input().split()) # cost は 辺　u -> v の重み(距離,コスト)
    u, v = u - 1, v - 1
    route_map[u][v] = cost # route_mapの第u番目のdictに{v:cost}が入る
    route_map[v][u] = cost # route_mapの第v番目のdictに{u:cost}が入る
    edge_num[u][v] = i # redge_numの第u番目のdictに{v:i}が入る
    edge_num[v][u] = i # redge_numの第v番目のdictに{u:i}が入る


used_edge = [0 for _ in range(M)]
for i in range(N-1):
    for j in range(i+1,N):
        dijkstra_result1 = Dijkstra(route_map, i, j).execute()
        dijkstra_result2 = Dijkstra(route_map, N-1-i, N-1-j).execute()

ans = used_edge.count(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Dijkstra: # 最短経路問題
    def __init__(self, route_map, start_point, goal_point=None):
        self.route_map = route_map #
        self.start_point = start_point # スタート位置
        self.goal_point = goal_point

    def execute(self):
        import heapq
        num_of_city = len(self.route_map) # ノード数
        dist = [float("inf") for _ in range(num_of_city)] # startからの距離を格納する
        prev = [float("inf") for _ in range(num_of_city)] # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる

        dist[self.start_point] = 0 # スタート位置までのコストは0
        heap_q = [] # 優先度つきキュー
        heapq.heappush(heap_q, (0, self.start_point)) # タプル(0,スタート位置)をheap_qに追加
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q) # 直前にheap_qに入れたタプルから取り出す(src＝ソース)

            if dist[src] < prev_cost: # もし、スタート位置からsrcまでの距離がprev_costより小さいなら問題ないのでok
                continue

            for dest, cost in self.route_map[src].items(): # destはsrcから行ける頂点(目的地)
                if cost != float("inf") and dist[dest] > dist[src] + cost: # もし、destに有限のコストで行けて、srcからdestに行くのがスタートからの現状の最短距離になるなら、
                    dist[dest] = dist[src] + cost # 更新する
                    heapq.heappush(heap_q, (dist[dest], dest)) # 更新したのでheap_qに入れておく。次のノードに移動した時に取り出して無駄な変更がないか確認する
                    prev[dest] = src
        if self.goal_point is not None: # ゴールまでの最短経路を返す
            return self.get_path(self.goal_point, prev)
        else: # スタートから各頂点までの最短距離を格納したリストを返す
            return dist

    def get_path(self, goal, prev):  # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる
        global edge_num
        global used_edge
        path = [goal]
        dest = goal
        
        while prev[dest] != float("inf"): # prev[start]はfloat("inf")になり、停止する
            used_edge[edge_num[prev[dest]][dest]] += 1
            path.append(prev[dest]) # 後ろから戻っていく
            dest = prev[dest]

        return list(reversed(path)) # 逆から辿ったので順を元に戻す

import sys
input = sys.stdin.readline


N,M = map(int,input().split())
route_map = [dict() for _ in range(N)]
edge_num = [dict() for _ in range(N)]
for i in range(M): # M == エッジの数
    u, v, cost = map(int, input().split()) # cost は 辺　u -> v の重み(距離,コスト)
    u, v = u - 1, v - 1
    route_map[u][v] = cost # route_mapの第u番目のdictに{v:cost}が入る
    route_map[v][u] = cost # route_mapの第v番目のdictに{u:cost}が入る
    edge_num[u][v] = i # redge_numの第u番目のdictに{v:i}が入る
    edge_num[v][u] = i # redge_numの第v番目のdictに{u:i}が入る


used_edge = [0 for _ in range(M)]
# ゴールまでの最短経路
for i in range(N-1):
    for j in range(i+1,N):
        dijkstra_result1 = Dijkstra(route_map, i, j).execute()
        dijkstra_result2 = Dijkstra(route_map, N-1-i, N-1-j).execute()

ans = used_edge.count(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy

V, M = map(int, input().split())
d = [0] * V
prev = [0] * V
INF = float('inf')

cost = [[INF] * V for i in range(V)]
for i in range(M):
    a, b, c = map(int,  input().split())
    cost[a - 1][b - 1] = c
    cost[b - 1][a - 1] = c
    
def dijkstra_back(s, t):
    for i in range(V):
        prev[i] = s
        d[i] = INF
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
         
        for i in range(V):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                heapq.heappush(h, [d[i], 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

cost2 = copy.deepcopy(cost)
for i in range(V - 1):
    for j in range(i + 1, V):
        g = dijkstra_back(i, j)
        # print(i, j, g)
        for k in range(len(g) - 1):
            cost2[g[k]][g[k + 1]] = INF
            cost2[g[k + 1]][g[k]] = INF
            
cnt = 0
for i in range(V):
    for j in range(V):
        if cost2[i][j] != INF:
            cnt += 1
                     
print(cnt // 2)

Submission status: Time Limit Exceeded

Solution code:
import copy

V, M = map(int, input().split())
d = [0] * V
prev = [0] * V
INF = float('inf')

cost = [[INF] * V for i in range(V)]
for i in range(M):
    a, b, c = map(int,  input().split())
    cost[a - 1][b - 1] = c
    cost[b - 1][a - 1] = c
    
def dijkstra_back(s,t):
    prev = [s] * V
    d = [float("inf")] * V
    used = [False] * V
    d[s] = 0
    
    while True:
        v = -1
        for i in range(V):
            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(V):
            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

cost2 = copy.deepcopy(cost)
for i in range(V - 1):
    for j in range(i + 1, V):
        g = dijkstra_back(i, j)
        for k in range(len(g) - 1):
            cost2[g[k]][g[k + 1]] = INF
            cost2[g[k + 1]][g[k]] = INF
            
cnt = 0
for i in range(V):
    for j in range(V):
        if cost2[i][j] != INF:
            cnt += 1
                     
print(cnt // 2)

Submission status: Time Limit Exceeded

Solution code:
def candidates_of_no_shortest_paths(N: int, M: int, edges: list)->int:
    INF = float('inf')

    d = [[0 if i == j else INF for i in range(N)] for j in range(N)]

    for u, v, c in edges:
        d[u-1][v-1] = d[v-1][u-1] = c

    # warshall-floyd
    for k in range(N):
        for u in range(N):
            for v in range(N):
                if d[u][v] > d[u][k] + d[k][v]:
                    d[u][v] = d[u][k] + d[k][v]

    def used(edge: tuple)->bool:
        u, v, c = edge
        for s in range(N):
            for t in range(N):
                if d[s][u-1] + c + d[v-1][t] == d[s][t]:
                    return True
        return False

    return sum(not used(edge) for edge in edges)


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(int(s) for s in input().split()) for _ in range(M)]
    ans = candidates_of_no_shortest_paths(N, M, edges)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
inf = float('inf')

# dist[i][j]: iからjへのコスト,  n:頂点数
def warshall_floyd(dist,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

N,M = map(int,input().split())
edges = []
ad = [[inf]*N for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1;  b -= 1
    edges.append((a,b,c))
    ad[a][b] = c
    ad[b][a] = c

warshall_floyd(ad,N)
ans = M

for a,b,c in edges:
    for s in range(N):
        for e in range(N):
            if ad[s][a] + c + ad[b][e] == ad[s][e]:
                ans -= 1
                break
        else:
            continue
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
abc = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]

dist = [[9999999 for _ in range(n)] for _ in range(n)]

e = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    e[a][b] = c + 1
    e[b][a] = c + 1

for i in range(n):
    dist[i][i] = 0
    temp = set()
    temp.add(i)
    while len(temp) < n:
        next = -1
        nc = 99999999
        for x in temp:
            for y in e[x].keys():
                if y in temp:
                    continue
                if dist[i][x] + e[x][y] < nc:
                    nc = dist[i][x] + e[x][y]
                    next = y
        temp.add(next)
        dist[i][next] = nc

ans = m
for a, b, c in abc:
    for i in range(n):
        if c + 1 == dist[a][i] - dist[b][i]:
            ans -= 1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
abc = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]

dist = [[9999999 for _ in range(n)] for _ in range(n)]

e = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    e[a][b] = c + 1
    e[b][a] = c + 1

for i in range(n-1):
    for j in range(i + 1, n):
        dp = [9999999 for _ in range(n)]
        dp[i] = 0
        temp = set()
        temp.add(i)
        while j not in temp:
            next = -1
            nc = 99999999
            for x in temp:
                for y in e[x].keys():
                    if y in temp:
                        continue
                    if dp[x] + e[x][y] < nc:
                        nc = dp[x] + e[x][y]
                        next = y
            temp.add(next)
            dp[next] = nc
            #print(temp, dp)
        dist[i][j] = dp[j]
        dist[j][i] = dp[j]

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

ans = m
for a, b, c in abc:
    for i in range(n):
        if c + 1 == dist[a][i] - dist[b][i]:
            ans -= 1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m = map(int, input().split())

am = [[float("inf")] * n for x in range(n)] #隣接行列
al = [] #隣接リスト

for x in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    am[a][b] = c
    am[b][a] = c
    al.append([a,b,c])

for e in al: #e[0]は始点,e[1]は終点
    l = [x for x in range(n)]
    l.remove(e[0])
    for x in itertools.permutations(l): #順列を用いて経路xを生成
        x = list(x)
        x.insert(0,e[0])
        d = 0
        for y in range(len(x)-1): #ある経路の距離を計算
            d += am[x[y]][x[y+1]]
            if d == float("inf"): #存在しない経路でbreak
                break
            if y+1 == e[1]: #終点に着いたらbreak
                break
        if am[e[0]][e[1]] > d: #より短い経路をamに記録
            am[e[0]][e[1]] = d
            am[e[1]][e[0]] = d

ans = 0
for a, b, c in al: #辺の長さが最短経路よりも長ければカウント
    if am[a][b] < c:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

am = [[float("inf")] * n for x in range(n)] #隣接行列
al = [] #隣接リスト

for x in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    am[a][b] = c
    am[b][a] = c
    al.append([a,b,c])

for i in range(n): #iは始点
    for j in range(i+1,n): #jは終点
        l = [x for x in range(n)]
        l.remove(j)
        for x in itertools.permutations(l): #組み合わせを用いて経路を生成
            x = list(x)
            x.insert(0,i)
            d = 0
            for y in range(len(x)-1): #ある経路の距離を計算
                d += am[x[y]][x[y+1]]
                if d == float("inf"): #存在しない経路でbreak
                    break
                if y+1 == j: #終点に着いたらbreak
                    break
            if am[i][j] > d: #より短い経路をamに記録
                am[i][j] = d
                am[j][i] = d

ans = 0
for a, b, c in al: #辺の長さが最短経路よりも短ければカウント
    if am[a][b] < c:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as comb
from collections import deque as dq

def inpl(): return list(map(int, input().split()))


def dijkstra(a, b):
    node = dq()
    node.append(a)
    ncost = [1<<20 for _ in range(N+1)]
    first = a
    ncost[a] = 0
    path = {}
    while b not in node:
        for nb in edge[first]:
            if nb in node:
                continue
            if ncost[nb] > ncost[first] + cost[(first, nb)]:
                # print(nb, ncost[nb])
                path[nb] = first
                ncost[nb] = ncost[first] + cost[(first, nb)]
                # print(nb, ncost[nb])

        nf = 0
        # print(path)
        for t in range(N+1):
            if t in node:
                continue
            # print(nf, t)
            if ncost[nf] > ncost[t]:
                nf = t
        node.append(nf)
        first = nf
        # print(node)
    now = b
    # print(path)
    # print(ncost)
    ret = set()
    while True:
        if now == a:
            break
        ret.add((now, path[now]))
        ret.add((path[now], now))
        now = path[now]
    return ret


N, M = inpl()
cost = {}
edge = [dq() for _ in range(N+1)]
for _ in range(M):
    a, b, c = inpl()
    cost[(a, b)] = c
    cost[(b, a)] = c
    edge[a].append(b)
    edge[b].append(a)

ans = set()
for a, b, in comb([i for i in range(1, N+1)], 2):
    # print(a, b, "check")
    # print(dijkstra(a, b))
    ans = ans | dijkstra(a, b)
# print(ans)
print(M-len(ans)//2)