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:
#無向グラフ
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):
            next_edge=next_edge_info[0]
            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
                #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=[-1 for _ in range(self.node_num)]

        while last_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)
                
            now_ind+=1
        
        return distance

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=0
for i in range(n):
    cal=G.bfs(i)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np
N,M=map(int,input().split())
abc = [tuple(map(int,input().split())) for i in range(M)]
g = [[10**9]*N for i in range(N)]
for a,b,c in abc:
  a,b = a-1,b-1
  g[a][b]=c
  g[b][a]=c
g = np.array(g)
G,P=shortest_path(g,return_predecessors=True)
ans=set()
for i in range(N):
  for j in range(N):
    if P[i][j]==i:
      if (j,i) not in ans:
        ans.add((i,j))
    elif P[i][j]>0 and (P[i][j],i) not in ans:
      ans.add((i,P[i][j]))
print(M-len(ans))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np
N,M=map(int,input().split())
abc = [tuple(map(int,input().split())) for i in range(M)]
g = [[10**5]*N for i in range(N)]
for a,b,c in abc:
  a,b = a-1,b-1
  g[a][b]=c
  g[b][a]=c
g = np.array(g)
G,P=shortest_path(g,return_predecessors=True)
ans=set()
for i in range(N):
  for j in range(N):
    if P[i][j]==i:
      if (j,i) not in ans:
        ans.add((i,j))
    elif P[i][j]>0 and (P[i][j],i) not in ans:
      ans.add((i,P[i][j]))
print(M-len(ans))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall

INF = 10 ** 18
N, M = map(int, input().split())
d = [[INF for _ in range(N)] for _ in range(N)]
abc = []

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

dtra = floyd_warshall(d)
minlst = [INF] * N
for i in range(N):
    for j in range(N):
        if dtra[i][j] != 0:
            minlst[i] = min(minlst[i], dtra[i][j])

cnt = 0
for i in range(M):
    if int(minlst[abc[i][1]]) < abc[i][2]:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]

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

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

g = copy.deepcopy(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]])


# 経路復元
p = {}
for i in range(N):
    for j in range(N):
        c = i
        while c != j:
            for k in range(N):
                if k != c and (g[c][k]+dp[k][j]) == dp[c][j]:
                    p[(c, k) if c < k else (k, c)] = 1
                    c = k
                    break
print(max([0, M-len(p)]))

Submission status: Wrong Answer

Solution code:
import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]

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

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

g = copy.deepcopy(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]])


# 経路復元
p = {}
for i in range(N):
    for j in range(i+1, N):
        c = i
        while c != j:
            for k in range(N):
                if k != c and (g[c][k]+dp[k][j]) == dp[c][j]:
                    p[(c, k) if c < k else (k, c)] = 1
                    c = k
                    break
print(M-len(p))

Submission status: Wrong Answer

