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:
N,M=list(map(int,input().split()))
from scipy.sparse.csgraph import shortest_path,dijkstra
from scipy.sparse import csr_matrix
l=[[0]*N for i in range(N)]
ans=set()
for i in range(M):
   tmp=(list(map(int,input().split())))
   l[tmp[0]-1][tmp[1]-1]=tmp[2]
   l[tmp[1]-1][tmp[0]-1]=tmp[2]
csr=csr_matrix(l)
d,p=dijkstra(csr,return_predecessors=True)
S=p[0]

def path(N,index):
   while N != 0:
      ans.add((min(N,index),max(N,index)))
      index=N
      N=p[0][N]
   else:
      ans.add((min(N,index),max(N,index)))
for i,j in enumerate(S):
   if j == -9999:
      continue
   elif j == 0:
      ans.add((0,i))
   else:
      path(j,i)
print(M-len(ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq


def check(N, adj_nodes, costs, from_node, to_node):
    # calculate shortest distances on a graph without a edge (from_node, to_node)
    INF = 10 ** 6
    dists = [INF for _ in range(N)]
    frontier = [(0, from_node)]
    while len(frontier) > 0:
        d, node = heapq.heappop(frontier)
        dists[node] = d
        for next_node in adj_nodes[node]:
            if (from_node, to_node) == (node, next_node):
                continue
            next_d = costs[(node, next_node)] + dists[node]
            if dists[next_node] > next_d:
                heapq.heappush(frontier, (next_d, next_node))
    return costs[(from_node, to_node)] > dists[to_node]


def main():
    N, M = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    costs = defaultdict(int)
    edges = list()
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
        costs[(a, b)] = c
        costs[(b, a)] = c
        edges.append((a, b))
    ans = 0
    for edge in edges:
        from_node, to_node = edge
        if check(N, adj_nodes, costs, from_node, to_node):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
INF = 10**10
edge_idx = {}
graph = [[] for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  a -= 1; b -= 1
  graph[a].append((b, c))
  graph[b].append((a, c))
  edge_idx[(a, b)] = edge_idx[(b, a)] = i

used = set()
def dijkstra(node):
  global used
  dist = [INF] * N
  dist[node] = 0
  e = []
  for child, cost in graph[node]:
    heappush(e, (cost, child, node))
  while e:
    cost, node, par = heappop(e)
    if dist[node] < INF:
      continue
    dist[node] = cost
    used.add(edge_idx[(node, par)])
    for child, c in graph[node]:
      if dist[child] < INF:
        continue
      heappush(e, (cost+c, child, node))

for i in range(N):
  dijkstra(i)

print(M - len(used))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
INF = 10**6
edge_idx = {}
graph = [[] for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  a -= 1; b -= 1
  graph[a].append((b, c))
  graph[b].append((a, c))
  edge_idx[(a, b)] = edge_idx[(b, a)] = i

used = set()
def dijkstra(node):
  global used
  dist = [INF] * N
  dist[node] = 0
  e = []
  for child, cost in graph[node]:
    heappush(e, (cost, child, node))
  while e:
    cost, node, par = heappop(e)
    if dist[node] < INF:
      continue
    dist[node] = cost
    used.add(edge_idx[(node, par)])
    for child, c in graph[node]:
      if dist[child] < INF:
        continue
      heappush(e, (cost+c, child, node))

for i in range(N):
  dijkstra(i)

print(M - len(used))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000001)

def main():
    n, m = map(int, input().rstrip().split())
    dist = [[500000 for i in range(n)]for j in range(n)]

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

    a = [None] * m
    b = [None] * m
    c = [None] * m

    for i in range(m):
        x, y, z = map(int, input().rstrip().split())
        dist[x-1][y-1] =  min(dist[x-1][y-1], z)
        dist[y-1][x-1] =  min(dist[x-1][y-1], z)
        a[i] = x - 1
        b[i] = y - 1
        c[i] = z - 1
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
    #print(dist)
    result = m

    for i in range(m):
        for j in range(n):
            if dist[j][a[i]] + c[i] == dist[j][b[i]]:
                result -= 1
                break

    print(result)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split()) #n:頂点数　w:辺の数
from collections import defaultdict
D=defaultdict(list)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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]
                    D[(i,j)]=D[(i,k)]+D[(k,j)][1:]
    return d
done=[[-1]*n for _ in range(n)]
d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
    D[(x-1,y-1)]=[x-1,y-1]
    D[(y-1,x-1)]=[y-1,x-1]
    done[x-1][y-1]=0
    done[y-1][x-1]=0
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)
for l in D.values():
    for i in range(1,len(l)):
        a=l[i-1]
        b=l[i]
        done[a][b]=1
        done[b][a]=1
