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 *
import numpy as np

def dijkstra(start,node,edge):
    #始点sから各頂点への最短距離
    #node:頂点数
    #d:各頂点へのコスト(存在しないときはinf)
    d = [float("inf")] * node
    d[start] = 0
    q = [(0,start)]
    
    while(len(q) != 0):
      ci,i = heappop(q)
      if(d[i] < ci):
        continue
      for cj,j in edge[i]:
        if(d[j] > d[i] + cj):
          d[j] = d[i] + cj
          used[i][j] = 1
          heappush(q,(d[j], j))
    return d
  
N,M = (int(x) for x in input().split())
E = [[] for _ in [0]*N]
used = np.zeros((N,N))

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

d = dijkstra(0, N, E)

print(int(M - np.sum(used)))

Submission status: Wrong Answer

Solution code:
from heapq import *
import numpy as np

def dijkstra(start,node,edge):
    #始点sから各頂点への最短距離
    #node:頂点数
    #d:各頂点へのコスト(存在しないときはinf)
    d = [float("inf")] * node
    d[start] = 0
    q = [(0,start)]
    
    while(len(q) != 0):
      ci,i = heappop(q)
      if(d[i] < ci):
        continue
      for cj,j in edge[i]:
        if(d[j] > d[i] + cj):
          d[j] = d[i] + cj
          used[i][j] = 1
          heappush(q,(d[j], j))
    return d
  
N,M = (int(x) for x in input().split())
E = [[] for _ in [0]*N]
used = np.zeros((N,N))

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

d = dijkstra(0, N, E)

print(int(M - np.sum(used)))

Submission status: Wrong Answer

Solution code:


from heapq import heappush, heappop, heapify

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

#abcm = [ list( map(int,input().split()) ) for _ in range(m)]


graph = [[0]*n for _ in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split())
    a-= 1;b-=1

    graph[a][b] = graph[b][a] = c

#print(graph)

# Prim's Algorithm
# https://tjkendev.github.io/procon-library/python/graph/min_st_prim.html

print(m - (n-1) )

def prim():
    heap = [(c, i) for i, c in enumerate(graph[0]) if c != 0]
    heapify(heap)
    visited = [False]*n
    visited[0] = True

    from_ = 0
    to_ = 0
    edge = []

    while heap:
        c, v = heappop(heap)

        if visited[v] :
            continue
    
        to_ = v
        edge.append( (from_,to_) )
        from_ = to_
        for i, c in enumerate(graph[v]):
            if visited[i] :
                continue
            heappush(heap, (c, i))

        visited[v] = True
        

    #print(heap)

    #print(edge)

    print( m - len(edge) )

#prim()

Submission status: Wrong Answer

Solution code:


from heapq import heappush, heappop, heapify

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

#abcm = [ list( map(int,input().split()) ) for _ in range(m)]


graph = [[0]*n for _ in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split())
    a-= 1;b-=1

    graph[a][b] = graph[b][a] = c

#print(graph)

# Prim's Algorithm
# https://tjkendev.github.io/procon-library/python/graph/min_st_prim.html

heap = [(c, i) for i, c in enumerate(graph[0]) if c != 0]
heapify(heap)
visited = [False]*n
visited[0] = True

from_ = 0
to_ = 0
edge = []

while heap:
    c, v = heappop(heap)

    if visited[v] :
        continue
    
    to_ = v
    edge.append( (from_,to_) )
    from_ = to_
    for i, c in enumerate(graph[v]):
        if visited[i] :
            continue
        heappush(heap, (c, i))

    visited[v] = True
        

#print(heap)

#print(edge)

print( m - len(edge) )

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = [[] for _ in range(N)]
    used_edge = set()

    # ダイクストラ
    def dijkstra(start, edge):
        costs=[inf]*N
        costs[start]=0
        hash={}
        queue = [(0, start, (-1,-1))]  # 第一要素が優先的に評価されるので 第３要素にpre(前の頂点)が入る
        pre_node = [-1]*N
        while queue:
            c, from_ ,e=heappop(queue)
            if from_ in hash:
                continue
            hash[from_] = 1
            costs[from_] = c
            used_edge.add(e)
            #pre_node[from_]=pre
            for cost,node in edge[from_]:
                if node in hash:
                    continue
                e = tuple(sorted([from_,node]))
                heappush(queue, (c + cost, node,e))

        return costs


    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge[a].append((c, b))
        edge[b].append((c, a))
        
    for start in range(N):
        costs = dijkstra(start, edge)
    
    num_used_edge = len(used_edge)-1
    print(M-num_used_edge)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=[3,3]
