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:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

# --- ワーシャルフロイド
def warshall_floyd(dp):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j])
    return dp

n, m = map(int, input().split())
d = [[float("inf")]*n for i in range(n)]

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

warshall_floyd(d)

used = [0]*m

for i, (a,b,c) in enumerate(abc):
    a,b = a-1,b-1
    for j in range(n):
        if  d[j][a] + c == d[j][b]:
            used[i]=1
            break

print(m-sum(used))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

# --- ワーシャルフロイト
def warshall_floyd(dp):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j])
    return dp

n, m = map(int, input().split())
d = [[float("inf")]*n for i in range(n)]

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

warshall_floyd(d)

used = [0]*m

for i, (a,b,c) in enumerate(abc):
    a,b = a-1,b-1
    for j in range(n):
        if  d[j][a] + d[a][b] == d[j][b]:
            used[i]=1
            break
        if  d[j][b] + d[b][a] == d[j][a]:
            used[i]=1
            break

print(m-sum(used))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]
tmp = []

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

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

ans = 0
for a, b, c in tmp:
    if c > graph[a][b]:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import *
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for i,(a,b,c) in enumerate(ABC):
    data[a].append([b,c,i])
    data[b].append([a,c,i])


mlst=set()

for sp in range(1,N+1):
    visited={sp}
    dic={}
    stack=[]
    for p,c,i in data[sp]:
        if not c in dic:
            dic[c]=[[p,i]]
            stack.append(c)
        else:
            dic[c].append([p,i])
            stack.append(c)
    stack.sort()
    while stack:
        m=heappop(stack)
        a,i=dic[m].pop()
        if a in visited:
            continue
        visited.add(a)
        mlst.add(i)
        for p,c,i in data[a]:
            if not p in visited:
                C=m+c
                heappush(stack,C)
                if C in dic:
                    dic[C].append([p,i])
                else:
                    dic[C]=[[p,i]]
print(M-len(mlst))

Submission status: Wrong Answer

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import *
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for i,(a,b,c) in enumerate(ABC):
    data[a].append([b,c,i])
    data[b].append([a,c,i])


mlst=set()

for sp in range(1,N+1):
    visited={sp}
    dic={}
    stack=[]
    for p,c,i in data[sp]:
        if not c in dic:
            dic[c]=[[p,i]]
            stack.append(c)
        else:
            dic[c].append([p,i])
            stack.append(c)
    heapify(stack)
    while stack:
        m=heappop(stack)
        a,i=dic[m].pop()
        if a in visited:
            continue
        visited.add(a)
        mlst.add(i)
        for p,c,i in data[a]:
            if not p in visited:
                C=m+c
                heappush(stack,C)
                if C in dic:
                    dic[C].append([p,i])
                else:
                    dic[C]=[[p,i]]
print(M-len(mlst))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
INF=10**18
edge=[[INF]*n for i in range(n)]
s=[]
for i in range(m):
  u,v,c=map(int,input().split())
  edge[u-1][v-1]=edge[v-1][u-1]=c
  s.append((u-1,v-1,c))
for i in range(n):
  for j in range(n):
    for k in range(n):
      edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
cnt=0
for i,j,cost in s:
  if edge[i][j]==cost:
    cnt+=1