Solution code:
INF = 10**10
N,M=map(int,input().split())
e=[]
w=[[INF for j in range(N)]for i in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    w[a-1][b-1]=c
    w[b-1][a-1]=c
    e.append((a-1,b-1,c))

class lheapq():
#最小値を取り出す優先度付きキュー
    def __init__(self,p):
        self.l = []
        if p:
            for sp in p:
                self.heappush(sp)

    def heappush(self,a):
        n=len(self.l)
        self.l.append(a)
        t = n
        while t != 0:
            if self.l[t][1] < self.l[(t-1)//2][1]:
                self.l[t],self.l[(t-1)//2] = self.l[(t-1)//2],self.l[t]
                t = (t-1)//2
            else:break

    def heappop(self):
        n=len(self.l)
        if n == 0:
            return (-1,0)
        if n == 1:
            return self.l.pop()
        ret = self.l[0]
        self.l[0] = self.l.pop()
        n -= 1
        t = 0
        while t<n:
            child1 = t*2+1
            child2 = t*2+2
            if child1 >= n:
                break
            elif child2 >= n:
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t],self.l[child1] = self.l[child1],self.l[t]
                    t = child1
                else:break
            else:
                if self.l[child2][1] < self.l[child1][1]:
                    child1,child2 = child2,child1
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t],self.l[child1] = self.l[child1],self.l[t]
                    t = child1
                elif self.l[t][1] > self.l[child2][1]:
                    self.l[t],self.l[child2] = self.l[child2],self.l[t]
                    t = child2
                else:break
        return ret
    
    def isnotblank(self):
        if self.l:return True
        else:return False

def dijkstra(s,g,N,e):
    INF =10**10
    res = [INF for _ in range(N)]
    q=lheapq([(s,0)])
    while q.isnotblank():
        while q.isnotblank():
            des,dis = q.heappop()
            if res[des] == INF:
                res[des] = dis
                break
        for se in e[des]:
            if res[se[0]] == INF:
                q.heappush((se[0],se[1]+res[des]))
    return res[g]

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

res = 0
for i in range(M):
    g=[[] for _ in range(N)]
    for j in range(M):
        if j!=i:
            a,b,c = e[j][0],e[j][1],e[j][2]
            g[a].append((b,c))
            g[b].append((a,c))
    a,b,c = e[i][0],e[i][1],e[i][2]
    if dijkstra(a,b,N,g) == w[a][b]:
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
INF = 10**10
N,M=map(int,input().split())
e=[]
w=[[INF for j in range(N)]for i in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    w[a-1][b-1]=c
    w[b-1][a-1]=c
    e.append((a-1,b-1,c))

class lheapq():
#最小値を取り出す優先度付きキュー
    def __init__(self,p):
        self.l = []
        if p:
            for sp in p:
                self.heappush(sp)

    def heappush(self,a):
        n=len(self.l)
        self.l.append(a)
        t = n
        while t != 0:
            if self.l[t][1] < self.l[(t-1)//2][1]:
                self.l[t],self.l[(t-1)//2] = self.l[(t-1)//2],self.l[t]
                t = (t-1)//2
            else:break

    def heappop(self):
        n=len(self.l)
        if n == 0:
            return (-1,0)
        if n == 1:
            return self.l.pop()
        ret = self.l[0]
        self.l[0] = self.l.pop()
        n -= 1
        t = 0
        while t<n:
            child1 = t*2+1
            child2 = t*2+2
            if child1 >= n:
                break
            elif child2 >= n:
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t],self.l[child1] = self.l[child1],self.l[t]
                    t = child1
                else:break
            else:
                if self.l[child2][1] < self.l[child1][1]:
                    child1,child2 = child2,child1
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t],self.l[child1] = self.l[child1],self.l[t]
                    t = child1
                elif self.l[t][1] > self.l[child2][1]:
                    self.l[t],self.l[child2] = self.l[child2],self.l[t]
                    t = child2
                else:break
        return ret
    
    def isnotblank(self):
        if self.l:return True
        else:return False

def dijkstra(s,g,N,e):
    INF =10**10
    res = [INF for _ in range(N)]
    q=lheapq([(s,0)])
    while res[g]==INF:
        while q.isnotblank():
            des,dis = q.heappop()
            if res[des] == INF:
                res[des] = dis
                break
        for se in e[des]:
            if res[se[0]] == INF:
                q.heappush((se[0],se[1]+res[des]))
    return res[g]

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

res = 0
for i in range(M):
    g=[[] for _ in range(N)]
    for j in range(M):
        if j!=i:
            a,b,c = e[j][0],e[j][1],e[j][2]
            g[a].append((b,c))
            g[b].append((a,c))
    a,b,c = e[i][0],e[i][1],e[i][2]
    if dijkstra(a,b,N,g) == w[a][b]:
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
links = [[[1e11*(i!=j), [1e11]]for i in range(n)]for j in range(n)]
used = [[0]*n for i in range(n)]

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if links[i][j][0]>=links[i][k][0]+links[k][j][0]:
                links[i][j] = [links[i][k][0]+links[k][j][0], links[i][k][1]+links[k][j][1]]

for i in range(n):
    for j in range(n):
        prev = links[i][j][1][0]
        for k in links[i][j][1]:
            if prev!=k and (not 1e11 in [prev,k]): used[prev][k] = 0
            prev = k

#print(links)
#print(used)

ans = 0
for i in range(n): ans += sum(used[i])
print(ans//2)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
links = [[[1e11*(i!=j), []]for i in range(n)]for j in range(n)]
used = [[0]*n for i in range(n)]

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if links[i][j][0]>=links[i][k][0]+links[k][j][0]:
                links[i][j] = [links[i][k][0]+links[k][j][0], links[i][k][1]+[k]+links[k][j][1]]

for i in range(n):
    for j in range(n):
        prev = links[i][j][1][0]
        for k in links[i][j][1]:
            if prev!=k: used[prev][k] = 0
            prev = k

#print(links)
#print(used)

ans = 0
for i in range(n): ans += sum(used[i])
print(ans//2)

Submission status: Wrong Answer

Solution code:
import sys
sys.stdin.readline

def main():
    N, M = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    INF = float("inf")
    D = [[INF] * 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 = M - sum(any(D[i][a-1] + c == D[i][b-1] for i in range(N)) for a, b, c in ABC)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

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

l = [[0 for i in range(n)] for j in range(n)]
cl = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    a,b,c=list(map(int,input().split()))
    a-=1
    b-=1
    l[a][b]=c
    l[b][a]=c
    
for i in range(n):
    for j in range(n):
        if i==j:
            cl[i][j]=1
            continue
        dr = l[i][j]
        mind = 9999
        minl = []
        minl.clear()
        for k in range(n):
            if (i==k or j==k):
                continue
            d = l[j][k]+l[i][k]
            if d < mind:
                minl.clear()
                mind=d
                minl.append(k)
            elif d == mind:
                minl.append(k)
            
        if dr <= mind:
            cl[i][j]=1
            cl[j][i]=1
        if mind <= dr:
            for x in minl:
                cl[i][x]=1            
                cl[x][i]=1
                cl[j][x]=1
                cl[x][j]=1

c=0

for i in range(n):
    for j in range(n):          
        if cl[i][j]==0:
            c+=1

print(int(c/2))

Submission status: Wrong Answer

Solution code:
import sys

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

l = [[0 for i in range(n)] for j in range(n)]
cl = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    a,b,c=list(map(int,input().split()))
    a-=1
    b-=1
    l[a][b]=c
    l[b][a]=c
    
for i in range(n):
    for j in range(n):
        if i==j:
            cl[i][j]=1
            continue
        dr = l[i][j]
        mind = 9999
        minl = []
        for k in range(n):
            if (i==k or j==k):
                continue
            d = l[j][k]+l[i][k]
            if d < mind:
                minl.clear()
                mind=d
                minl.append(k)
            elif d == mind:
                minl.append(k)
            
        if dr <= mind:
            cl[i][j]=1
            cl[j][i]=1
        if mind <= dr:
            for x in minl:
                cl[i][x]=1            
                cl[x][i]=1
                cl[j][x]=1
                cl[x][j]=1

c=0

for i in range(n):
    for j in range(n):          
        if cl[i][j]==0:
            c+=1

print(int(c/2))

Submission status: Wrong Answer

Solution code:
import sys

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

l = [[0 for i in range(n)] for j in range(n)]
cl = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    a,b,c=list(map(int,input().split()))
    a-=1
    b-=1
    l[a][b]=c
    l[b][a]=c
    
for i in range(n):
    for j in range(n):
        if i==j:
            cl[i][j]=1
            cl[j][i]=1
            continue
        dr = l[i][j]
        mind = 9999
        minl = []
        for k in range(n):
            if (i==k or j==k):
                continue
            d = l[j][k]+l[i][k]
            if d < mind:
                minl.clear()
                mind=d
                minl.append(k)
            elif d == mind:
                minl.append(k)
            
        if dr <= mind:
            cl[i][j]=1
            cl[j][i]=1
        if mind <= dr:
            for x in minl:
                cl[i][x]=1            
                cl[x][i]=1
                cl[j][x]=1
                cl[x][j]=1

c=0

for i in range(n):
    for j in range(n):          
        if cl[i][j]==0:
            c+=1

print(int(c/2))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split()))for i in range(m)]
dist=[[1<<29]*n for i in range(n)]
for i in range(n): dist[i][i]=0
for a in l:
  dist[a[0]-1][a[1]-1] = min(dist[a[0]-1][a[1]-1],a[2])
  dist[a[1]-1][a[0]-1] = min(dist[a[1]-1][a[0]-1],a[2])
print(dist)
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 a in l:
  flag=False
  for j in range(n): 
    if dist[j][a[0]-1]+a[2]==dist[j][a[1]-1]: flag=True
  if flag: ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
# ABC051 D - Candidates of No Shortest Paths
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
def WF():
    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])