l=[[1,2,1],[1,3,1],[2,3,3]]
inf=10**20
a=[[inf]*N for i in range(N)]
e=[[0]*N for i in range(N)]
for i,j,k in l:
    a[i-1][j-1]=k
    a[j-1][i-1]=k
    e[i-1][j-1]=1
    e[j-1][i-1]=1

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

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
edge=[list(map(int,input().split())) for i in range(M)]
inf=10**20
c=[[inf]*N for i in range(N)]
e=[[0]*N for i in range(N)]
for i,j,w in edge:
    c[i-1][j-1]=w
    c[j-1][i-1]=w
    e[i-1][j-1]=1
    e[j-1][i-1]=1
for i in range(N):
    c[i][i]=0
ans=0
def wf(c,N):
    global ans
    for k in range(N):
        for i in range(N-1):
            for j in range(i+1,N):
                if c[i][j]>c[i][k]+c[k][j]:
                    if e[i][j]==1:
                        ans+=1
                    c[i][j]=c[i][k]+c[k][j]
wf(c,N)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
edge=[list(map(int,input().split())) for i in range(M)]
inf=10**20
c=[[inf]*N for i in range(N)]
for i,j,w in edge:
    c[i-1][j-1]=w
    c[j-1][i-1]=w
for i in range(N):
    c[i][i]=0
ans=0
def wf(c,N):
    global ans
    for k in range(N):
        for i in range(N-1):
            for j in range(i+1,N):
                if c[i][j]>c[i][k]+c[k][j]:
                    if c[i][j]<inf:
                        ans+=1
                    c[i][j]=c[i][k]+c[k][j]
wf(c,N)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
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
    n=1
    for b,c in G[i]:
        heapq.heappush(stack,(g[i]+c,i,b))
    used=[[0]*N for i in range(N)]
    while(stack):
        if n==N:
            break
        c,a,b=heapq.heappop(stack)
        g[b]=c
        n+=1
        used[a][b]=1
        used[b][a]=1
        for j in G[b]:
            if used[b][j[0]] or g[j[0]]!=INF:
                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: Wrong Answer

Solution code:
from collections import deque
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=deque([(i,0,-1)])
    g=[INF for i in range(N)]
    used=[[0]*N for i in range(N)]
    while(stack):
        b,c,p=stack.popleft()
        if p==-1:
            g[b]=0
        else:
            g[b]=min(g[b],g[p]+c)
            used[p][b]=1
            used[b][p]=1

        for j in G[b]:
            if used[b][j[0]]:
                continue
            stack.append((j[0],j[1],b))
    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: Wrong Answer

Solution code:
from collections import deque
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=deque([(i,0,-1)])
    g=[INF for i in range(N)]
    used=[[0]*N for i in range(N)]
    while(stack):
        b,c,p=stack.popleft()
        if p==-1:
            g[b]=0
        else:
            g[b]=min(g[b],g[p]+c)
            used[p][b]=1
            used[b][p]=1

        for j in G[b]:
            if used[b][j[0]]:
                continue
            stack.append((j[0],j[1],b))
    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: Wrong Answer

Solution code:
#coding:utf-8

N,M=map(int,raw_input().split())
D=[[1145141919]*101 for _ in range(101)]

A=set()
for i in range(M):
    a,b,c=map(int,raw_input().split())
    D[a][b]=c;D[b][a]=c
    A.add((min(a,b),max(a,b)))
P={}
for i in range(1,N+1):
    P[(i,i)]=i
    D[i][i]=0
    for j in range(1,N+1):
        P[(i,j)]=j
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if D[i][j]>D[i][k]+D[k][j]:
                D[i][j]=D[i][k]+D[k][j]
                P[(i,j)]=k
#for i in range(1,N+1):
#    print(D[i][1:N+1])
def rec(s,e):
    if s==e:return [s]
    k=P[(s,e)]
    if s==k or k==e:
        return [s,e]
    return rec(s,k)+rec(k,e)
for s in range(1,N+1):
    for e in range(s+1,N+1):
        p=rec(s,e)
        f=[p[0]]
        for pp in p[1:]:
            if f[-1]!=pp:f.append(pp)
        s=f[0]
        for e in f[1:]:
            p=(min(s,e),max(s,e))
            if p in A:
                A.remove(p)
            s=e