print(m-cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
INF=10**18
edge=[[INF]*n for i in range(n)]
s=[]
for i in range(m):
  u,v,c=map(int,input().split())
  edge[u-1][v-1]=edge[v-1][u-1]=c
  s.append((u-1,v-1,c))
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i==j or j==k or k==i:
        continue
      edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
cnt=0
for i,j,cost in s:
  if edge[i][j]==cost:
    cnt+=1
print(m-cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
INF=10**18
edge=[[INF]*n for i in range(n)]
s=set()
for i in range(m):
  u,v,c=map(int,input().split())
  edge[u-1][v-1]=edge[v-1][u-1]=c
  s.add((u-1,v-1,c))
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i==j or j==k or k==i:
        continue
      edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
cnt=0
for i,j,cost in s:
  if edge[i][j]==cost:
    cnt+=1
print(m-cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
INF=10**9
edge=[[INF]*n for i in range(n)]
s=set()
for i in range(m):
  u,v,c=map(int,input().split())
  edge[u-1][v-1]=edge[v-1][u-1]=c
  s.add((u-1,v-1,c))
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i==j or j==k or k==i:
        continue
      edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
cnt=0
for i,j,cost in s:
  if edge[i][j]==cost:
    cnt+=1
print(m-cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
INF=10**9
edge=[[INF]*n for i in range(n)]
s=set()
for i in range(m):
  u,v,c=map(int,input().split())
  edge[u-1][v-1]=edge[v-1][u-1]=c
  s.add((u-1,v-1))
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i==j or j==k or k==i:
        continue
      edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
cnt=0
for t in range(n):
  for i,j in s:
    if edge[t][i]+edge[i][j]==edge[t][j]:
      cnt+=1
    break
print(cnt)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
n,m = map(int, input().split())
l = []
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort(key=lambda x:x[2])
uf=UnionFind(n)
ans=0
for edge in l:
    if uf.same(edge[0]-1,edge[1]-1):
        ans+=1
    else:
        uf.union(edge[0]-1,edge[1]-1)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
l = []
for i in range(m):
    l.append(list(map(int,input().split())))

wf=[[10**10 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c = l[i]
    wf[a-1][b-1] = c
    wf[b-1][a-1] = c
for i in range(n):
    wf[i][i]=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            wf[i][j] = min(wf[i][j],wf[i][k]+wf[k][j])

ans=0
for no_l in range(m):
    wf_t=[[10**10 for i in range(n)] for j in range(n)]

    for i in range(m):
        if i==no_l:
            continue
        a,b,c = l[i]
        wf_t[a-1][b-1] = c
        wf_t[b-1][a-1] = c
    for i in range(n):
        wf_t[i][i]=0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf_t[i][j] = min(wf_t[i][j],wf_t[i][k]+wf_t[k][j])
    ok=True
    for i in range(n):
        for j in range(n):
            if wf_t[i][j] != wf[i][j]:
                ok=False
    if ok:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist): #キューから値が無くなるまで
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)

if __name__ == "__main__":
    n,e = map(int,readline().split()) #n:頂点数　e:辺の数
    g = [[] for i in range(n+1)] #g[i]:点iに隣接している点のリスト
    for i in range(e):
        x,y,w = map(int,readline().split())
        x,y = x,y
        g[x].append([w,y])
        g[y].append([w,x])
    
    ans = 0

    for i in range(n):
        plane = dijkstra_heap(i,g)
        for j in range(len(g[i])):
            res = g[i].pop(j)
            if plane == dijkstra_heap(i,g):
                ans += 1
            g[i].insert(j,res)
    
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_2
# CreatedDate:  2020-02-21 20:39:32 +0900
# LastModified: 2020-02-21 23:32:20 +0900
#


import heapq
def initial_signal(i,adj,N):
    d = [float("inf") for _ in range(N)]
    d[i] = 0
    Q = [(0,i)]
    return d,Q

def relax(n_cost, u, v, adj,d,Q):
    if d[v] > d[u]+n_cost:
        d[v]=d[u]+n_cost
        heapq.heappush(Q,(d[v],v))



def dijkstra(i,adj,N):
    d,Q = initial_signal(i,adj,N)
    while Q:
        cost, u = heapq.heappop(Q)
        for n_cost, v in adj[u]:
            relax(n_cost, u, v, adj, d, Q)
        
    return d



def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = map(int, input().split())
        adj[a-1].append((c,b-1))
        adj[b-1].append((c,a-1))
    shortest = []
    for i in range(N):
        shortest.append(dijkstra(i,adj,N))
    ans = 0
    for i in range(N):
        for cost, j in adj[i]:
            if cost>shortest[i][j]:
                ans+=1
    print(shortest)
    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import os
import sys
import numpy as np
import heapq
#import pandas as pd
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c

def initial_signal(i,matrix):
    d = [float("inf")]*(matrix.shape[0])
    d[i] = 0
    Q = []
    heapq.heappush(Q,(0,i))
    return d,Q

def relax(matrix,u,v,d,Q):
    if d[v] > d[u]+matrix[u][v]:
        d[v] = d[u]+matrix[u][v]
        heapq.heappush(Q, (d[v],v))


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    while Q:
        cost,u = heapq.heappop(Q)
        if d[u]<cost:
            continue
        for v in range(matrix.shape[0]):
            if matrix[u][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        short = dijkstra(i,matrix)
        shortest.append(short)
    ans=0
    for i in range(N):
        for j in range(N):
            if matrix[i][j]!=0 and matrix[i][j]>shortest[i][j]:
                ans+=1
    print(shortest)
    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import os
import sys
import numpy as np
import heapq
#import pandas as pd
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c

def initial_signal(i,matrix):
    d = [9000]*(matrix.shape[0])
    d[i] = 0
    Q = []
    heapq.heappush(Q,(0,i))
    return d,Q

def relax(matrix,u,v,d,Q):
    if d[v] > d[u]+matrix[u][v]:
        d[v] = d[u]+matrix[u][v]
        heapq.heappush(Q, (d[v],v))


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    while Q:
        cost,u = heapq.heappop(Q)
        if d[u]<cost:
            continue
        for v in range(matrix.shape[0]):
            if matrix[u][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        short = dijkstra(i,matrix)
        shortest.append(short)
    ans=0
    for i in range(N):
        for j in range(N):
            if matrix[i][j]!=0 and matrix[i][j]>shortest[i][j]:
                ans+=1
    print(shortest)
    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import os
import sys
import numpy as np
import heapq
#import pandas as pd
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c

def initial_signal(i,matrix):
    d = [2000]*(matrix.shape[0])
    d[i] = 0
    Q = []
    heapq.heappush(Q,(0,i))
    return d,Q

def relax(matrix,u,v,d,Q):
    if d[v] > d[u]+matrix[u][v]:
        d[v] = d[u]+matrix[u][v]
        heapq.heappush(Q, (d[v],v))


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    while Q:
        cost,u = heapq.heappop(Q)
        if d[u]<cost:
            continue
        for v in range(matrix.shape[0]):
            if matrix[u][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        short = dijkstra(i,matrix)
        shortest.append(short)
    ans=0
    for i in range(N):
        for j in range(N):
            if matrix[i][j]!=0 and matrix[i][j]>shortest[i][j]:
                ans+=1
    print(shortest)
    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import os
import sys
import numpy as np
import heapq
#import pandas as pd
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c

def initial_signal(i,matrix):
    d = [100]*(matrix.shape[0])
    d[i] = 0
    Q = []
    heapq.heappush(Q,(0,i))
    return d,Q

def relax(matrix,u,v,d,Q):
    if d[v] > d[u]+matrix[u][v]:
        d[v] = d[u]+matrix[u][v]
        heapq.heappush(Q, (d[v],v))


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    while Q:
        cost,u = heapq.heappop(Q)
        if d[u]<cost:
            continue
        for v in range(matrix.shape[0]):
            if matrix[u][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        short = dijkstra(i,matrix)
        shortest.append(short)
    ans=0
    for i in range(N):
        for j in range(N):
            if matrix[i][j]!=0 and matrix[i][j]>shortest[i][j]:
                ans+=1

    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import os
import sys
import numpy as np
import heapq
#import pandas as pd
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c
def initial_signal(i,matrix):
    d = [100]*(matrix.shape[0])
    d[i] = 0
    Q = []
    heapq.heappush(Q,(0,i))
    return d,Q

def relax(matrix,u,v,d,Q):
    if d[v] > d[u]+matrix[u][v]:
        d[v] = d[u]+matrix[u][v]
        heapq.heappush(Q, (d[v],v))


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    while Q:
        cost,u = heapq.heappop(Q)
        if d[u]<cost:
            continue
        for v in range(matrix.shape[0]):
            if matrix[u][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        short = dijkstra(i,matrix)
        shortest.append(short)
    ans=0
    for i in range(N):
        for j in range(N):
            cost = matrix[i][j]
            if cost>shortest[i][j]:
                ans+=1

    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import os
import sys
import numpy as np
import heapq
#import pandas as pd
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c
def initial_signal(i,matrix):
    d = [100]*(matrix.shape[0])
    d[i] = 0
    Q = []
    heapq.heappush(Q,(0,i))
    return d,Q

def relax(matrix,u,v,d,Q):
    if d[v] > d[u]+matrix[u][v]:
        d[v] = d[u]+matrix[u][v]
        heapq.heappush(Q, (d[v],v))


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    while Q:
        cost,u = heapq.heappop(Q)
        for v in range(matrix.shape[0]):
            if matrix[u][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        short = dijkstra(i,matrix)
        shortest.append(short)
    ans=0
    for i in range(N):
        for j in range(N):
            cost = matrix[i][j]
            if cost>shortest[i][j]:
                ans+=1

    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import os
import sys
import numpy as np
#import pandas as pd
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c
def initial_signal(i,matrix):
    d = [100]*(matrix.shape[0])
    d[i] = 0
    Q = []
    for j in range(matrix.shape[0]):
        Q.append([j,100])
    Q[i][1]=0
    Q.sort()
    return d,Q

def relax(matrix,u,v,d,Q):
    if d[v] > d[u[0]]+matrix[u[0]][v]:
        d[v] = d[u[0]]+matrix[u[0]][v]
        for i,tmp in enumerate(Q):
            if Q[i][0]==v:
                Q[i][1] = d[u[0]]+matrix[u[0]][v]


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    S = []
    while Q:
        Q.sort(key=lambda x: x[1])
        u = Q.pop(0)
        S.append(u)
        for v in range(matrix.shape[0]):
            if matrix[u[0]][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        short = dijkstra(i,matrix)
        shortest.append(short)
    ans=0
    for i in range(N):
        for j in range(N):
            cost = matrix[i][j]
            if cost>shortest[i][j]:
                ans+=1

    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

N,M = map(int,input().split())
l = [[float('inf') for _ in range(N)] for _ in range(N)]
X = [list(map(int,input().split())) for _ in range(M)]
for i in range(M):
  l[X[i][0]-1][X[i][1]-1] = X[i][2]
  l[X[i][1]-1][X[i][0]-1] = X[i][2]
for i in range(N):
  l[i][i] = 0
d = deepcopy(l)
for i in range(N):
  for j in range(i):
    m = min(a+b for a,b in zip(d[i], d[j]))
    d[i][j] = m
    d[j][i] = m

count = 0
for i in range(N):
  for j in range(i):
    if l[i][j] != d[i][j] and l[i][j]!=float('inf'):
      count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
dist = [[float('inf')]*N for i in range(N)]
used = defaultdict(int)
log = defaultdict(int)
prev = [[-1]*N for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  log[(min(a-1,b-1),max(a-1,b-1))] = 1
  dist[a-1][b-1] = c
  dist[b-1][a-1] = c
  prev[a-1][b-1] = a-1
  prev[b-1][a-1] = b-1
for i in range(N):
  dist[i][i] = 0
  prev[i][i] = i
for k in range(N):
  for i in range(N):
    for j in range(N):
      if dist[i][j]>dist[i][k]+dist[k][j]:
        prev[i][j] = k
        dist[i][j] = dist[i][k]+dist[k][j]
for i in range(N):
  for j in range(i+1,N):
    p = prev[i][j]
    used[(min(p,j), max(p,j))] = 1
    while p!=i:
      np = prev[i][p]
      used[(min(np,p),max(np,p))] = 1
      p = np
ans = 0
for i in range(N):
  for j in range(i+1,N):
    if used[(i,j)]==0 and log[(i,j)]==1:
      ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#made in 2019/7/1
#modified in 2020/2/14
class Node:
    def __init__(self):
        self.next={}
    def get_data(self,new_next,weight=1):
        self.next[new_next]=weight



def dijkstra():
    total=0
    node_cost=[float("inf") for i in range(0,N)]
    now=[E-1]
    node_cost[now[0]]=0
    check=[i for i in range(0,N)]
    check.remove(E-1)
    next_node=node[now[0]].next.keys()
    while len(check):
        total+=1
        tmp=[]
        #print("now", now)
        for each in now:
            next_node=node[each].next.keys()
            for i in next_node:
                val=node[each].next[i]+node_cost[each]
                if node_cost[i]>val:
                    node_cost[i]=val
                    if i in check:
                        #check.remove(i)
                        #tmp.extend(node[i].next.keys())
                        tmp.append(i)
        now=tmp
        #print("next... ",tmp)
        #print("now...",node_cost)
        if len(now)==0:
            break
        
    print(node_cost)
    print("min_cost:",node_cost[S-1])
    



def BFS():
    total=0
    #print("start bfs")
    check_node=[i for i in range(0,N)]
    now=S-1
    tmp=[now]
    check_node.remove(now)
    new_tmp=[]
    while len(check_node)>0:
        #print("tmp:{}".format(tmp))
        total+=1
        for each in tmp:
            #print("each:{}".format(each))
            for i in node[each].next.keys():
                k=i
                #print(k)
                if k in check_node:
                    #print("append :{}".format(k))
                    new_tmp.append(k)
                    check_node.remove(k)
        #print("new_tmp:{}".format(new_tmp))
        #print("check_node:{}".format(check_node))
        tmp=new_tmp
        new_tmp=[]
    print("end")
    print("loop time:{}".format(total))
    







        
        


#??
N,M=list(map(int,input().split()))
#S,E=list(map(int,input().split()))
node=[Node() for _ in range(N)]
ans=[[100 for _ in range(N)]for _ in range(N)]
for i in range(M):
    tmp_p,tmp_n,tmp_w=list(map(int,input().split()))
    node[tmp_p-1].get_data(tmp_n-1,tmp_w)
    node[tmp_n-1].get_data(tmp_p-1,tmp_w)
#BFS()
a_num=ord("a")
for i in range(N):
    #print(chr(a_num+i),"→",chr(a_num+j))
    S=i+1
    E=i+1
    dijkstra()
    print()

Submission status: Wrong Answer

Solution code:
#無向グラフ
class Graph():
    #初期変数は頂点数、辺数、標準入力から受け取った配列形式の入力
    def __init__(self,vertex_num,node_num,naive_input):
        self.vertex_num=vertex_num
        self.node_num=node_num
        #nodeには入力時のインデックスも含む
        #[接続ノード , インッデクス]のarray
        node=[[] for _ in range(vertex_num)]
        for i in range(node_num):
            u,v=naive_input[i][:2]
            w=naive_input[i][2]
            node[u].append([v,i,w])
            node[v].append([u,i,w])
        self.node=node
        #それぞれの頂点の辺の数
        self.node_num_arr=list(map(lambda x:len(x),node))
    #頂点nowから順にbfs
    def bfs(self,s=0):
        #最短経路＋αで問題を解くと思うのでcal_distance内で問題を解くための関数を実行する形の方が自然？
        def cal_distance(now_edge,next_edge_info,distance_arr,before_vertex_arr,queue,l_ind,ind_arr):
            next_edge=next_edge_info[0]
            ind=next_edge_info[1]
            weight=next_edge_info[2]
            cal_distance_val=distance_arr[now_edge]+weight
            if before_vertex_arr[next_edge]==-1:
                    queue[l_ind]=next_edge
                    #print("queue is updated")
                    l_ind+=1
            if cal_distance_val<distance_arr[next_edge]:
                #配列渡しなのでこのあたりは返り値に持たせる必要無し
                distance_arr[next_edge]=cal_distance_val
                before_vertex_arr[next_edge]=now_edge
                ind_arr[next_edge]=ind
                #for debug
                """
                print(now_edge,"→",next_edge,":",cal_distance_val)
                print(distance_arr)
                print(before_vertex)
                """
            return l_ind

        #bfs用のキュー
        q=[-1 for _ in range(self.vertex_num)]
        #pypyを使うときは要変更
        #ダイクストラ使用に伴って削除
        #訪問済み頂点は距離から導出
        #cal_node_num_arr=self.node_num_arr.copy()
        now_ind=0
        q[now_ind]=s
        last_ind=1


        distance=[float("inf") for _ in range(self.vertex_num)]
        distance[s]=0
        before_vertex=[-1 for _ in range(self.vertex_num)]
        before_vertex[s]=s
        index_arr=[float("inf") for _ in range(self.vertex_num)]
        #index_arr[s]=s

        while now_ind<self.vertex_num:
            now_edge=q[now_ind]
            """
            print()
            print()
            print("now_node:",now_edge)
            print("now_ind:",now_ind,"last_ind",last_ind)
            print(q)
            print(before_vertex)
            """
            for next_edge_info in self.node[now_edge]:
                #インデックスを利用したいときは要修正
                #cal_node_num_arr[now_edge]-=1
                #cal_node_num_arr[next_edge]-=1
                #q[last_ind]=next_edge
                ##ここにやりたい処理をぶち込む！！
                #######cal_hogehoge()

                #頂点sから各頂点までの距離を計算する

                last_ind=cal_distance(now_edge,next_edge_info,distance,before_vertex,q,last_ind,index_arr)
                
            now_ind+=1
        
        return distance,index_arr

n,m=list(map(int,input().split()))
"""
maze=[[i for i in input()] for _ in range(n)]
graph=[[] for _ in range(n*m)]
q_num=0
for i in range(n):
    for j in range(m):
        if maze[i][j]=="#":
            continue
        ind=i*m+j
        q_num+=1
        #move[i][j]=ind
        if i!=0:
            if maze[i-1][j]!="#":
                graph[ind].append((i-1)*m+j)
        if i!=n-1:
            if maze[i+1][j]!="#":
                graph[ind].append((i+1)*m+j)
        if j!=0:
            if maze[i][j-1]!="#":
                graph[ind].append(i*m+j-1)
 
        if j!=m-1:
            if maze[i][j+1]!="#":
                graph[ind].append(i*m+j+1)

a=[]
for num,i in enumerate(graph):
    for j in i:
        a.append([num,j,1])
#print(a)
tmp=0
for i in maze:
    for j in i:
        if j==".":
            tmp+=1
n=tmp
m=len(a)
"""
a=[list(map(int,input().split())) for _ in range(m)]
a=list(map(lambda x:[x[0]-1,x[1]-1,x[2]],a))
G=Graph(n,m,a)
ans=[True for _ in range(m)]

for i in range(n):
    #print(i,":time")
    cal,ind=G.bfs(i)
    for j in ind:
        if j==float("inf"):
            continue
        ans[j]=False
    #print("\n\n\n\n\n")

print(sum(ans))