n,m=nm()
aa=[]
bb=[]
cc=[]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    aa.append(a)
    bb.append(b)
    cc.append(c)

d=[[10**5]*n for i in range(n)]
for i in range(m):
    d[aa[i]][bb[i]]=min(d[aa[i]][bb[i]],cc[i])
    d[bb[i]][aa[i]]=min(d[bb[i]][aa[i]],cc[i])
WF()

ans=m
for i in range(m):
    short=False
    for j in range(n):
        if d[j][aa[i]]+cc[i]==d[j][bb[i]]:
            short=True
    if short:
        ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
MAX_D = 10**9
def solve():
    N,M = map(int, input().split())
    d = [[MAX_D]*N for _ in range(N)]
    edges = [[False]*N for _ in range(N)]
    for _ in range(M):
        a,b,c = map(int, input().split())
        edges[a-1][b-1] = True
        edges[b-1][a-1] = True
        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):
                if i != j and d[i][j] > d[i][k]+d[k][j]:
                    # print(i,k,j, d[i][j], d[i][k], d[k][j])
                    edges[i][j] = False
                    edges[i][k] = True
                    edges[k][j] = True
                    d[i][j] = d[i][k]+d[k][j]
                    
    # print(edges)
    print(M - sum(map(sum, edges))//2)
    
solve()

Submission status: Wrong Answer

Solution code:
MAX_D = 10**9
def solve():
    N,M = map(int, input().split())
    d = [[MAX_D]*N for _ in range(N)]
    edges = [[False]*N for _ in range(N)]
    for _ in range(M):
        a,b,c = map(int, input().split())
        edges[a-1][b-1] = True
        edges[b-1][a-1] = True
        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):
                if d[i][j] > d[i][k]+d[k][j]:
                    # print(i,k,j)
                    edges[i][j] = False
                    edges[i][k] = True
                    edges[k][j] = True
                    d[i][j] = d[i][k]+d[k][j]
                    
    # print(edges)
    print(M - sum(map(sum, edges))//2)
    
solve()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
inf = float("inf")
dist = [[inf for _ in range(N)] for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

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

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

ans = M
for a, b, c in T:
    check = False
    for i in range(N):
        if dist[i][a] + c == dist[i][b]:
            check = True
    if check:
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import defaultdict
    from heapq import heappop, heappush
    import sys
    input=sys.stdin.readline 

    class Graph:
    
        def __init__(self):
            self.graph = defaultdict(list)
            self.vertices = set()
            self.edges = []
    
        def add_edge(self, a, b, weight=1):
            self.graph[a].append((b, weight))
            self.vertices |= {a, b}
            self.edges.append((a, b, weight))
    
        def get_vertices(self):
            return sorted(list(self.vertices))
    
        def num_of_vertices(self):
            return len(self.vertices)
    
        def get_edges(self):
            return self.edges
    
        def num_of_edges(self):
            return len(self.edges)
    
    class Dijkstra:
    
        def __init__(self, graph, start):
            self.g = graph.graph
    
            self.dist = defaultdict(lambda: 10**12)
            self.dist[start] = 0
    
            self.prev = defaultdict(lambda: None)
    
            self.Q = []
            heappush(self.Q, (0, 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):
    
            return self.dist[goal]
    
        def shortest_path(self, goal):
    
            path = []
            vertice = goal
            while vertice is not None:
                path.append(vertice)
                vertice = self.prev[vertice]
    
            return path[::-1]

    N, M = map(int, input().split())
    G = Graph()
    T = []
    C = defaultdict(int)
    for _ in range(M):
        a, b, c = map(int, input().split())
        G.add_edge(a, b, c)
        G.add_edge(b, a, c)
        T.append(tuple(sorted([a, b])))

    for i in range(1, N+1):
        for j in range(1, N+1):
            D = Dijkstra(G, i)
            P = D.shortest_path(j)
            for k in range(len(P)-1):
                a, b = P[k], P[k+1]
                C[tuple(sorted([a, b]))] = 1

    ans = 0
    for a, b in T:
        if C[(a, b)] == 0:
            ans += 1

    print(ans)

if __name__ == "__main":
    main()

Submission status: Wrong Answer

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

INF = 10 ** 10
dist = [[INF for _ in range(N + 1)] for _ in range(N + 1)]

for a, b, c in ABC:
  dist[a][b] = c
  dist[b][a] = c

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

check = [0] * (M)
for i in range(M):
  a, b, c = ABC[i]
  for j in range(1, N + 1):
    if dist[j][b] == dist[j][a] + c:
      check[i] = 1
      break
print(len(check) - sum(check))

Submission status: Wrong Answer

Solution code:
# ワーシャルフロイド法
n,w = map(int,input().split()) #n:頂点数　w:辺の数

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

# 入力の辺リスト
e_list = []
#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
    # 入力の辺リストに追加
    e_list.append([x-1,y-1,z])
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
    
#d[i][j]: iからjへの最短距離
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])

# 移動コスト表示
print(d)
##############################

# 辺の数から使用済みの数を引く
ans = w
for x, y, z in e_list:
    # dにx,y,z の情報が残っていたら利用されている
    if d[x][y] == z:
        ans -= 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split()]