print(len(A))

Submission status: Wrong Answer

Solution code:
#import numpy as np
N,M=map(int,input().split())
inf=10**9

class Node():
	def __init__(self, ix):
		self.ix = ix # ノード番号
		self.done = False # 確定ノードかどうか
		self.pay = {} # 頂点番号:コストの一覧を容れる辞書
		self.paid = -1 # ここに到達するための最小コスト(未定義なら-1)
		self.prev = -1 # 最小コストを与える親ノード(未定義なら-1)
	def __str__(self):
		# デバッグ用
		return '{} <- [{}] <- {}, done:{}, pay:{}'.format(self.ix, self.paid, self.prev, self.done, self.pay)

# ノードのリストを生成
nodes = []
for i in range(N):
	nodes.append(Node(i))

# エッジのリストを生成(これはこの問題用)
# edges = np.zeros((N,N), dtype=np.uint8) # NumPy
edges = []
for _ in range(N):
	edges.append([0]*N)

# エッジ情報を取得
# 全エッジを格納
# 注意: 標準入力は1-indexedだがここでは0-indexedに直す
for _ in range(M):
	a,b,c = map(int,input().split())
	nodes[a-1].pay[b-1] = c
	nodes[b-1].pay[a-1] = c
	edges[a-1][b-1] = 1
	edges[b-1][a-1] = 1
		
		
# 出発ノードを0からN-1まで変化させる
for i in range(N):
	nodes[i].prev = i # 出発点の最良親を自分自身に
	nodes[i].paid = 0 # 出発点のコストは0
	nodes[i].done = True # 出発点は確定済み
	n_done = 1 # 確定ノード数を1に
	while n_done < N: # 全部確定するまで続行
		to_conf_ix = -1 # 次に確定されるべきノード番号
		to_conf_paid = 10**9 # そのコスト
		for node in nodes:
			# 確定ノードすべてに対して操作を行う
			if node.done:
				# 接続先を全列挙
				for child in list(node.pay.keys()):
					# その接続先が未確定なら処理続行
					if not nodes[child].done:
						# その接続先の仮の最小コストと仮の親を更新
						# まだ確定済みにはしない
						newcost = node.paid + node.pay[child]
						# 更新するための条件
						flag = (nodes[child].paid < 0) or (newcost < nodes[child].paid)
						# 条件をみたせば接続先の情報を更新
						# また次に確定されるノード候補の情報も更新
						if flag:
							nodes[child].paid = newcost
							nodes[child].prev = node.ix
							if newcost < to_conf_paid:
								to_conf_paid = newcost
								to_conf_ix = child
		# 操作が完了したら現段階の候補ノードを確定させる
		nodes[to_conf_ix].done = True
		# 確定ノード数を1増やす
		n_done += 1
		
	# 各ノードについてそれを親と連結するパスをedgeから削除
	for j in range(N):
		k = nodes[j].prev
		edges[j][k], edges[k][j] = 0, 0

	# 全ノードのpaid,prevをリセット
	for j in range(N):
		nodes[j].paid, nodes[j].prev = -1, -1

# 最後にedgesに残っているエッジの本数を出力
# print(int(np.sum(edges)//2))  # NumPy
ans = 0
for i in range(N):
	ans += sum(edges[i])