import numpy as np
done=np.array(done)
ans=(done==0).sum()
#print(D)
#print(done)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N,M = map(int,input().split())
INF = float("inf")
edge = [[] for _ in range(N)]
#print(load)
#dis = [[] for _ in range(N)]
ID = [0 for _ in range(M)] #0は未使用、1は使用
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  edge[a].append([c,b,i])
  edge[b].append([c,a,i])

def dijkstra_heap(s):
  d = [INF for _ in range(N)]
  used = [True for _ in range(N)]
  d[s] = 0
  used[s] = False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]: #すでに探索済みの場合にはスキップ
      continue
    v = minedge[1]
    d[v] = minedge[0]
    ID[minedge[2]] = 1 #この道を使用したと記録
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1],e[2]])
  return d

for i in range(N):
  dijkstra_heap(i)

ans = M -sum(ID)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
INF = float("inf")
load = [[[INF, 0] for _ in range(N)] for _ in range(N)]
#print(load)
#dis = [[] for _ in range(N)]
#ID = [0 for _ in range(M)] #、0は未使用、1は使用
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  load[a][b] = [c,0]
  load[b][a] = [c,0]
  #dis[a].append([b,i])
  #dis[b].append([a,i])
#for i in range(N):
for i in range(N):
  load[i][i] = [0,0]
#print(load)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if load[i][j][0] > load[i][k][0]+load[k][j][0]:
        load[i][j][1] = 1
#print(load)
ans = 0
for i in range(N):
  for j in range(i+1,N):
    if load[i][j][0] != INF and load[i][j][1] == 1:
      ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
from collections import deque
v = [deque([]) for _ in range(N)]

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

s = deque([])
for i in range(N):
    ls = [[-1,M*10000]]*N
    ls[i] =  [-1,0]
    q = [deque(j for j in k) for k in v]
    l = deque([i])
    while l:
        u = l.popleft()
        while q[u]:
            e = q[u].popleft()
            if ls[u][1] + e[1] < ls[e[0]][1]:
                ls[e[0]] = [u, ls[u][1] + e[1]]
                l.append(e[0])
    for j,e in enumerate(ls):
        if e[0] != -1:
             s.append([min(j,e[0]),max(j,e[0])])

s = list(map(list, set(map(tuple, s))))
print(M-len(s))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
from collections import deque
v = [deque([]) for _ in range(N)]

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

s = deque([])
for i in range(N):
    ls = [[-1,M*1000]]*N
    ls[i] =  [-1,0]
    q = [deque(j for j in i) for i in v]
    l = deque([i])
    while l:
        u = l.popleft()
        while q[u]:
            e = q[u].popleft()
            if ls[u][1] + e[1] < ls[e[0]][1]:
                ls[e[0]] = [u, ls[u][1] + e[1]]
                l.append(e[0])
    for j,e in enumerate(ls):
        if e[0] != -1:
             s.append([min(j,e[0]),max(j,e[0])])

s = list(map(list, set(map(tuple, s))))
print(M-len(s))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
N,M = map(int,input().split())
start = []
goal = []
data = []
for _ in range(M):
    a,b,c = map(int,input().split())
    start.append(a)
    goal.append(b)
    data.append(c)
csr = csr_matrix((data,(start,goal)),shape=(N+1,N+1))
p,q = floyd_warshall(csr,directed=False,return_predecessors=True)
d=[[True]*N for _ in range(N)]
for i in range(1,N+1):
    for k,v in enumerate(q[i]):
        if v != -9999:
            d[i-1][v-1]=False
            d[v-1][i-1]=False