print(m-(n-1))

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush, heappop

INF = 10 ** 7

n, m = map(int, sys.stdin.readline().split())
abc = map(int, sys.stdin.read().split())
abc = zip(*[abc] * 3)
graph = [[] for _ in range(n)]
for a, b, c in abc:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

def dijkstra(v):
    used_edges = [set() for _ in range(n)]
    hq = []
    heappush(hq, (0, v, None))
    dist = [INF] * n
    pars = [set() for _ in range(n)]
    while hq:
        d, x, z = heappop(hq)
        if 0 < dist[x] < INF:
            if d == dist[x]:
                pars[x].add(z)
                used_edges[x] |= used_edges[z]
                if z < x:
                    used_edges[x].add((z, x))
                else:
                    used_edges[x].add((x, z))
            continue   
        
        dist[x] = d
        if x != v:
            used_edges[x] |= used_edges[z]
            pars[x].add(z)
            if z < x:
                used_edges[x].add((z, x))
            else:
                used_edges[x].add((x, z))

        for (y, c) in graph[x]:
            if y in pars[x] or pars[y]:
                continue
            heappush(hq, (d+c, y, x))

    res = set()
    for i in range(n):
        res |= used_edges[i]
    return res

def main():
    res = set()
    for v in range(n):
        res |= dijkstra(v)
    
    ans = m - len(res)
    return ans

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

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush, heappop