print(ans//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import copy
N, M = map(int, input().split())
G = [[10**9 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    tmp_a, tmp_b, tmp_c = map(int, input().split())
    G[tmp_a-1][tmp_b-1] = tmp_c
    G[tmp_b-1][tmp_a-1] = tmp_c

G_raw = copy.deepcopy(G)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if G[i][k] + G[k][j] < G[i][j]:
                G[i][j] = G[i][k] + G[k][j]
ans = 0
for i in range(N):
    for j in range(N):
        if j <= i:
            continue
        flag = False
        for k in range(N):
            if i == k or k == j:
                continue
            if G_raw[i][j] != 10**9 and G_raw[k][i] != 10**9 and G_raw[k][j] != 10 ** 9 and G[k][i] + G_raw[i][j] != G[k][j]:
                flag = True
                break
        if flag:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
N, M = map(int, input().split())
G = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    tmp_a, tmp_b, tmp_c = map(int, input().split())
    G[tmp_a-1][tmp_b-1] = tmp_c
    G[tmp_b-1][tmp_a-1] = tmp_c

import copy
G_raw = copy.deepcopy(G)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if G[i][k] + G[k][j] <= G[i][j]:
                G[i][j] = G[i][k] + G[k][j]
ans = 0
for i in range(N):
    for j in range(N):
        if G_raw[i][j] != G[i][j]:
            ans += 1

print(ans//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
N, M = map(int, input().split())
G = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    tmp_a, tmp_b, tmp_c = map(int, input().split())
    G[tmp_a-1][tmp_b-1] = tmp_c
    G[tmp_b-1][tmp_a-1] = tmp_c

import copy
G_raw = copy.deepcopy(G)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if G[i][k] + G[k][j] < G[i][j]:
                G[i][j] = G[i][k] + G[k][j]
ans = 0
for i in range(N):
    for j in range(N):
        if G_raw[i][j] != G[i][j]:
            ans += 1

print(ans//2)

Submission status: Wrong Answer

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

print(M - (N-1))

Submission status: Wrong Answer

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

Solution code:
N, M = map(int, input().split())
INF = int(1e10)
g = [[INF] * N for _ in range(N)]
flag = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    g[a-1][b-1], g[b-1][a-1] = c, c

for k in range(N):
    min_cand = [(-1, -1), INF]
    for i in range(N):
        for j in range(N):
            if g[i][k] + g[k][j] <= min_cand[1]:
                min_cand = [(i, j), g[i][k] + g[k][j]]
    if min_cand[1] >= INF:
        continue
    min_i = min_cand[0][0]
    min_j = min_cand[0][1]
    g[min_i][min_j] = min_cand[1]
    flag[min_i][k],  flag[k][min_j] = True, True

count = 0
for i in range(N):
    for j in range(N):
        if flag[i][j] is True:
            count += 1
count //= 2
print(M - count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
INF = int(1e10)
g = [[INF] * N for _ in range(N)]
flag = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    g[a-1][b-1], g[b-1][a-1] = c, c

for k in range(N):
    min_cand = [(-1, -1), INF]
    for i in range(N):
        for j in range(N):
            if g[i][k] + g[k][j] <= min_cand[1]:
                min_cand = [(i, j), g[i][k] + g[k][j]]
    if min_cand[1] == INF:
        continue
    min_i = min_cand[0][0]
    min_j = min_cand[0][1]
    g[min_i][min_j] = min_cand[1]
    flag[min_i][k],  flag[k][min_j] = True, True

count = 0
for i in range(N):
    for j in range(N):
        if flag[i][j] is True:
            count += 1
count //= 2
print(M - count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
INF = int(1e10)
g = [[INF] * N for _ in range(N)]
flag = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    g[a-1][b-1], g[b-1][a-1] = c, c

for k in range(N):
    min_cand = [(-1, -1), INF]
    for i in range(N):
        for j in range(N):
            if g[i][k] + g[k][j] <= min_cand[1]:
                min_cand = [(i, j), g[i][k] + g[k][j]]
    min_i = min_cand[0][0]
    min_j = min_cand[0][1]
    g[min_i][min_j] = min_cand[1]
    flag[min_i][k],  flag[k][min_j] = True, True

count = 0
for i in range(N):
    for j in range(N):
        if flag[i][j] is True:
            count += 1
count //= 2
print(M - count)

Submission status: Wrong Answer

Solution code:
import copy
N, M = map(int, input().split())
INF = 2 ** 63 - 1
d = [[INF for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
    d[i][i] = 0

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

d_original = copy.deepcopy(d)

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

ans = 0
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if d_original[i][j] != INF and d[i][j] != d_original[i][j]:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
	INF = 10**9+7
	N, M = map(int, input().split())
	dist = [[INF for _ in range(N+1)] for _ in range(N+1)]
	a, b, c = [0]*M, [0]*M, [0]*M
	for i in range(M):
		a[i], b[i], c[i] = map(int, input().split())
		dist[a[i]][b[i]] = c[i]
		dist[b[i]][a[i]] = c[i]
	for i in range(1, N+1):
		for j in range(1, N+1):
			if i == j:
				dist[i][j] = 0
			for k in range(1, N+1):
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
	ans = M
	for i in range(M):
		shrotest = False
		for j in range(1, N+1):
			if dist[j][a[i]]+c[i] == dist[j][b[i]]:
				shrotest = True
		if shrotest:
			ans -= 1
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
	INF = 10**9+7
	N, M = map(int, input().split())
	dist = [[INF for _ in range(N+1)] for _ in range(N+1)]
	a, b, c = [0]*M, [0]*M, [0]*M
	for i in range(M):
		a[i], b[i], c[i] = map(int, input().split())
		dist[a[i]][b[i]] = c[i]
		dist[b[i]][a[i]] = c[i]
	for i in range(1, N+1):
		for j in range(1, N+1):
			for k in range(1, N+1):
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
	ans = M
	for i in range(M):
		shrotest = False
		for j in range(1, N+1):
			if dist[j][a[i]]+c[i] == dist[j][b[i]]:
				shrotest = True
		if shrotest:
			ans -= 1
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
	INF = 10**9+7
	N, M = map(int, input().split())
	dist = [[INF for _ in range(N+1)] for _ in range(N+1)]
	for _ in range(M):
		a, b, c = map(int, input().split())
		dist[a][b] = c
		dist[b][a] = c
	ans = 0
	for i in range(1, N+1):
		for j in range(i+1, N+1):
			if dist[i][j] == INF:
				continue
			for k in range(1, N+1):
				if dist[i][j] >= dist[i][k] + dist[k][j]:
					ans += 1
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
	INF = 10**9+7
	N, M = map(int, input().split())
	dist = [[INF for _ in range(N+1)] for _ in range(N+1)]
	for _ in range(M):
		a, b, c = map(int, input().split())
		dist[a][b] = c
		dist[b][a] = c
	ans = 0
	for i in range(1, N+1):
		for j in range(i+1, N+1):
			if dist[i][j] == INF:
				continue
			for k in range(1, N+1):
				if dist[i][j] > dist[i][k] + dist[k][j]:
					ans += 1
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
	N, M = map(int, input().split())
	points = [[] for _ in range(N+1)]
	for i in range(1, M+1):
		a, b, c = map(int, input().split())
		points[a].append([b, c])
		points[b].append([a, c])
	is_visited = [False]*(N+1)
	is_visited[0] = True
	def dijksta(start):
		is_visited[start] = True
		stack = list(points[start])
		edge = 0
		while stack:
			edge += 1
			stack.sort(key=lambda x: x[1])
			use_edge = stack.pop()
			cur = use_edge[0]
			dist = use_edge[1]
			is_visited[cur] = True
			if all(is_visited):
				return edge
			add_stack = list(points[cur])
			removes = []
			for i, pair in enumerate(add_stack):
				if is_visited[pair[0]]:
					removes.append(i)
					continue
				add_stack[i][1] += dist
			removes.reverse()
			for i in removes:
				add_stack.pop(i)
			stack.extend(add_stack)

	ans = M - dijksta(1)
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
	N, M = map(int, input().split())
	points = [[] for _ in range(N+1)]
	for i in range(1, M+1):
		a, b, c = map(int, input().split())
		points[a].append([b, c])
		points[b].append([a, c])
	is_visited = [False]*(N+1)
	is_visited[0] = True
	def dijksta(start):
		is_visited[start] = True
		stack = list(points[start])
		edge = 0
		while stack:
			edge += 1
			stack.sort(key=lambda x: x[1])
			use_edge = stack.pop()
			cur = use_edge[0]
			dist = use_edge[1]
			is_visited[cur] = True
			if all(is_visited):
				return edge
			add_stack = list(points[cur])
			removes = []
			for i, pair in enumerate(add_stack):
				if is_visited[pair[0]]:
					removes.append(i)
					continue
				pair[1] += dist
			removes.reverse()
			for i in removes:
				add_stack.pop(i)
			stack.extend(add_stack)

	ans = M - dijksta(1)
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
	N, M = map(int, input().split())
	points = [[] for _ in range(N+1)]
	for i in range(1, M+1):
		a, b, c = map(int, input().split())
		points[a].append([b, c])
		points[b].append([a, c])
	is_visited = [False]*(N+1)
	is_visited[0] = True
	def dijksta(start):
		is_visited[start] = True
		stack = list(points[start])
		dist = 0
		edge = 0
		while stack:
			edge += 1
			stack.sort(key=lambda x: x[1])
			cur = stack.pop()[0]
			is_visited[cur] = True
			if all(is_visited):
				return edge
			add_stack = list(points[cur])
			removes = []
			for i, pair in enumerate(add_stack):
				if is_visited[pair[0]]:
					removes.append(i)
					continue
				pair[1] += dist
			removes.reverse()
			for i in removes:
				add_stack.pop(i)
			stack.extend(add_stack)

	ans = M - dijksta(1)
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 = [(s, 0)]
    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()