print(sum([sum(i) for i in d])//2)

Submission status: Wrong Answer

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

INF = 10**10

# Warshall-Floyd
dist = [[INF for _ in range(n)] for _ in range(n)]
edge = []
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1
    dist[a][b] = c
    dist[b][a] = c
    edge.append([a, b, c])

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

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

ans = m
for e in edge:
    flag = False
    i, j, c = e
    print(i, j)
    for s in range(n):
        if flag:
            break
        for t in range(n):
            if dist[s][i]+c+dist[j][t] == dist[s][t]:
                flag = True
                break
    if flag:
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import bisect

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7
# mod = 998244353


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class UF:
    def __init__(self, N):
        self.state = [-1] * N
        self.rank = [0] * N
        self.num_group = N

    def get_parent(self, a):
        p = self.state[a]
        if p < 0:
            return a

        q = self.get_parent(p)
        self.state[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return

        if self.rank[pa] > self.rank[pb]:
            pa, pb = pb, pa
            a, b = b, a
        elif self.rank[pa] == self.rank[pb]:
            self.rank[pb] += 1

        self.state[pb] += self.state[pa]
        self.state[pa] = pb
        self.state[a] = pb
        self.num_group -= 1

    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def get_size(self, a):
        return -self.state[self.get_parent(a)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, M = read_values()
    L = []
    for _ in range(M):
        a, b, c = read_values()
        a -= 1
        b -= 1
        L.append((c, a, b))
    L.sort()

    D = [[10 ** 10 for _ in range(N)] for __ in range(N)]
    for i in range(N):
        D[i][i] = 0

    res = 0
    for c, a, b in L:
        if D[a][b] < c:
            continue

        res += 1
        D[a][b] = c
        D[b][a] = c

        for k in range(N - 1):
            for j in range(k + 1, N):
                D[k][j] = min(D[k][j], D[k][a] + D[a][b] + D[b][j])
                D[j][k] = D[k][j]

    print(M - res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
ma = [[0]*n for _ in range(n)]
list_ABC = [ list(map(int,input().split(" "))) for i in range(m)]
for a, b, c in list_ABC:
  ma[a - 1][b - 1] = c
  ma[b - 1][a - 1] = c

p = csr_matrix(ma)
q = dijkstra(p, directed=False).astype(int)
r = 0

for l in q:
    r += sum(l)

ans = 0

for i in range(m):
    a, b, c = list_ABC[i]
    ma[a-1][b-1] = 0
    ma[b-1][a-1] = 0
    p = csr_matrix(ma)
    q = dijkstra(p, directed=False).astype(int)
    cnt = 0
    for l in q:
        cnt += sum(l)

    if cnt == r:
        ans += 1

    ma[a - 1][b - 1] = c
    ma[b - 1][a - 1] = c

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    d=[[INF]*N for _ in range(N)]
    for _ in range(M):
        a,b,c=map(int1,input().split())
        c+=1
        d[a][b]=c
        d[b][a]=c
    d2=[d[i][:] for i in range(N)]
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d2[i][j]=min(d2[i][j],d2[i][k],d2[k][j])
    ans=0
    for i in range(N):
        for j in range(N):
            if d[i][j]!=INF and d[i][j]!=d2[i][j]:
                ans+=1
    print(ans//2)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

#O(ElogV)
import heapq
def dijkstra_heap(s, n, edges):
    #始点sから各頂点への最短距離
    dist = [float("inf")] * n
    used = [True] * n #True:未確定
    dist[s] = 0
    used[s] = False
    used_edges = set()
    edgelist = []
    for (d, e) in edges[s]:
        heapq.heappush(edgelist, (d, e, s))
    while len(edgelist):
        d, e, s = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[e]:
            continue
        dist[e] = d
        used[e] = False

        if s < e:
            used_edges.add((s, e))
        else:
            used_edges.add((e, s))

        for (nd, ne) in edges[e]:
            if used[ne]:
                heapq.heappush(edgelist, (nd + dist[e], ne, e))
    return dist, used_edges

N, M = map(int, sys.stdin.readline().strip().split())

edges = [[] for _ in range(N)]
all_edges = set()
for _ in range(M):
    a, b, c = map(int, sys.stdin.readline().strip().split())
    edges[a-1].append((c, b-1))
    edges[b-1].append((c, a-1))
    if a < b:
        all_edges.add((a-1, b-1))
    else:
        all_edges.add((b-1, a-1))

for i in range(N):
    min_d, used_edges = dijkstra_heap(i, N, edges)
    # 利用した辺を取り除く
    all_edges -= used_edges

print(len(all_edges))

Submission status: Wrong Answer

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

import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist=[float("inf")]*size_v  
  used=[False]*size_v
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w,i in graph[s]:
    heapq.heappush(hq_edge,(w,v,i))

  while hq_edge:
    min_w,min_v,ei=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    answer_set.add(ei)
    for v,w,ei2 in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v,ei2))

  return dist

graph=[[] for _ in range(N+1)]
for i in range(M):
  a,b,c=map(int,input().split())
  graph[a].append((b,c,i))
  graph[b].append((a,c,i))
#print(graph)

size_v=N+1
answer_set=set()
for i in range(1,N+1):
  dist=dijkstra_heap(i)
  #print(dist)
    
#print(answer_set)
print(M-len(answer_set))

Submission status: Wrong Answer

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

import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist=[float("inf")]*size_v  
  used=[False]*size_v
  prev=[-1]*size_v
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w,i in graph[s]:
    heapq.heappush(hq_edge,(w,v,i))

  while hq_edge:
    min_w,min_v,ei=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    prev[min_v]=ei
    for v,w,ei2 in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v,ei2))

  #return dist
  return prev

graph=[[] for _ in range(N+1)]
for i in range(M):
  a,b,c=map(int,input().split())
  graph[a].append((b,c,i))
  graph[b].append((a,c,i))
#print(graph)

size_v=N+1
answer_set=set()
for i in range(1,N+1):
  prev=dijkstra_heap(i)
  #print(prev)
  for j in range(1,N+1):
    if i==j:
      continue
    answer_set.add(prev[j])
    
#print(answer_set)
print(M-len(answer_set))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(' '))
dist = [[10 ** 9 for _ in range(N)] for _ in range(N)]
edges = []

