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: Wrong Answer

Solution code:

from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

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

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

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

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

# 入力    
N,M = map(int, input().split())
ABC = []
for i in range(M):
    ABC.append(tuple(map(int, input().split())))
    
    
graphMaker = MakeGraph(N,False)
add_edge = graphMaker.add_undr_edge_lst

for a,b,c in ABC:
    add_edge(a-1, b-1, c)

graph = graphMaker.get_graph()

dist = []
for i in range(N):
    dist_temp = dijkstra(graph, N, i)
    dist.append(dist_temp)
    
ans = 0
for i in range(N):
    for cost, node in graph[i]:
        if dist[i][node] != cost:
            ans += 1
            
            
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

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

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

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

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

# 入力    
N,M = map(int, input().split())
ABC = []
for i in range(M):
    ABC.append(tuple(map(int, input().split())))
    
#file = open("sampleABC051D.txt", "r")
#
#N,M = map(int, file.readline().split())
#ABC = []
#for i in range(M):
#    ABC.append(tuple(map(int, file.readline().split())))
    
graphMaker = MakeGraph(N,False)
add_edge = graphMaker.add_undr_edge_lst

for a,b,c in ABC:
    add_edge(a-1, b-1, c)

graph = graphMaker.get_graph()

dist = []
for i in range(N):
    dist_temp = dijkstra(graph, N, i)
    dist.append(dist_temp)
    
ans = 0
for i in range(N-1):
    for cost, node in graph[i]:
        if dist[i][node] != cost:
            ans += 1
            
            
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
d = [[float("inf")] * n for _ in range(n)]
d_org = [[float("inf")] * n for _ in range(n)]
for _ in range(m):
	a, b, c = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
	d_org[a - 1][b - 1] = c
	d_org[b - 1][a - 1] = c

for i in range(n):
	for j in range(n):
		if i == j:
			continue
		for k in range(n):
			if d[i][k] + d[k][j] < d[i][j]:
				d[i][j] = d[i][k] + d[k][j]

ans = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		if d_org[i][j] < float("inf") and d_org[i][j] > d[i][j]:
			ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
d = [[float("inf") for _ in range(n)] for _ in range(n)]
d_org = [[float("inf") for _ in range(n)] for _ in range(n)]
for _ in range(m):
	a, b, c = map(int, input().split())
	d[a - 1][b - 1] = c
	d[b - 1][a - 1] = c
	d_org[a - 1][b - 1] = c
	d_org[b - 1][a - 1] = c

for i in range(n):
	for j in range(n):
		if i == j:
			continue
		for k in range(n):
			if d[i][k] + d[k][j] < d[i][j]:
				d[i][j] = d[i][k] + d[k][j]

ans = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		if d_org[i][j] < float("inf") and d_org[i][j] > d[i][j]:
			ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:

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

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

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

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


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

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

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

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

Submission status: Wrong Answer

Solution code:
import copy

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

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

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

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


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

dist = copy.deepcopy(graph)


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

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

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

Submission status: Wrong Answer

Solution code:
import copy

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

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

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

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


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

dist = copy.deepcopy(graph)


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

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

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

Submission status: Wrong Answer

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

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

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

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


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

