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=map(int,input().split())
Islands=[[] for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1].append([b-1,c])
  Islands[b-1].append([a-1,c])
  Edge.append([a-1,b-1,c])
for m in range(M):
  a=Edge[m][0]
  b=Edge[m][1]
  c_m=Edge[m][2]
  List=[[a,0]]
  for l in List:
    c_base=l[-1]
    c=c_base
    if l[-2]==b:
      if c_m>c:
        S+=1
        break
    else:        
      for n in Islands[l[-2]]:
        if n[0] in l[0:-1]:
          pass
        else:
          c+=n[1]
          List.append(l[0:-1]+[n[0],c])  
          c=c_base
print(S-1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
Islands=[[] for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1].append([b-1,c])
  Islands[b-1].append([a-1,c])
  Edge.append([a-1,b-1])
for m in range(M):
  a=Edge[m][0]
  b=Edge[m][1]
  for i in Islands[a]:
    if i[0]==b:
      c_m=i[1]
  List=[[a,0]]
  for l in List:
    print(m,List)
    c_base=l[-1]
    c=c_base
    if l[-2]==b:
      if c_m>c:
        S+=1
        break
    else:        
      for n in Islands[l[-2]]:
        if n[0] in l[0:-1]:
          pass
        else:
          c+=n[1]
          List.append(l[0:-1]+[n[0],c])  
          c=c_base
print(S-1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
Islands=[[] for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1].append([b-1,c])
  Islands[b-1].append([a-1,c])
  Edge.append([a-1,b-1])
for m in range(M):
  a=Edge[m][0]
  b=Edge[m][1]
  for i in Islands[a]:
    if i[0]==b:
      c_m=i[1]
  List=[[a,-1]]
  for l in List:
    c=(-1)*(l[-1]+1)
    if l[-2]==b:
      if c_m>c:
        S+=1
        break
    else:        
      for n in Islands[l[-2]]:
        if n[0] in l:
          pass
        else:
          c+=n[1]
          List.append(l[0:-1]+[n[0],(-1)*(c+1)])
          
print(S)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
Islands=[[] for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1].append([b-1,c])
  Islands[b-1].append([a-1,c])
  Edge.append([a-1,b-1])
for m in range(M):
  a=Edge[m][0]
  b=Edge[m][1]
  for i in Islands[a]:
    if i[0]==b:
      c_m=i[1]
  List=[[a,-1]]
  for l in List:
    print(List)
    c=(-1)*(l[-1]+1)
    if l[-2]==b:
      if c_m>c:
        S+=1
        break
    else:        
      for n in Islands[l[-2]]:
        if n[0] in l:
          pass
        else:
          c+=n[1]
          List.append(l[0:-1]+[n[0],(-1)*(c+1)])
          
print(S)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
Islands=[[] for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1].append([b-1,c])
  Islands[b-1].append([a-1,c])
  Edge.append([a-1,b-1])
for m in range(M):
  a=Edge[m][0]
  b=Edge[m][1]
  for i in Islands[a]:
    if i[0]==b:
      c_m=i[1]
  List=[[a,-1]]
  for l in List:
    c=(-1)*(l[-1]+1)
    if l[-2]==b:
      if c_m>c:
        S+=1
        break
    else:        
      for n in Islands[l[-2]]:
        if n[0] in l:
          pass
        else:
          l_copy=list(l)
          c+=n[1]
          del l_copy[-1]
          List.append(l_copy+[n[0],(-1)*(c+1)])
          
print(S)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall as ws
import numpy as np

N,M=list(map(int,input().split()))
dist=np.array([[10*9 for _ in range(N)] for _ in range(N)])
for i in range(N):
    dist[i,i]=0

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

wsdist=np.array(ws(dist),dtype='int')
ans=-N
for i in range(N):
    for j in range(N):
        if wsdist[i][j]==dist[i][j]:
            ans+=1
print(M-ans//2)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall as ws
import numpy as np

N,M=list(map(int,input().split()))
dist=np.array([[1001000 for _ in range(N)] for _ in range(N)])
for i in range(N):
    dist[i,i]=0

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

wsdist=np.array(ws(dist),dtype='int')
ans=-N
for i in range(N):
    for j in range(N):
        if wsdist[i][j]==dist[i][j]:
            ans+=1
print(M-ans//2)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall as ws
import numpy as np

N,M=list(map(int,input().split()))
dist=np.array([[1001 for _ in range(N)] for _ in range(N)])
for i in range(N):
    dist[i,i]=0

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

wsdist=np.array(ws(dist))
ans=-N
for i in range(N):
    for j in range(N):
        if wsdist[i][j]==dist[i][j]:
            ans+=1
print(M-ans//2)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall as ws
import numpy as np

N,M=list(map(int,input().split()))
dist=np.array([[1001 for _ in range(N)] for _ in range(N)])
for i in range(N):
    dist[i,i]=0

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

wsdist=np.array(ws(dist),dtype='int')
ans=-N
for i in range(N):
    for j in range(N):
        if wsdist[i][j]==dist[i][j]:
            ans+=1
print(M-ans//2)

Submission status: Wrong Answer

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

d = [[0]*n for i in range(n)]
e = [[0]*n for i in range(n)]

for i in range(n):
    for j in range(n):
        if i!=j:
            d[i][j]=float('inf')
            e[i][j]=float('inf')

for i in range(m):
    d[abc[i][0]-1][abc[i][1]-1]=abc[i][2]
    d[abc[i][1]-1][abc[i][0]-1]=abc[i][2]
    e[abc[i][0]-1][abc[i][1]-1]=abc[i][2]
    e[abc[i][1]-1][abc[i][0]-1]=abc[i][2]

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

f = 0

for i in range(n):
    for j in range(n):
        if d[i][j]!=e[i][j]:
            f+=1

print(f//2)

Submission status: Wrong Answer

Solution code:
import heapq

n, m = [int(i) for i in input().split()]
inf = 10**10
path = [[0] * n for _ in range(n)]
Q = [[inf] * n for _ in range(n)]
ans = 0
pathnum = []
ctr = 0

for i in range(m):
    a, b, c = map(lambda x: int(x)-1 ,input().split())    
    path[a][b] = path[b][a] = c+1
    pathnum.append((a,b))

for i in range(n):
    decided = [False for _ in range(n)]
    H = []
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    while ctr != n:
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                ctr += 1
                break
        for j in range(n):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

for i in pathnum:
    if Q[i[0]][i[1]] == inf:
        continue
    elif Q[i[0]][i[1]] != path[i[0]][i[1]]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in range(m)]
d=[[1<<32 for _ in range(n)] for _ in range(n)]
for a,b,c in abc:
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=0
for a,b,c in abc:
    j=True
    for s in range(n):
        if d[s][a-1]+c==d[s][b-1]:
            j=False
    if j: ans+=1
print(ans)

Submission status: Wrong Answer

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

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

count = 0
for i, j, val in edges:
    isIncluded = False
    for s in range(n):
        if s == i or s == j:
            continue

        if d[s][i] + val == d[s][j] or d[s][j] + val == d[s][i]:
            isIncluded = True
            break

    if not isIncluded:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 9
g = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    g[i][i] = 0
for a, b, c in edge:
    g[a][b] = c
    g[b][a] = c
for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

ans = 0
for a, b, c in edge:
    if g[a][b] != c:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
edge = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
INF = 10 ** 9
g = [[INF] * N for _ in range(N)]
for i in range(N):
    g[i][i] = 0
for a, b, c in edge:
    g[a][b] = c
    g[b][a] = c
for i in range(N):
    for j in range(N):
        for k in range(N):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

ans = 0
for a, b, c in edge:
    if g[a][b] != c:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import copy

def Dijk(s, t):
    Cost = [-1 for i in range(N)]
    Cost[s] = 0
    Q = copy.deepcopy(Edge[s])
    for node in Q:
        Cost[node[1]] = node[0]
    V = [False for i in range(N)]
    V[s] = True
    while V[t] == False:
        Next = heapq.heappop(Q)
        V[Next[1]] = True
        for node in Edge[Next[1]]:
            if V[node[1]] == False:
                if Cost[node[1]] == -1:
                    Cost[node[1]] = Next[0] + node[0]
                else:
                    Cost[node[1]] = min(Next[0] +node[0], Cost[node[1]])
                heapq.heappush(Q, [Cost[node[1]], node[1]])
    return Cost[t]


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

Ans = 0
for s in Search:
    for i in range(N):
        if Dijk(i, s[0]) + s[2] == Dijk(i, s[1]):
            break
    else:
        Ans += 1

print(Ans)

Submission status: Wrong Answer

Solution code:
INF = 10**6 + 1

N,M = map(int,raw_input().split())

a_l=[]
b_l=[]
c_l=[]

for i in range(M):
    a,b,c=map(int,raw_input().split())
    a_l.append(a-1)
    b_l.append(b-1)
    c_l.append(c-1)
    

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

for i in range(N):
    d[i][i]=0

    

for i in range(M):
    d[a_l[i]][b_l[i]] = min(c_l[i],d[a_l[i]][b_l[i]])
    d[b_l[i]][a_l[i]] = min(c_l[i],d[b_l[i]][a_l[i]])


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

for i in range(M):
    flag=False
    for j in range(N):
        for k in range(N):
            if d[j][k]==d[j][a_l[i]]+d[b_l[i]][k]+c_l[i]:
                flag=True
    if flag:
        ans-=1
print ans

Submission status: Wrong Answer

Solution code:
import heapq

def dijkstra(adj, start, goal=None):
    n = len(adj)
    dist = [float("inf") for i in range(n)]
    prev = [float("inf") for i in range(n)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
        prov_cost, src = heapq.heappop(q)

        if dist[src] < prov_cost:
            continue

        for dest in range(n):
            cost = adj[src][dest]
            if cost != float("inf") and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost
                heapq.heappush(q, (dist[dest], dest))
                prev[dest] = src

    return dist

n, m = map(int, input().split())
adj = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
shortest = []
for i in range(n):
     shortest.append(dijkstra(adj, i))
ans = 0
for i in range(n):
    k = 0
    for j in adj[i]:
        if j > shortest[i][k]:
            ans += 1
        k += 1
print(ans // 2)

Submission status: Wrong Answer

Solution code:
import heapq

def dijkstra(adj, start, goal=None):
    n = len(adj)
    dist = [float("inf") for i in range(n)]
    prev = [float("inf") for i in range(n)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
        prov_cost, src = heapq.heappop(q)

        if dist[src] < prov_cost:
            continue

        for dest in range(n):
            cost = adj[src][dest]
            if cost != float("inf") and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost
                heapq.heappush(q, (dist[dest], dest))
                prev[dest] = src

    if goal is not None:
        return get_path(goal, prev)
    else:
        return dist

def get_path(goal, prev):
    path = [goal]
    dest = goal
    while prev[dest] != float("inf"):
        path.append(prev[dest])
        dest = prev[dest]
    return list(reversed(path))

n, m = map(int, input().split())
adj = [[float("inf") for i in range(n)] for i in range(n)]
path = []
for i in range(m):
    a, b, c = map(int, input().split())
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
    path.append(set([a - 1, b - 1]))
print(adj)
for i in range(n):
    for j in range(n):
        if i != j:
            saitan = dijkstra(adj, i, j)
            for k in range(len(saitan) - 1):
                ss = set(saitan[k:k + 2])
                if ss in path:
                    path.remove(ss)
print(len(path))

Submission status: Wrong Answer

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

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

dist = [[10000000 for i in range(n)] for k in range(n)]
for i in range(n):
    dist[i][i] = 0
    for k in graph[i]:
        dist[i][k[0]] = k[1]

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]:
                dist[i][j] = dist[i][k] + dist[k][j]


counter = 0
for i in range(m):
    check = False
    for start in range(n):
        for goal in range(start+1,n):
            if dist[start][branch[i][0]] + branch[i][2] + dist[branch[i][1]][goal] == dist[start][goal]:
                check = True
    if check:
        counter += 1

print(m-counter)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,M = inpl()
cost = [[INF for i in range(N)] for j in range(N)]

#0:辺がない -1:辺はあるけど使ってない 1:使ってる
ed = [[0]*N for i  in range(N)]

for _ in range(M):
    a,b,c = inpl()
    a,b = a-1,b-1
    cost[a][b] = c
    cost[b][a] = c
    ed[a][b] = -1
    ed[b][a] = -1

for k in range(N):
    for i in range(N):
        for j in range(N):
            moto = cost[i][j]
            new = cost[i][k]+cost[k][j]
            if moto > new:
                if ed[i][j] != 0:
                    ed[i][j] = -1
                ed[i][k] = 1
                ed[k][j] = 1
                cost[i][j] = new

ans = 0
for i in range(N):
    for j in range(N):
        if ed[i][j] == -1:
            ans += 1
print(ans//2)

Submission status: Wrong Answer

Solution code:
import heapq
INF = 10**7
N,M = map(int,input().split())
dist = [[INF for j in range(N)] for i in range(N)]
used = [[True for i in range(N)] for j in range(N)]
for i in range(M):
	a,b,c = map(int,input().split())
	a -= 1
	b -= 1
	dist[a][b] = c
	dist[b][a] = c
	used[a][b] = False
	used[b][a] = False

for i in range(N):
	hq = []
	heapq.heapify(hq)
	heapq.heappush(hq, (0, i, None))
	searched = [False for j in range(N)]
	while len(hq) > 0:
		cost, node, edge = heapq.heappop(hq)
		if searched[node]:
			continue
		
		searched[node] = True
		if edge != None:
			used[edge[0]][edge[1]] = True
			used[edge[1]][edge[0]] = True
		for j in range(N):
			if dist[node][j] == INF or searched[j]:
				continue
			heapq.heappush(hq, (cost + dist[node][j], j, (node,j)))

print(sum([sum([1 for j in range(N) if not used[i][j]]) for i in range(N)]) // 2)

Submission status: Wrong Answer

Solution code:
import heapq
INF = 10**7
N,M = map(int,input().split())
dist = [[INF for j in range(N)] for i in range(N)]
used = [[True for i in range(N)] for j in range(N)]
for i in range(M):
	a,b,c = map(int,input().split())
	a -= 1
	b -= 1
	dist[a][b] = c
	dist[b][a] = c
	used[a][b] = False
	used[b][a] = False

for i in range(N):
	hq = []
	heapq.heapify(hq)
	heapq.heappush(hq, (0, i, None))
	searched = [False for j in range(N)]
	while len(hq) > 0:
		cost, node, edge = heapq.heappop(hq)
		if searched[node]:
			continue
		
		searched[node] = True
		if edge != None:
			used[edge[0]][edge[1]] = True
			used[edge[1]][edge[0]] = True
		for j in range(N):
			if dist[j] == INF or searched[j]:
				continue
			heapq.heappush(hq, (cost + dist[node][j], j, (node,j)))

print(sum([sum([1 for j in range(N) if not used[i][j]]) for i in range(N)]) // 2)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
DP = [[10000 for i in range(N)] for j in range(N)]
check = [[1 for i in range(N)] for j in range(N)]
pointlist = []
for i in range(M):
    a, b, c = map(int, input().split())
    DP[a - 1][b - 1] = c
    DP[b - 1][a - 1] = c
    pointlist.append([a, b, c])

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

cnt = 0
for i in pointlist:
    if DP[i[0] - 1][i[1] - 1] != i[2]:
        cnt += 1
    

print(cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
DP = [[10000 for i in range(N)] for j in range(N)]
check = [[1 for i in range(N)] for j in range(N)]
pointlist = []
for i in range(M):
    a, b, c = map(int, input().split())
    DP[a - 1][b - 1] = c
    DP[b - 1][a - 1] = c
    pointlist.append([a, b, c])

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

cnt = 0
for i in pointlist:
    if DP[i[0] - 1][i[1] - 1] != i[2]:
        cnt += 1
    

print(cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
DP = [[10000 for i in range(N)] for j in range(N)]
check = [[1 for i in range(N)] for j in range(N)]
pointlist = []
for i in range(M):
    a, b, c = map(int, input().split())
    DP[a - 1][b - 1] = c
    DP[b - 1][a - 1] = c
    pointlist.append([a, b])

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

cnt = 0
for i in pointlist:
    if check[i[0] - 1][i[1] - 1] == 0:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall as fw
import sys
sdin = sys.stdin.readline


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

INF = float("inf")
adj_mat = INF * np.ones((n, n))


for _ in range(m):
    a,b,c = map(int, sdin().split())
    a -= 1
    b -= 1
    adj_mat[a,b] = c
    adj_mat[b,a] = c

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

    
shortest = fw(adj_mat)


ans = 0
for i in range(1,n):
    for j in range(i+1,n):
        if adj_mat[i][j] != INF and adj_mat[i][j] > shortest[i][j]:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict, deque
n, m = map(int, input().split())
G = defaultdict(list)
E = []
for i in range(m):
    a, b, c = map(int, input().split())
    G[a - 1].append((b - 1, c))
    G[b - 1].append((a - 1, c))
    E.append((a - 1, b - 1, c))

INF = float("inf")
d = [INF] * n
d[0] = 0
que = [(0, 0)]
while que:
    cost, v = heappop(que)
    if d[v] < cost:
        continue
    for w, c in G[v]:
        if cost + c < d[w]:
            d[w] = cost + c
            heappush(que, (cost + c, w))

num = m
for x, y, c in E:
    if d[x] +  c == d[y]:
        num -= 1

print(num)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, inputs,m, start):
        self.graph = defaultdict(list)
        for i in range(m):
            self.graph[inputs[i][0]].append((inputs[i][1], inputs[i][2]))
            self.graph[inputs[i][1]].append((inputs[i][0], inputs[i][2]))

        self.g = self.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

def main():
    n, m= map(int,input().split())

    inputs = [0]*m

    for i in range(m):
        lst = [int(i) for i in input().split()]
        inputs[i]=lst

    lst = [[0 for i in range(n+1)] for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i != j and lst[j][i] == 0:
                d = Dijkstra(inputs,m,i)
                lst[i][j] = d.shortest_distance(j)

   # print(lst)
    #print(inputs)

    ans = 0
    for i in range(1,m):
        if lst[min(inputs[i][0],inputs[i][1])][max(inputs[i][0],inputs[i][1])] < inputs[i][2]:
            ans+=1

    print(ans)

if __name__ == "__main__":
        main()

Submission status: Wrong Answer

Solution code:
from itertools import product

N, M = map(int, input().split())
abc = [[int(x) - 1 for x in input().split()] for _ in range(M)]

dist = [[float('inf') for _ in range(N)] for _ in range(N)]
for a, b, c in abc:
    dist[a][b] = c
    dist[b][a] = c

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

ans = 0
for a, b, c in abc:
    if dist[a][b] != c:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product


N, M = map(int, input().split())


class WarshallFloyd(object):
    def __init__(self, graph):
        n = len(graph)
        dist = graph
        for k, i, j in product(range(n), repeat=3):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        self.dist = dist

    def shortest_distance(self, start, goal):
        return self.dist[start][goal]


graph = [[0 for _ in range(N)] for _ in range(N)]
edge = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c
    edge[i] = (a - 1, b - 1, c)

wf = WarshallFloyd(graph)
ans = 0
for e in edge:
    if wf.shortest_distance(e[0], e[1]) != e[2]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
    ai, bi, ci = map(int, input().split())
    a.append(ai-1)
    b.append(bi-1)
    c.append(ci)

G = csr_matrix((c, (a, b)), shape=(N, N), dtype=int)
D, P = floyd_warshall(G, directed=False, return_predecessors=True)
edges = []
for i in range(N):
    for j in range(N):
        if P[i][j] < 0 or i == P[i][j]:
            continue
        edges.append((min(i, P[i][j]), max(i, P[i][j])))
edges = list(set(edges))
print(M - len(edges))

Submission status: Wrong Answer

Solution code:
from itertools import product


N, M = map(int, input().split())


class WarshallFloyd(object):
    def __init__(self, graph):
        n = len(graph)
        self.c = 0
        dist = graph
        for i, j, k in product(range(n), repeat=3):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                self.c += 1
        self.dist = dist

    def shortest_distance(self, start, goal):
        return self.dist[start][goal]


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

wf = WarshallFloyd(graph)
print(wf.c // 2)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


N, M = map(int, input().split())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(dict)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src][dst] = weight

    def get_nodes(self):
        return self.graph.keys()


class Prim(object):

    def __init__(self, graph, start=0):
        self.edge = []
        self.total = 0

        g = graph.graph
        n = len(graph)
        visited = [False] * n
        visited[start] = True

        Q = []
        for v, cost in g[start].items():
            heappush(Q, (cost, (start, v)))

        while Q:
            cost, edge = heappop(Q)

            if visited[edge[1]]:
                continue

            self.edge.append(edge)
            self.total += cost
            visited[edge[1]] = True

            for v, cost in g[edge[1]].items():
                heappush(Q, (cost, (edge[1], v)))



g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, c)
    g.add_edge(b - 1, a - 1, c)
print(M - len(Prim(g).edge))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
    ai, bi, ci = map(int, input().split())
    a.append(ai-1)
    b.append(bi-1)
    c.append(ci)

G = csr_matrix((c, (a, b)), shape=(N, N), dtype=int)
_, P = floyd_warshall(G, return_predecessors=True)
edges = np.unique(P)
count = 0
for i in range(M):
    if i not in edges:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Adj = [[10 ** 7 for j in range(N)] for i in range(N)]
for i in range(N):
  Adj[i][i] = 0
Edge = []
for m in range(M):
  a, b, c = map(int, input().split())
  Adj[a - 1][b - 1] = c
  Adj[b - 1][a - 1] = c
  Edge.append([a - 1, b - 1, c])
for i in range(N):
  for j in range(N):
    for k in range(N):
      Adj[i][j] = min(Adj[i][k] + Adj[k][j], Adj[i][j])
Used = [1 for m in range(M)]
for i, e in enumerate(Edge):
  for s in range(N):
    if Adj[s][e[0]] + e[2] == Adj[s][e[1]]:
      Used[i] = 0
print(sum(Used))