for _ in range(M):
    a, b, c = map(int, input().split(' '))
    dist[a - 1][b - 1] = min(dist[a - 1][b - 1], c)
    dist[b - 1][a - 1] = min(dist[b - 1][a - 1], c)
    edges.append((a - 1, b - 1, c))

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

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

ans = 0
for (u, v, cost) in edges:
    flag = False
    for i in range(N):
        for j in range(i + 1, N):
            flag |= ((dist[i][u] + cost + dist[v][j]) == dist[i][j])
    ans += 1 - int(flag)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(' '))
dist = [[10 ** 9 for _ in range(N)] for _ in range(N)]
edges = []

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

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

ans = 0
for (u, v, cost) in edges:
    flag = False
    for i in range(N):
        for j in range(i + 1, N):
            flag |= ((dist[i][u] + cost + dist[v][j]) == dist[i][j])
    ans += 1 - int(flag)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(' '))
dist = [[10 ** 9 for _ in range(N)] for _ in range(N)]
edges = []

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

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

ans = 0
for (u, v, cost) in edges:
    flag = True
    for i in range(N):
        for j in range(i + 1, N):
            flag &= ((dist[i][u] + cost + dist[v][j]) != dist[i][j])
    ans += int(flag)
print(ans)

Submission status: Wrong Answer

Solution code:
# 最小全域木

import sys
readline = sys.stdin.readline

import networkx as nx

N,M = map(int,readline().split())
INF = 10 ** 9
G = nx.Graph()
for i in range(M):
  a,b,c = map(int,readline().split())
  G.add_edge(a-1,b-1,weight = c)
  
T = nx.minimum_spanning_tree(G)
print(M - len(T.edges()))

Submission status: Wrong Answer

Solution code:
# 最小全域木

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
INF = 10 ** 9
G = [[] for i in range(N)]
for i in range(M):
  a,b,c = map(int,readline().split())
  G[a-1].append([b-1,c])
  G[b-1].append([a-1,c])
  
# Gの適当な頂点から始めて、
# ・最もコストの小さい辺に進む　（heapq）
# ・閉路を作らない(一度行った場所に行かない)
# で進んだ数が辺の数　これを全部の辺の数から引く

import heapq
q = []
for e in G[0]:
  # 辺のコスト、行先
  q.append([e[1],e[0]])

visited = [False for i in range(N)]
visited[0] = True

heapq.heapify(q)
edge = 0
while q:
  c,v = heapq.heappop(q)
  if visited[v]:
    continue
  edge += 1
  visited[v] = True
  for e in G[v]:
    if visited[e[0]]: # 既に行った場所には行かない
      continue
    heapq.heappush(q,[e[1],e[0]])
  
print(M - edge)

Submission status: Wrong Answer

Solution code:
# ワーシャルフロイドする際に、デフォルト値が入っている（INFではなく）のに、
# 更新された箇所に印をつけていく
# 最後に印を数える

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
INF = 10 ** 9
G = [[INF] * N for i in range(N)]
for i in range(M):
  a,b,c = map(int,readline().split())
  G[a-1][b-1] = c
  G[b-1][a-1] = c

ans = [[False] * N for i in range(N)]
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]:
        if G[i][j] != INF:
          ans[i][j] = True
        G[i][j] = G[i][k] + G[k][j]
  
p = 0
for i in range(len(ans)):
  for j in range(len(ans[i])):
    if ans[i][j]:
      p += 1
      
