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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import collections
import heapq


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1


# Prim法で頂点0からの最小全域木を求める
def compute_mst_prim(max_v, adj_list):
    # pred[u]は頂点uの「ひとつ前」の頂点を表す
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # uとpred[u]を結ぶ辺の重みがkey[u]に入る
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # 二分ヒープを優先度付きキューとして用いる
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # 優先度付きキューに頂点が入っているかを示す配列
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def main():
    max_v, max_e = map(int, input().split())
    adjacency_list = collections.defaultdict(set)
    for _ in range(max_e):
        s, t, w = map(int, input().split())
        adjacency_list[s-1].add(AdjacentVertex(t-1, w))
        adjacency_list[t-1].add(AdjacentVertex(s-1, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(max_e-len(_))
    #print(key)
    #print(sum(key.values()))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[9999999 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	org = copy.deepcopy(maps)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				if maps[i][j] == 9999999:
					continue
				if i <= j:
					continue
				maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])
				maps[j][i] = min(maps[i][j], maps[i][k] + maps[k][j])
			
	for i in range(N):
		for j in range(N):
			if i <= j:
				continue
			if org[i][j] == 9999999:
				continue
			if org[i][j] != maps[i][j]:
				ans += 1
		
	print(ans)
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[9999999 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	org = copy.deepcopy(maps)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				if maps[i][j] == 9999999:
					continue
				if i <= j:
					continue
				maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])
			
	for i in range(N):
		for j in range(N):
			if i <= j:
				continue
			if org[i][j] == 9999999:
				continue
			if org[i][j] != maps[i][j]:
				ans += 1
		
	print(ans)
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[9999999 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	org = copy.deepcopy(maps)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				if maps[i][j] == 9999999:
					continue
				if i <= j:
					continue
				maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])
			
	for i in range(N):
		for j in range(N):
			if i <= j:
				continue
			if org[i][j] != maps[i][j]:
				ans += 1
		
	print(ans)
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[9999999 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	org = copy.deepcopy(maps)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				if maps[i][j] == 9999999:
					continue
				if i <= j:
					continue
				maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])
			
	for i in range(N):
		for j in range(N):
			if i <= j:
				continue
			if org[i][j] != maps[i][j]:
				ans += 1
		
	print(ans // 2)
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[9999999 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	org = copy.deepcopy(maps)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				if maps[i][j] == 9999999:
					continue
				maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])
			
	for i in range(N):
		for j in range(N):
			if org[i][j] != maps[i][j]:
				ans += 1
		
	print(ans // 2)
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[9999999 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	for k in range(N):
		for i in range(N):
			for j in range(N):
				if maps[i][j] == 9999999:
					continue
				tmp = min(maps[i][j], maps[i][k] + maps[k][j])
				if tmp != maps[i][j]:
					ans += 1
					maps[i][j] = tmp
			
	print(ans // 2)
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[2000 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	for k in range(N):
		for i in range(N):
			for j in range(N):
				if maps[i][j] == 2000:
					continue
				tmp = min(maps[i][j], maps[i][k] + maps[k][j])
				if tmp != maps[i][j]:
					ans += 1
					maps[i][j] = tmp
			
	print(ans // 2)
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[2000 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	for k in range(N):
		for i in range(N):
			for j in range(N):
				if maps[i][j] == 2000:
					continue
				tmp = min(maps[i][j], maps[i][k] + maps[k][j])
				if tmp != maps[i][j]:
					ans += 1
			
	print(ans // 2)
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d, V, M): #d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
    for k in range(V):
        for i in range(V):
            for j in range(V):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
                
    return d
    
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
dist = [[10 ** 5 for i in range(N)] for i in range(N)]

for l in L:
    l[0] -= 1
    l[1] -= 1
      
for i in range(M):
    dist[L[i][0]][L[i][1]] = L[i][2]
    dist[L[i][1]][L[i][0]] = L[i][2]

dist = warshall_floyd(dist, N, M)

res = M
for i in range(M):
    if dist[L[i][0]][L[i][1]] != L[i][2]:
        res -= 1
            
print(res)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d, V, M): #d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
    tmp = M
    for k in range(V):
        flag = False
        for i in range(V):
            for j in range(V):
                if d[i][j] > d[i][k] + d[k][j]:
                    if d[i][j] != 10 ** 5:
                        flag = True
                    d[i][j] =  d[i][k] + d[k][j]
                    
                    
        if flag == True:
            tmp -= 1
                
    return tmp
    
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
dist = [[10 ** 5 for i in range(N)] for i in range(N)]

for i in range(M):
    dist[L[i][0]-1][L[i][1]-1] = L[i][2]
    dist[L[i][1]-1][L[i][0]-1] = L[i][2]

res = warshall_floyd(dist, N, M)

print(M - res)

Submission status: Wrong Answer

Solution code:
#クラスカル法 最小全域木を求めるO(nlogn)

#union-find木
#クラスカル法にはUnion-find木が必要
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(n)] #根の深さ

    #xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合のマージ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    #xとyが同じ集合に属するかを判定
    def same(self, x, y):
        return self.find(x) == self.find(y)


#クラスカル法
# V: 頂点集合(リスト) E: 辺集合[始点, 終点, 重み](リスト)
class kruskal():
    def __init__(self, V, E):
        self.V = V
        self.E = E
        self.E.sort(key=lambda x: x[2]) #辺の重みでソート

    def weight(self):
        UF = UnionFind(len(V)) #頂点数でUnion Find Treeを初期化
        res = 0
        for i in range(len(self.E)):
            e = self.E[i]

            if (UF.same(e[0], e[1])) == False:
                UF.unite(e[0], e[1])
                res += e[2]

        return res

    def edge(self):
        UF = UnionFind(len(self.V)) #頂点数でUnion Find Treeを初期化
        res_E = []
        for i in range(len(self.E)):
            e = self.E[i]

            if (UF.same(e[0], e[1])) == False:
                UF.unite(e[0], e[1])
                res_E.append(e)

        return res_E

    def node(self):
        UF = UnionFind(len(V)) #頂点数でUnion Find Treeを初期化
        res_V = []
        for i in range(len(E)):
            e = E[i]

            if (UF.same(e[0], e[1])) == False:
                UF.unite(e[0], e[1])
                res_V.append(e[0])
                res_V.append(e[1])

        return list(set(res_V))

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

for l in L:
    l[0] -= 1
    l[1] -= 1

V = [i for i in range(N)]

kr = kruskal(V, L)

print(M - len(kr.edge()))

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import *
d=defaultdict(list)
n,m=map(int,input().split())

for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#print(d.keys())

#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})

def DIJKSTRA(point,d):
    cost      = {node:np.inf for node in d.keys()}
    preference= {node:  None for node in d.keys()}#最適路のこと
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while True:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
   #     del Q[prefnd]
        if len(Q)==0:
            break #全部の点消したら終了
        for pathcost in d[prefnd]:  #次の点とそこまでのコスト
            tempcost=cost[prefnd]+pathcost[1]  #スタートからそこまでのコストを計算
            if tempcost<cost[pathcost[0]]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[pathcost[0]]=tempcost #最小値更新
                preference[pathcost[0]]=prefnd
    return len(preference)
        
print(m-DIJKSTRA(1,d)+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import *
d=defaultdict(list)
n,m=map(int,input().split())

for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#print(d.keys())

#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})

def DIJKSTRA(point,d):
    cost      = {node:np.inf for node in d.keys()}
    preference= {node:  None for node in d.keys()}#最適路のこと
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while True:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
   #     del Q[prefnd]
        if np.isinf(cost[prefnd]): 
            return np.inf , []    #もし探した点がinfだったらinfを返す
        if len(Q)==0:
            break #全部の点消したら終了
        for pathcost in d[prefnd]:  #次の点とそこまでのコスト
            tempcost=cost[prefnd]+pathcost[1]  #スタートからそこまでのコストを計算
            if tempcost<cost[pathcost[0]]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[pathcost[0]]=tempcost #最小値更新
                preference[pathcost[0]]=prefnd
    return len(preference)
        
print(m-DIJKSTRA(1,d)+1)

Submission status: Wrong Answer

Solution code:
V,E = map(int, input().split())

inf = float("inf")
# edges = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]
edges = [ [inf]*V for _ in range(V)]
# a,b,c = [],[],[]

ee = []
for _ in [None]*E:
    s,t,cost  = map(int, input().split())
    ee.append( (s-1, t-1, cost) )

    edges[s-1][t-1] = cost
    edges[t-1][s-1] = cost



for i in range(V):
    for j in range(V):
        for k in range(V):
            edges[i][j] = min(edges[i][j], edges[i][k] + edges[k][j])

ans = 0
for i in range(E):
    shortest = False
    e1,e2,c = ee[i]

    if edges[e1][e2] != c:
        ans += 1




print(ans)

Submission status: Wrong Answer

Solution code:
V,E = map(int, input().split())

inf = float("inf")
edges = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]
# a,b,c = [],[],[]

ee = []
for _ in [None]*E:
    s,t,cost  = map(int, input().split())
    ee.append( (s-1, t-1, cost) )

    edges[s-1][t-1] = cost
    edges[t-1][s-1] = cost



for i in range(V):
    for j in range(V):
        for k in range(V):
            edges[i][j] = min(edges[i][j], edges[i][k] + edges[k][j])

ans = 0
for i in range(E):
    shortest = False
    e1,e2,c = ee[i]

    if edges[e1][e2] != c:
        ans += 1




print(ans)

Submission status: Wrong Answer

Solution code:
V,E = map(int, input().split())

inf = float("inf")
edges = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]
# a,b,c = [],[],[]

ee = []
for _ in [None]*E:
    s,t,cost  = map(int, input().split())
    ee.append( (s-1, t-1, cost) )

    edges[s-1][t-1] = cost
    edges[t-1][s-1] = cost

for i in range(V):
    edges[i][i] = 0


for i in range(V):
    for j in range(V):
        for k in range(V):
            edges[i][j] = min(edges[i][j], edges[i][k] + edges[k][j])

ans = 0
for i in range(E):
    shortest = False
    e1,e2,c = ee[i]

    if edges[e1][e2] != c:
        ans += 1




print(ans)

Submission status: Wrong Answer

Solution code:
V,E = map(int, input().split())

inf = float("inf")
edges = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]
# a,b,c = [],[],[]

ee = []
for _ in [None]*E:
    s,t,cost  = map(int, input().split())
    ee.append( (s-1, t-1, cost) )

    edges[s-1][t-1] = cost
    edges[t-1][s-1] = cost

for i in range(V):
    edges[i][i] = 0


for i in range(V):
    for j in range(V):
        for k in range(V):
            edges[i][j] = min(edges[i][j], edges[i][k] + edges[k][j])

ans = E
for i in range(E):
    shortest = False
    e1,e2,c = ee[i]
    for j in range(V):
        if edges[j][e1] + c == edges[j][e2]:
            shortest = True

    if shortest:
        ans -= 1




print(ans)

Submission status: Wrong Answer

Solution code:
V,E = map(int, input().split())

inf = float("inf")
edges = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]
ee = []

for _ in [None]*E:
    s,t,cost  = map(int, input().split())
    ee.append(( s-1,t-1, cost) )
    edges[s-1][t-1] = cost
    edges[t-1][s-1] = cost


d = [ [inf]*V for _ in range(V)]
for i in range(V):
    d[i][i] = 0

for i in range(E):
    # print(len(ee))
    # exit(0)
    d[ee[i][0]][ee[i][1]] = min(d[ee[i][0]][ee[i][1]] , ee[i][2])
    d[ee[i][1]][ee[i][0]] = min(d[ee[i][1]][ee[i][0]] , ee[i][2])

for i in range(V):
    for j in range(V):
        for k in range(V):
            d[j][i] = min( d[j][i], d[j][k] + d[k][i])
                    # vertices[j][k] + vertices[k][i])



ss = set()

ans = E
for i in range(E):
    shortest = False
    e1,e2,c = ee[i]
    for j in range(V):
        if d[j][e1] + c == d[j][e2]:
            shortest = True

    if shortest:
        ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
V,E = map(int, input().split())

inf = float("inf")
edges = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]
ee = []