INF = 10 ** 7

n, m = map(int, sys.stdin.readline().split())
abc = map(int, sys.stdin.read().split())
abc = zip(*[abc] * 3)
graph = [[] for _ in range(n)]
for a, b, c in abc:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

def dijkstra(v):
    used_edges = [set() for _ in range(n)]
    hq = []
    heappush(hq, (0, v, None))
    dist = [INF] * n
    pars = [set() for _ in range(n)]
    while hq:
        d, x, z = heappop(hq)
        if 0 < dist[x] < INF:
            if d == dist[x]:
                pars[x].add(z)
                used_edges[x] |= used_edges[z]
                if z < x:
                    used_edges[x].add((z, x))
                else:
                    used_edges[x].add((x, z))
            continue   
        
        dist[x] = d
        if x != v:
            used_edges[x] |= used_edges[z]
            pars[x].add(z)
            if z < x:
                used_edges[x].add((z, x))
            else:
                used_edges[x].add((x, z))

        for (y, c) in graph[x]:
            if y in pars[x]:
                continue
            heappush(hq, (d+c, y, x))

    res = set()
    for i in range(n):
        res |= used_edges[i]
    return res

def main():
    res = set()
    for v in range(n):
        res |= dijkstra(v)
    
    ans = m - len(res)
    return ans

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G = [[10**8]*N for _ in range(N)]   # 1-indexed
for _ in range(M):
    A, B, C = map(int, input().split())
    # 無向グラフ
    G[A-1][B-1] = C
    G[B-1][A-1] = C

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(i+1, N):
            if G[i][j] > G[i][k]+G[j][k]:
                if G[i][j] != 10**8:
                    ans += 1
                G[i][j] = G[i][k]+G[j][k]
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
G = [[10**8]*N for _ in range(N)]   # 1-indexed
for _ in range(M):
    A, B, C = map(int, input().split())
    # 無向グラフ
    G[A-1][B-1] = C
    G[B-1][A-1] = C

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