print(p // 2)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, m = map(int, readline().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]
abc = [list(map(int, readline().split())) for _ in range(m)]
for a, b, c in abc:
    graph[a][b] = c
    graph[b][a] = c
cost = floyd_warshall(csr_matrix(graph))
cnt = 0
for s in range(1, n + 1):
    for a, b, c in abc:
        if s == a or s == b:
            continue
        if cost[s][a] + c != cost[s][b] and cost[s][b] + c != cost[s][a]:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    root = [[] for _ in range(N)]
    for i in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c,i))
        root[b-1].append((a-1,c,i))

    rest = [1] * M
    q = []
    heapify(q)

    for i in range(N):
        node = [INF] * N
        heappush(q,(0,i,-1))
        while q:
            v,d,m = heappop(q)
            if node[v] < d: continue
            if m >= 0: rest[m] = 0
            for u,c,n in root[v]:
                if d + c < node[u]:
                    node[u] = d + c
                    heappush(q,(u,d+c,n))
    print(sum(rest))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]

ABC.sort(key=lambda x:x[2])
INF = 1 << 28
ds = [[INF] * N for _ in range(N)]
for i in range(N):
    ds[i][i] = 0

cnt = 0
for abc in ABC:
    a, b, c = abc
    a -= 1
    b -= 1

    update = False
    for i in range(N):
        for j in range(N):
            if ds[i][j] > ds[i][a] + c + ds[b][j]:
                ds[i][j] = ds[j][i] = ds[i][a] + c + ds[b][j]
                update = True

    if not update:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]

ABC.sort(key=lambda x:x[2])
INF = 1 << 28
ds = [[INF] * N for _ in range(N)]
for i in range(N):
    ds[i][i] = 0

cnt = 0
for abc in ABC:
    a, b, c = abc
    a -= 1
    b -= 1
    if ds[a][b] <= c:
        cnt += 1
        continue

    ds[a][b] = ds[b][a] = c

    for i in range(N):
        for j in range(N):
            if ds[i][j] > ds[i][a] + ds[a][b] + ds[b][j]:
                ds[i][j] = ds[j][i] = ds[i][a] + ds[a][b] + ds[b][j]

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]

ABC.sort(key=lambda x:x[2])
INF = 1 << 28
ds = [[INF] * N for _ in range(N)]
for i in range(N):
    ds[i][i] = 0

cnt = 0
for abc in ABC:
    a, b, c = abc
    a -= 1
    b -= 1
    if ds[a][b] <= c:
        cnt += 1
        continue

    ds[a][b] = ds[b][a] = c

    noupdate = True
    for i in range(N):
        if ds[a][b] > ds[a][i] + ds[i][b]:
            ds[a][b] = ds[b][a] = ds[a][i] + ds[i][b]
            noupdate = False

    if not noupdate:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import heapq
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    dp = [[float("inf")] * N for _ in range(N)]
    edges = set()
    for i in range(N):
        dp[i][i] = 0

    for _ in range(M):
        a, b, c, = map(int, input().split())
        a -= 1
        b -= 1
        dp[a][b] = c
        dp[b][a] = c
        if a > b:
            a, b = b, a
        edges.add((a, b))

    # ワーシャルフロイド
    # 経路復元のための配列
    # iからjへの最短経路における，jの一つ前の点
    prev = [[None] * N for _ in range(N)]
    for k in range(N):
        for i in range(N):
            for j in range(N):
                tmp = dp[i][k] + dp[k][j]
                if tmp < dp[i][j]:
                    dp[i][j] = tmp
                    prev[i][j] = k

    for i in range(N):
        for j in range(N):
            k = prev[i][j]
            if k is None:
                continue

            a = k
            b = j
            if a > b:
                a, b = b, a
            if (a, b) in edges:
                edges.remove((a, b))

    print(len(edges))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

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

a = [0]*M
b = [0]*M
c = [0]*M

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

d = [[float("inf")]*N for i in range(N)]

for i in range(M):
    d[a[i]][b[i]] = c[i]
    d[b[i]][a[i]] = c[i]
    
for i in range(N):
    d[i][i] = 0

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

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

Submission status: Wrong Answer

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

a = [0]*M
b = [0]*M
c = [0]*M

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

d = [[float("inf")]*N for i in range(N)]

for i in range(M):
    d[a[i]][b[i]] = c[i]
    d[b[i]][a[i]] = c[i]
    
for i in range(N):
    d[i][i] = 0

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

count = 0
for i in range(M):
    if d[a[i]][b[i]] != c[i]:
        count += 1
print(count)