for _ in [None]*E:
    s,t,cost  = map(int, input().split())
    ee.append(( s-1,t-1, cost) )
    edges[s-1][t-1] = cost
    edges[t-1][s-1] = cost


d = [ [inf]*V for _ in range(V)]
for i in range(V):
    d[i][i] = 0

for i in range(E):
    # print(len(ee))
    # exit(0)
    d[ee[i][0]][ee[i][1]] = min(d[ee[i][0]][ee[i][1]] , ee[i][2])
    d[ee[i][1]][ee[i][0]] = min(d[ee[i][1]][ee[i][0]] , ee[i][2])

for i in range(V):
    for j in range(V):
        for k in range(V):
            d[j][i] = min( d[j][i], d[j][k] + d[k][i])
                    # vertices[j][k] + vertices[k][i])



ss = set()

ans = E
for i in range(E):
    e1,e2 = ee[i][:2]
    shortest = False

    try:

        for s in range(V):
            for t in range(V):
        
                if d[s][t] == d[s][e1] + edges[e1][e2] + d[e2][t]:
                    ans -= 1
                    raise "a"
                # ss.add( (e1, e2) )
    except:
        pass


# ans =  E
# ans = ans - len(ss)
# ans = ans // 2

print(ans)

Submission status: Wrong Answer