# WF
min_root = [[[] for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        min_root[i][j].append(j)
        
for i in range(N):
    for j in range(N):
        for k in range(N):
            if graph[i][j] >= graph[i][k]+graph[k][j]:
                graph[i][j] = graph[i][k]+graph[k][j]
                min_root[i][j].append(k)
       
for i in range(N):
    for j in range(N):
        min_root[i][j].append(i)
        
# 辺集合
edge_list = []
for a,b,c in ABC:
    edge_list.append([a-1,b-1])
    
# 削除
for i in range(N):
    for j in range(N):
        for k in range(len(min_root[i][j])-1):
            if i==j:
                continue
            
            if [min_root[i][j][k], min_root[i][j][k+1]] in edge_list:
                edge_list.remove([min_root[i][j][k], min_root[i][j][k+1]])
                
                
            elif [min_root[i][j][k+1], min_root[i][j][k]] in edge_list:
                edge_list.remove([min_root[i][j][k+1], min_root[i][j][k]])
                
                
print(len(edge_list))

Submission status: Wrong Answer

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

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

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

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


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

# WF
min_root = [[[] for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        min_root[i][j].append(j)
        
for i in range(N):
    for j in range(N):
        for k in range(N):
            if graph[i][j] > graph[i][k]+graph[k][j]:
                graph[i][j] = graph[i][k]+graph[k][j]
                min_root[i][j].append(k)
       
for i in range(N):
    for j in range(N):
        min_root[i][j].append(i)
        
# 辺集合
edge_list = []
for a,b,c in ABC:
    edge_list.append([a-1,b-1])
    
# 削除
for i in range(N):
    for j in range(N):
        for k in range(len(min_root[i][j])-1):
            if i==j:
                continue
            
            if [min_root[i][j][k], min_root[i][j][k+1]] in edge_list:
                edge_list.remove([min_root[i][j][k], min_root[i][j][k+1]])
                
                
            elif [min_root[i][j][k+1], min_root[i][j][k]] in edge_list:
                edge_list.remove([min_root[i][j][k+1], min_root[i][j][k]])
                
                
print(len(edge_list))

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
connect = {}
dist = {}
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in connect.keys(): connect[a] = [b]
    else: connect[a].append(b)
    if not b in connect.keys(): connect[b] = [a]
    else: connect[b].append(a)
    
    dist[tuple(sorted([a, b]))] = c

ans = 0
for s in range(1, n):
    for t in range(s+1, n+1):
        if not (s, t) in dist.keys():
            continue
        
        dists = [1000]*(n+1)
        dists[s] = 0
        stack = [(s, sc) for sc in connect[s]]
        while len(stack) > 0:
            s0, s1 = stack[0]
            stack = stack[1:]
            if dists[s0]+dist[tuple(sorted((s0, s1)))] >= dists[s1]:
                continue
            else:
                dists[s1] = dists[s0]+dist[tuple(sorted((s0, s1)))]
                for s2 in connect[s1]:
                    stack.append((s1, s2))
        print(dists)
        if dists[t] < dist[(s, t)]:
            ans += 1

print(ans)

Submission status: Wrong Answer

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

ans = 0

for i in range(n):
	for j in range(i + 1, n):
		if d[i][j] == float("inf"):
			continue
		for k in range(n):
			if d[i][k] + d[k][j] < d[i][j]:
				ans += 1
				break

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G = [[float('inf')]*N for i in range(N)]
G2 = [[float('inf')]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = c
    G[b-1][a-1] = c
    G2[a-1][b-1] = c
    G2[b-1][a-1] = c

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

changed = set()
for i in range(N):
    for j in range(N):
        if G[i][j] != G2[i][j]:
            changed.add((i, j))

print(M - len(changed)//2)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G = [[float('inf')]*N for i in range(N)]
G2 = [[float('inf')]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = c
    G[b-1][a-1] = c
    G2[a-1][b-1] = c
    G2[b-1][a-1] = c

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

changed = set()
for i in range(N):
    for j in range(N):
        if G[i][j] != G2[i][j]:
            changed.add((i, j))

print(M - len(changed)//2)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G = [[float('inf')]*N for i in range(N)]
G2 = [[float('inf')]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = c
    G[b-1][a-1] = c
    G2[a-1][b-1] = c
    G2[b-1][a-1] = c

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

cnt = 0
for i in range(N):
    for j in range(N):
        for k in range(N):
            if G[i][j] != G2[i][j]:
                cnt += 1

print(M - cnt//2)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G = [[float('inf')]*N for i in range(N)]
G2 = [[float('inf')]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = c
    G[b-1][a-1] = c
    G2[a-1][b-1] = c
    G2[b-1][a-1] = c

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

cnt = 0
for i in range(N):
    for j in range(N):
        if G[i][j] != float('inf') and G2[i][j] != float('inf') and G[i][j] != G2[i][j]:
            cnt += 1

print(cnt//2)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
G = [[float('inf')]*N for i in range(N)]

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

distance, path = dijkstra(G, directed=False, return_predecessors=True)

used = set()
for i in range(N):
    for j in range(N):
        t = j
        while i != t:
            t = path[i][t]
            if path[i][t] != t:
                used.add((path[i][t], t))

K = len(used)
for l, r in used:
    if l < 0 or r < 0:
        K -= 1
print(M - K)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
G = [[float('inf')]*N for i in range(N)]

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

distance, path = dijkstra(G, directed=False, return_predecessors=True)

used = set()
for i in range(N):
    for j in range(N):
        if i != j and i != path[i][j]:
            used.add((i, path[i][j]))
            
print(M - len(used))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
G = [[float('inf')]*N for i in range(N)]

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

distance, path = dijkstra(G, directed=False, return_predecessors=True)
K = 0
for p in path:
    K = max(K, len(set(p))-1)
print(M-K)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G = [[float('inf')]*N for i in range(N)]

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

cnt = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if G[i][j] > G[i][k]+G[k][j]:
                G[i][j] = G[i][k]+G[k][j]
                flg = True
    if flg:
        cnt += 1
    flg = False

print(M - cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G = [[float('inf')]*N for i in range(N)]

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

used = set()
for i in range(N):
    for j in range(N):
        for k in range(N):
            if G[i][j] >= G[i][k]+G[k][j]:
                G[i][j] = G[i][k]+G[k][j]
                use = k
        if i != k:
            used.add((i, k))

print(M - len(used))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G1 = [[float('inf')]*N for i in range(N)]
G2 = [[float('inf')]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G1[a-1][b-1] = c
    G1[b-1][a-1] = c
    G2[a-1][b-1] = c
    G2[b-1][a-1] = c

used = set()
for i in range(N):
    for j in range(N):
        for k in range(N):
            if G1[i][j] > G1[i][k]+G1[k][j]:
                G1[i][j] = G1[i][k]+G1[k][j]
                use1 = (i+1, k+1)
                use2 = (k+1, j+1)
        used.add(use1)
        used.add(use2)
#print(used)
print(M - len(used) // 2)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G1 = [[float('inf')]*N for i in range(N)]
G2 = [[float('inf')]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G1[a-1][b-1] = c
    G1[b-1][a-1] = c
    G2[a-1][b-1] = c
    G2[b-1][a-1] = c

used = set()
for i in range(N):
    for j in range(N):
        for k in range(N):
            if G1[i][j] > G1[i][k]+G1[k][j]:
                G1[i][j] = G1[i][k]+G1[k][j]
                if i != k:
                    use1 = (i, k)
                if j != k:
                    use2 = (k, j)
        used.add(use1)
        used.add(use2)

print(M - len(used)// 2)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
G = [[10**5 for _ in range(N)] for _ in range(N)]
E = []
Ans = 0

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

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

for i in range(M):
    a,b,c = E[i]
    for j in range(N):
        if G[j][b-1] == G[j][a-1] + c:
           break
    else:
        Ans += 1

print(Ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return map(int, input().split())
N, M = inpl()

G = [[0]*(N) for _ in range(N)]
E = []
for _ in range(M):
    a, b, c = inpl()
    G[a-1][b-1] = c
    G[b-1][a-1] = c
    E.append([a-1, b-1, c])

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

print(sum([G[a][b] < c for a, b, c in E]))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
d=[[float('inf') for x in range(N)] for y in range(N)]
e=[[0 for x in range(N)] for y in range(N)]
for i in range(N):
  d[i][i]=0
ans=[]
for i in range(M):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=c
  d[b-1][a-1]=c
  ans.append([a-1,b-1,c])

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

res=0
for a,b,c in ans:
  if e[a][b]==0 and e[b][a]==0:
    res+=1
print(res)

Submission status: Wrong Answer

Solution code:
INF=100000000000


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

n,m = map(int,input().split())
dist=[[INF]*n for i in range(n)]
edges=[]

for i in range(m):
    ai,bi,ci=map(int,input().split())
    edges.append(tuple([ai-1,bi-1,ci]))
    dist[ai-1][bi-1]=ci
    dist[bi-1][ai-1]=ci

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

floyd_warshall(dist)

#print(dist)
ans = m
for edge in edges:
    ai,bi,ci=edge
    flag = 0
    for s in range(n):
        if dist[s][ai]+ci == dist[s][bi]:
            flag+=1

    if flag > 0:
        ans-=1

print(ans)

Submission status: Wrong Answer

Solution code:
INF=100000000000


def floyd_warshall(dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if (dist[i][j] > dist[i][k]+dist[k][j]):
                    dist[i][j] = dist[i][k]+dist[k][j]
                    dist[j][i] = dist[i][k]+dist[k][j]

n,m = map(int,input().split())
dist=[[INF]*n for i in range(n)]
edges=[]

for i in range(m):
    ai,bi,ci=map(int,input().split())
    edges.append(tuple([ai-1,bi-1,ci]))
    dist[ai-1][bi-1]=ci
    dist[bi-1][ai-1]=ci

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

floyd_warshall(dist)

#print(dist)
ans = m
for edge in edges:
    ai,bi,ci=edge
    flag = 0
    for s in range(n):
        if dist[s][ai]+ci == dist[s][bi]:
            flag+=1

    if flag > 0:
        ans-=1

print(ans)

Submission status: Wrong Answer

Solution code:
INF=100000000000


def floyd_warshall(dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if (dist[i][j] > dist[i][k]+dist[k][j]):
                    dist[i][j] = dist[i][k]+dist[k][j]
                    dist[j][i] = dist[i][k]+dist[k][j]

n,m = map(int,input().split())
dist=[[INF]*n for i in range(n)]
edges=[]

for i in range(m):
    ai,bi,ci=map(int,input().split())
    edges.append(tuple([ai-1,bi-1,ci]))
    dist[ai-1][bi-1]=ci
    dist[bi-1][ai-1]=ci

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

floyd_warshall(dist)

#print(dist)
count = 0
for edge in edges:
    ai,bi,ci=edge
    flag = 0
    for s in range(n):
        if dist[s][ai]+ci == dist[s][bi]:
            flag+=1

    if flag > 0:
        count+=1

print(m-count)