Solution code:
V,E = map(int, input().split())

inf = float("inf")
edges = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]
ee = []

for _ in [None]*E:
    s,t,cost  = map(int, input().split())
    ee.append(( s-1,t-1, cost) )
    edges[s-1][t-1] = cost
    edges[t-1][s-1] = cost


d = [ [inf]*V for _ in range(V)]
for i in range(V):
    d[i][i] = 0

for i in range(E):
    # print(len(ee))
    # exit(0)
    d[ee[i][0]][ee[i][1]] = min(d[ee[i][0]][ee[i][1]] , ee[i][2])
    d[ee[i][1]][ee[i][0]] = min(d[ee[i][1]][ee[i][0]] , ee[i][2])

for i in range(V):
    for j in range(V):
        for k in range(V):
            d[j][i] = min( d[j][i], d[j][k] + d[k][i])
                    # vertices[j][k] + vertices[k][i])



ss = set()
for s in range(V):
    for t in range(V):
        if s == t: continue

        for i in range(E):
            e1,e2 = ee[i][:2]
            
            if d[s][t] == d[s][e1] + edges[e1][e2] + d[e2][t]:
                ss.add( (e1, e2) )


ans =  E
ans = ans - len(ss)
# ans = ans // 2

print(ans)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
V,E = map(int, input().split())
inf = float("inf")
vertices = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]

for _ in [None]*E:
    s,t,cost  = map(int, input().split())
    vertices[s-1][t-1] = cost
    vertices[t-1][s-1] = cost


d = [ [inf]*V for _ in range(V)]
for i in range(V):
    for j in range(V):
        for k in range(V):
            d[j][i] = min( d[j][i], 
                    vertices[j][k] + vertices[k][i])


ss = set()
for s in range(V):
    for t in range(V):
        if s == t: continue

        # for i in range(V):
        #     # for j in range(V):
        #         # if i == j or vertices[i][j] == inf: continue
        #         if vertices[i][t] == inf: continue
        #         if d[s][t] == d[s][i] + vertices[i][t]:
        #             ss.add( (i,t) )

        for i in range(V):
            for j in range(V):
                if i == j or vertices[i][j] == inf: continue
                if d[s][t] == d[s][i] + vertices[i][j] \
                 + d[j][t]:
                     
                     if d[s][t] != inf:
                         ss.add( (i,j) )

ans =  2*E
ans = ans - len(ss)
ans = ans // 2

print(ans)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
V,E = map(int, input().split())
inf = float("inf")
vertices = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]

for _ in [None]*E:
    s,t,cost  = map(int, input().split())
    vertices[s-1][t-1] = cost
    vertices[t-1][s-1] = cost


d = [ [inf]*V for _ in range(V)]
for i in range(V):
    for j in range(V):
        for k in range(V):
            d[j][i] = min( d[j][i], 
                    vertices[j][k] + vertices[k][i])


ss = set()
for s in range(V):
    for t in range(V):
        # if s == t: continue
        
        for i in range(V):
            for j in range(V):
                if i == j or vertices[i][j] == inf: continue
                if d[s][t] == d[s][i] + vertices[i][j] \
                 + d[j][t]:
                     ss.add( (i,j) )

ans =  2*E
ans = ans - len(ss)
ans = ans // 2

print(ans)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
V,E = map(int, input().split())
inf = float("inf")
vertices = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]
used_edge_map = [ [-1]*V for _ in range(V)]
for _ in [None]*E:
    s,t,cost  = map(int, input().split())
    vertices[s-1][t-1] = cost
    vertices[t-1][s-1] = cost

    used_edge_map[s-1][t-1] = 0
    used_edge_map[t-1][s-1] = 0

s = set()

d = [ [inf]*V for _ in range(V)]
for i in range(V):
    for j in range(V):
        for k in range(V):
            # if c2 > vertices[j][k] + vertices[k][i]:
            d[j][i] = min( d[j][i], 
                    vertices[j][k] + vertices[k][i])


ss = set()
for s in range(V):
    for t in range(V):
        if s == t: continue
        
        # make edge
        for i in range(V):
            for j in range(V):
                if i == j or vertices[i][j] == inf: continue
                if d[s][t] == d[s][i] + vertices[i][j] \
                 + d[j][t]:
                     ss.add( (i,j) )
# print(ss)
                



        # if i == j: continue
        
        

# for i in range(V):
#     for j in range(V):
#         c2 = vertices[j][i]
#         for k, (c1,c3) in enumerate(zip(vertices[j], vertices[i])):
#             if c1 > c2+c3:
#                 s.add( (j,k) ) # $B:GC;7PO)(B
#                 vertices[j][k] = c2+c3
#             # if c1 <= c2+c3:
#             #     s.add( (j,k) ) # $B:GC;7PO)(B
#             #     vertices[j][k] = c1 #  c2+c3


# print(s)
ans =  2*E
ans = ans - len(ss)
ans = ans // 2

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
dist=defaultdict(int)
branch=[]
for k in range(m):
    branch.append(tuple(map(int,input().split())))
branch.sort(key=lambda x:x[2])
ans=0
for k in range(m):
    check=branch[k]
    a,b,c=check[0],check[1],check[2]
    if dist[(a,b)]==0:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            elif dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            elif dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
    elif dist[(a,b)]<c:
        ans+=1
    elif dist[(a,b)]>c:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            elif dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            elif dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
            elif dist[(a,i)]!=0 and dist[(a,i)]!=0:
                if dist[(a,i)]+c<dist[(b,i)]:
                    dist[(b,i)]=dist[(a,i)]+c
                    dist[(i,b)]=dist[(a,i)]+c
                if dist[(b,i)]+c<dist[(a,i)]:
                    dist[(a,i)]=c+dist[(b,i)]
                    dist[(i,a)]=c+dist[(b,i)]
res=0
for i in range(m):
    now=0
    check=branch[i]
    a,b=check[0],check[1]
    for j in range(1,1+n):
        
        if abs(dist[(j,a)]-dist[j,b])==check[2]:
            now=1
            break
    if now==0:
        res+=1
        
print(res)

Submission status: Wrong Answer

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

dist=[]
def makedist(start,branch):
    check={start,}
    mind=[10**7 for i in range(n)]
    mind[start]=0
    while len(check)>0:
        now=check.pop()
        for k in branch[now]:
            if k[1]+mind[now]<mind[k[0]]:
                mind[k[0]]=k[1]+mind[now]
                check|={k[0],}
    return mind
for i in range(n):
    dist.append(makedist(i,branch))
ans=0
for k in edge:
    for s in range(n):
        if s==k[0] or s==k[1]:continue
        elif abs(dist[s][k[0]]-dist[s][k[1]])==k[2]:
            ans+=1
            break
print(m-ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
dist=defaultdict(int)
branch=[]
for k in range(m):
    branch.append(tuple(map(int,input().split())))
branch.sort(key=lambda x:x[2])
ans=0
for k in range(m):
    check=branch[k]
    a,b,c=check[0],check[1],check[2]
    if dist[(a,b)]==0:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            elif dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            elif dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
    elif dist[(a,b)]<c:
        ans+=1
    elif dist[(a,b)]>c:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            elif dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            elif dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
            elif dist[(a,i)]!=0 and dist[(a,i)]!=0:
                if dist[(a,i)]+c<dist[(b,i)]:
                    dist[(b,i)]=dist[(a,i)]+c
                    dist[(i,b)]=dist[(a,i)]+c
                if dist[(b,i)]+c<dist[(a,i)]:
                    dist[(a,i)]=c+dist[(b,i)]
                    dist[(i,a)]=c+dist[(b,i)]
res=0
for i in range(m):
    now=0
    check=branch[i]
    a,b=check[0],check[1]
    for j in range(1,1+n):
        if j==a or j==b:continue
        if abs(dist[(j,a)]-dist[j,b])==check[2]:
            now=1
            break
    if now==0:
        res+=1
        
print(res)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
dist=defaultdict(int)
branch=[]
for k in range(m):
    branch.append(tuple(map(int,input().split())))
branch.sort(key=lambda x:x[2])
ans=0
for k in range(m):
    check=branch[k]
    a,b,c=check[0],check[1],check[2]
    if dist[(a,b)]==0:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            elif dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            elif dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
    elif dist[(a,b)]<c:
        ans+=1
    elif dist[(a,b)]>c:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            elif dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            elif dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
            elif dist[(a,i)]!=0 and dist[(a,i)]!=0:
                if dist[(a,i)]+c<dist[(b,i)]:
                    dist[(b,i)]=dist[(a,i)]+c
                    dist[(i,b)]=dist[(a,i)]+c
                if dist[(b,i)]+c<dist[(a,i)]:
                    dist[(a,i)]=c+dist[(b,i)]
                    dist[(i,a)]=c+dist[(b,i)]
res=0
for i in range(m):
    now=0
    check=branch[i]
    a,b=check[0],check[1]
    for j in range(1,1+n):
        if j==a or j==b:continue
        if dist[(j,a)]+check[2]==dist[j,b]:
            now=1
            break
    if now==0:
        res+=1
        
print(res)