Problem:


Score : 400 points

Problem Statement

You are given an undirected connected weighted graph with N vertices and M edges that contains neither self-loops nor double edges.

The i-th (1≤i≤M) edge connects vertex a_i and vertex b_i with a distance of c_i.

Here, a self-loop is an edge where a_i = b_i (1≤i≤M), and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).

A connected graph is a graph where there is a path between every pair of different vertices.

Find the number of the edges that are not contained in any shortest path between any pair of different vertices.  

Constraints

2≤N≤100 

N-1≤M≤min(N(N-1)/2,1000) 

1≤a_i,b_i≤N 

1≤c_i≤1000

c_i is an integer.

The given graph contains neither self-loops nor double edges.

The given graph is connected.

Input

The input is given from Standard Input in the following format:

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

Output

Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.

Sample Input 1

3 3
1 2 1
1 3 1
2 3 3

Sample Output 1

1

In the given graph, the shortest paths between all pairs of different vertices are as follows:

The shortest path from vertex 1 to vertex 2 is: vertex 1 → vertex 2, with the length of 1.

The shortest path from vertex 1 to vertex 3 is: vertex 1 → vertex 3, with the length of 1.

The shortest path from vertex 2 to vertex 1 is: vertex 2 → vertex 1, with the length of 1.

The shortest path from vertex 2 to vertex 3 is: vertex 2 → vertex 1 → vertex 3, with the length of 2.

The shortest path from vertex 3 to vertex 1 is: vertex 3 → vertex 1, with the length of 1.

The shortest path from vertex 3 to vertex 2 is: vertex 3 → vertex 1 → vertex 2, with the length of 2.

Thus, the only edge that is not contained in any shortest path, is the edge of length 3 connecting vertex 2 and vertex 3, hence the output should be 1.

Sample Input 2

3 2
1 2 1
2 3 1

Sample Output 2

0

Every edge is contained in some shortest path between some pair of different vertices.



Sample input:
3 3
1 2 1
1 3 1
2 3 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
read = sys.stdin.read

N, M, *abc = map(int, read().split())
a, b, c = zip(*zip(*[iter(abc)] * 3))

graph = csr_matrix((c, (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False)

answer = 0

for i, j, k in zip(a, b, c):
    k = float(k)
    if k == distance[i][j]:
        continue

    for s in range(1, N + 1):
        if i == s or j == s:
            continue

        if k + distance[j][s] == distance[i][s]:
            break

        if k + distance[i][s] == distance[j][s]:
            break

        answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
read = sys.stdin.read

N, M, *abc = map(int, read().split())
a, b, c = zip(*zip(*[iter(abc)] * 3))

graph = csr_matrix((c, (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False)

answer = 0

for i, j, k in zip(a, b, c):
    k = float(k)
    if k == distance[i][j]:
        continue

    for s in range(1, N + 1):
        if i == s or j == s:
            continue

        if k + distance[j][s] == distance[i][s]:
            continue

        if k + distance[i][s] == distance[j][s]:
            continue

        answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
read = sys.stdin.read

N, M, *abc = map(int, read().split())
a, b, c = zip(*zip(*[iter(abc)] * 3))

graph = csr_matrix((c, (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False)

answer = 0

for i, j, k in zip(a, b, c):
    k = float(k)
    if k == int(distance[i][j]):
        continue

    for s in range(1, N + 1):
        if i == s or j == s:
            continue

        if k + distance[j][s] == distance[i][s]:
            continue

        if k + distance[i][s] == distance[j][s]:
            continue

        answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
read = sys.stdin.read

N, M, *abc = map(int, read().split())
a, b, c = zip(*zip(*[iter(abc)] * 3))

graph = csr_matrix((c, (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False)

answer = 0

for i, j, k in zip(a, b, c):
    if c == int(distance[i][j]):
        continue

    for s in range(1, N + 1):
        if i == s or j == s:
            continue

        if distance[i][j] + distance[j][s] == distance[i][s]:
            continue

        if distance[j][i] + distance[i][s] == distance[j][s]:
            continue

        answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
read = sys.stdin.read

N, M, *abc = map(int, read().split())
a, b, c = zip(*zip(*[iter(abc)] * 3))

graph = csr_matrix((c, (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False)

answer = 0

for i, j in zip(a, b):
    for s in range(1, N + 1):
        if distance[i][j] + distance[j][s] == distance[i][s]:
            continue

        if distance[j][i] + distance[i][s] == distance[j][s]:
            continue

        answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:

def dijkstra(graph,weight,s,N):
    distance=[1e10 for i in range(N)]
    distance[s]=0
    unvisited=[i for i in range(N)]
    while len(unvisited)>0:
        unvisited.sort(key=lambda x:distance[x])
        v=unvisited.pop(0)
        for w in graph[v]:
            if distance[w]>distance[v]+weight[(v,w)]:
                distance[w] = distance[v] + weight[(v, w)]
    return distance

def e_check(e,d_list,weight,N):
    for i in range(N):
        for j in range(N):
            if e[0]!=i and e[1]!=j and d_list[e[0]][i]+weight[(i,j)]==d_list[j][e[1]]:
                return True
    return False

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    graph={i:[] for i in range(N)}
    weight={(i,j):1e10 for i in range(N) for j in range(N)}
    E=[]

    for i in range(M):
        a,b,c = list(map(int, input().split()))
        E.append((a-1,b-1))
        E.append((b-1,a-1))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        weight[(a-1,b-1)]=c
        weight[(b-1,a-1)]=c
    d_list={i:dijkstra(graph,weight,i,N) for i in range(N)}
    removed=[]
    for e in E:
        if not e_check(e,d_list,weight,N):
            removed.append(e)
    E=set(E)
    removed=set(removed)
    ans=E.difference(removed)
    print(len(ans)//2)

Submission status: Wrong Answer

Solution code:


def dijkstra(graph,weight,s,N):
    distance=[1e10 for i in range(N)]
    distance[s]=0
    unvisited=[i for i in range(N)]
    while len(unvisited)>0:
        unvisited.sort(key=lambda x:distance[x])
        v=unvisited.pop(0)
        for w in graph[v]:
            if distance[w]>distance[v]+weight[(v,w)]:
                distance[w] = distance[v] + weight[(v, w)]
    return distance

def e_check(e,d_list,weight,N):
    for i in range(N):
        for j in range(N):
            if e[0]!=i and e[1]!=j and d_list[e[0]][i]+weight[(i,j)]==d_list[j][e[1]]:
                return True
    return False


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    graph={i:[] for i in range(N)}
    weight={(i,j):1e10 for i in range(N) for j in range(N)}
    E=[]

    for i in range(M):
        a,b,c = list(map(int, input().split()))
        E.append((a-1,b-1))
        E.append((b-1,a-1))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        weight[(a-1,b-1)]=c
        weight[(b-1,a-1)]=c
    d_list={i:dijkstra(graph,weight,i,N) for i in range(N)}
    removed=[]
    for e in E:
        if not e_check(e,d_list,weight,N):
            removed.append(e)

    E=set(E)
    removed=set(removed)
    ans=E.difference(removed)
    print(len(ans)//2)

Submission status: Wrong Answer

Solution code:
class quickfind:
  def __init__(self, n):
    self.i2g = [ i for i in range(n) ]
    self.g2i = [ [i] for i in range(n) ]
  
  def size(self, x):
    return len(self.g2i[self.i2g[x]])
  
  def parent(self, x):
    return self.i2g[x]
  
  def merge(self, l, r):
    l = self.parent(l)
    r = self.parent(r)
    if l == r:
      return False
    if self.size(l) < self.size(r):
      l, r = r, l
    for v in self.g2i[r]:
      self.i2g[v] = l
      self.g2i[l].append(v)
    self.g2i[r] = []
    return True
  
N, M = map(int, input().split())
E = []
for i in range(M):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  E.append((a, b, c))
E = sorted(E, key=lambda t:t[2])
qf = quickfind(N)
ans = 0
for id, e in enumerate(E):
  if qf.size(a) == N:
    ans = M - id
    break
  qf.merge(e[0], e[1])
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

n,m = map(int,input().split())
edges = [[int(x) for x in input().split()] for i in range(m)]
graph = [[False]*n for i in range(n)]
for a, b, c in edges :
    graph[a-1][b-1] = c

graph = csgraph_from_dense(graph)
dist = dijkstra(graph, directed=False).astype(int)

used = [0]*m
for s in range(n-1) :
    for t in range(s+1, n) :
        for i in range(len(edges)) :
            a, b, c = edges[i]
            a -= 1
            b -= 1
            if dist[s][a] + c + dist[b][t] == dist[s][t] :
                used[i] = 1
ans = m - sum(used)
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra

n,m = map(int,input().split())
edges = [[int(x) for x in input().split()] for i in range(m)]
graph = [[0]*n for i in range(n)]
for a, b, c in edges :
    graph[a-1][b-1] = c

#graph = csgraph_from_dense(graph)
dist = dijkstra(graph, directed=True).astype(int)

used = [0]*m
for s in range(n-1) :
    for t in range(s+1, n) :
        for i in range(len(edges)) :
            a, b, c = edges[i]
            a -= 1
            b -= 1
            if dist[s][a] + c + dist[b][t] == dist[s][t] :
                used[i] = 1
ans = m - sum(used)
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

n,m = map(int,input().split())
edges = [[int(x) for x in input().split()] for i in range(m)]
graph = [[0]*n for i in range(n)]
for a, b, c in edges :
    graph[a-1][b-1] = c

graph = csgraph_from_dense(graph)
dist = dijkstra(graph, directed=False).astype(int)

used = [0]*m
for s in range(n-1) :
    for t in range(s+1, n) :
        for i in range(len(edges)) :
            a, b, c = edges[i]
            a -= 1
            b -= 1
            if dist[s][a] + c + dist[b][t] == dist[s][t] :
                used[i] = 1
ans = m - sum(used)
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 1001

def dijkstra(s,N,M,cost,ans):
  d = [INF] * N
  used = [False] * N
  d[s] = 0
  prvv = [[] for i in range(N)]
  while True:
    v = -1
    for i in range(N):
      if (not used[i]) and (v == -1): v = i
      elif (not used[i] and d[i] < d[v]): v = i
    if v == -1: break
    used[v] = True
  
    min_e = None
    for j in range(N):
      if d[j] > d[v]+cost[v][j]:
        d[j] = d[v]+cost[v][j]
        prvv[j] = [v]
      elif d[j] == d[v]+cost[v][j]:
        d[j] = d[v]+cost[v][j]
        prvv[j].append(v)
  for i, vs in enumerate(prvv):
    for v in vs:
      ans.add(tuple(sorted([v,i])))

  return prvv

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

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


ans =set([])
for i in range(N):
  dijkstra(i,N,M,cost,ans)
print(M-len(ans))
#print(ans)

Submission status: Wrong Answer

Solution code:
INF = 1001

def dijkstra(s,N,M,cost,ans):
  d = [INF] * N
  used = [False] * N
  d[s] = 0
  prvv = [i for i in range(N)]
  while True:
    v = -1
    for i in range(N):
      if (not used[i]) and (v == -1): v = i
      elif (not used[i] and d[i] < d[v]): v = i
    if v == -1: break
    used[v] = True
  
    min_e = None
    for j in range(N):
      if d[j] >= d[v]+cost[v][j]:
        d[j] = d[v]+cost[v][j]
        prvv[j] = v
  for i, v in enumerate(prvv):
    if i != v: ans.add(tuple(sorted([v,i])))

  return prvv

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

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


ans =set([])
for i in range(N):
  dijkstra(i,N,M,cost,ans)
print(M-len(ans))
#print(ans)

Submission status: Wrong Answer

Solution code:
# ワーシャル-フロイド法
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n,w = map(int,input().split()) #n:頂点数　w:辺の数
d = [[float('inf') for i in range(n+1)] for i in range(n+1)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
W = []
for i in range(w):
    x,y,z = map(int,input().split())
    W.append((x,y,z))
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
a = 1
for i in range(w):
    x,y,z = W[i][0],W[i][1],W[i][2]
    if d[x][y] < z:
        a += 1
ans = w - a
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict, OrderedDict
from math import factorial
from fractions import Fraction
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, e = MAP()    
G = [[]for i in range(n)]   
G_table = [[0]*n for i in range(n)]
    
for i in range(e):
    fr, to, w = MAP()
    G_table[fr-1][to-1] = 1
    G_table[to-1][fr-1] = 1
    G[fr-1].append((w, to -1))
    G[to-1].append((w, fr -1))

def djkstra(s,G):
    visited = [False]*n    
    d = [INF]*n
    former = [INF]*n
    que = []
    heapq.heapify(que)
    heapq.heappush(que, (0,s,-1))

    while(len(que)>0):
        vs = heapq.heappop(que)
        distance = vs[0]
        vertex = vs[1]
        f = vs[2]
        if visited[vertex]:
            continue
        d[vertex] = distance
        visited[vertex] = True
        former[vertex] = f
        for Gs in G[vertex]:
            if d[Gs[1]] <= distance+Gs[0]:
                continue
            heapq.heappush(que,(distance+Gs[0], Gs[1], vertex))
    
    return d,former

res = 0

for k in range(n):
    d, former = djkstra(k,G)
    for i in range(n):
        if former[i] != -1:
            G_table[i][former[i]] = 0
            G_table[former[i]][i] = 0

for i in range(n):
    for j in range(n):
        if G_table[i][j] == 1:
            res += 1

print(res//2)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

inf = 1000 * 1000 + 10


def dijkstra_need_edge(s):
    used = [False] * n
    used[s] = True

    dist = [inf] * n
    dist[s] = 0

    hq = []
    for e in g[s]:
        heappush(hq, e)

    need_edge = set()
    while hq:
        w, t, ind = heappop(hq)
        if used[t]: continue
        need_edge.add(ind)
        used[t] = True
        dist[t] = w
        add_es = map(lambda x: (dist[t] + x[0], x[1], x[2]), g[t])
        for e in add_es:
            heappush(hq, e)
    return need_edge


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

g = tuple(set() for _ in range(n))
for ind in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a].add((c, b, ind))
    g[b].add((c, a, ind))

st = set()
for v in range(n):
    st |= dijkstra_need_edge(v)
print(m - len(st))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

inf = 1000 * 1000 + 10

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

g = tuple([inf] * n for _ in range(n))
e = set()
for ind in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((ind, a, b))

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

# print(g_ref)

need = set()
for ind, a, b in e:
    g_copy = deepcopy(g)
    g_copy[a][b] = inf
    g_copy[b][a] = inf
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g_copy[i][j] = min(g_copy[i][j], g_copy[i][k] + g_copy[k][j])
    # print(g_copy)
    if any(g_ref[i][j] != g_copy[i][j] for i in range(n) for j in range(n)):
        need.add(ind)

print(m - len(need))

# きっとTLE

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra

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

graph = [[0 if i == j else float("inf") for i in range(N)] for j in range(N)]
for i in range(M):
    ai, bi, ci = map(int, input().split())
    graph[ai - 1][bi - 1] = ci
    graph[bi - 1][ai - 1] = ci

dist1 = dijkstra(graph, directed=False)
print(graph)
print(dist1)

cnt = 0
for i in range(N):
    for j in range(N):
        used = False
        if i > j:
            continue
        for k in range(N):
            if graph[i][j] + dist1[k][i] == dist1[i][j]:
                used = True
                break
        if not used and graph[i][j] != float("inf"):
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra

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

graph = [[0 if i == j else float("inf") for i in range(N)] for j in range(N)]
for i in range(M):
    ai, bi, ci = map(int, input().split())
    graph[ai - 1][bi - 1] = ci
    graph[bi - 1][ai - 1] = ci

dist1 = dijkstra(graph, directed=False)
print(graph)
print(dist1)

cnt = 0
for i in range(N):
    for j in range(N):
        used = False
        if i > j:
            continue
        for k in range(N):
            if graph[i][j] + dist1[k][i] == dist1[i][j]:
                used = True
                break
        if not used and graph[i][j] == "inf":
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n, m = map(lambda x: int(x), input().split())
a = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
    a[i], b[i], c[i] = map(lambda x: int(x), input().split())

def dijkstra(graph, start, end):
    print('start:{}, end:{}'.format(start, end))
    cost = [1000*100 for _ in range(n+1)]
    fixed = [False for _ in range(n+1)]
    cost[start] = 0
    fixed[start] = True
    tmp_sta = start
    while True:
        tmp_min = 1000*100
        for i in graph[tmp_sta]:
            cost[i[0]] = min(cost[i[0]], cost[tmp_sta]+i[1])
        for i in range(1, n+1):
            if tmp_min > cost[i] and fixed[i] == False:
                tmp_min = cost[i]
                tmp_sta = i
        if tmp_sta == end:
            return tmp_min
        else:
            fixed[tmp_sta] = True
    
graph = {}
for i in range(1, n+1):
    graph[i] = []
for i in range(m):
    graph[a[i]].append((b[i], c[i]))
    graph[b[i]].append((a[i], c[i]))
print(graph)
    
ans = 0
for i in range(m):
    if c[i] > dijkstra(graph, a[i], b[i]):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# Python program for Dijkstra's 
# single source shortest 
# path algorithm. The program 
# is for adjacency matrix 
ans=[]
p=[]
# representation of the graph 

from collections import defaultdict 
pa=[]
#Class to represent a graph 
class Graph: 

	# A utility function to find the 
	# vertex with minimum dist value, from 
	# the set of vertices still in queue 
	def minDistance(self,dist,queue): 
		# Initialize min value and min_index as -1 
		minimum = float("Inf") 
		min_index = -1
		
		# from the dist array,pick one which 
		# has min value and is till in queue 
		for i in range(len(dist)): 
			if dist[i] < minimum and i in queue: 
				minimum = dist[i] 
				min_index = i 
		return min_index 


	# Function to print shortest path 
	# from source to j 
	# using parent array 
	def printPath(self, parent, j): 
		global p
		global pa 
		#Base Case : If j is source 
		if parent[j] == -1 : 
		#	print j, 
			p.append(j)
			pa.append(p)
			return
		self.printPath(parent , parent[j]) 
		#print j, 
		p.append(j)
        
	# A utility function to print 
	# the constructed distance 
	# array 
	def printSolution(self, dist, parent): 
		src = 0
		global p
	#	print("Vertex \t\tDistance from Source\tPath") 
		for i in range(1, len(dist)): 
		#	print("\n%d --> %d \t\t%d \t\t\t\t\t" % (src, i, dist[i])), 
			p=[]
			self.printPath(parent,i) 
			#print(p,'fun')
		#	pa.append(p)

	'''Function that implements Dijkstra's single source shortest path 
	algorithm for a graph represented using adjacency matrix 
	representation'''
	def dijkstra(self, graph, src): 

		row = len(graph) 
		col = len(graph[0]) 

		# The output array. dist[i] will hold 
		# the shortest distance from src to i 
		# Initialize all distances as INFINITE 
		dist = [float("Inf")] * row 

		#Parent array to store 
		# shortest path tree 
		parent = [-1] * row 

		# Distance of source vertex 
		# from itself is always 0 
		dist[src] = 0
	
		# Add all vertices in queue 
		queue = [] 
		for i in range(row): 
			queue.append(i) 
			
		#Find shortest path for all vertices 
		while queue: 

			# Pick the minimum dist vertex 
			# from the set of vertices 
			# still in queue 
			u = self.minDistance(dist,queue) 

			# remove min element	 
			queue.remove(u) 

			# Update dist value and parent 
			# index of the adjacent vertices of 
			# the picked vertex. Consider only 
			# those vertices which are still in 
			# queue 
			for i in range(col): 
				'''Update dist[i] only if it is in queue, there is 
				an edge from u to i, and total weight of path from 
				src to i through u is smaller than current value of 
				dist[i]'''
				if graph[u][i] and i in queue: 
					if dist[u] + graph[u][i] < dist[i]: 
						dist[i] = dist[u] + graph[u][i] 
						parent[i] = u 


		# print the constructed distance array 
		self.printSolution(dist,parent) 

g= Graph() 
edge=[]
n,m=map(int,raw_input().split())
graph=[[0 for j in range(n)]for i in range(n)]
for i in range(m):
    a,b,c=map(int,raw_input().split())
    a,b=min(a,b),max(a,b)
    edge.append([a-1,b-1])
    graph[a-1][b-1]=c 
    graph[b-1][a-1]=c 

		

ans={}
for i in range(n):
    p=[]
    g.dijkstra(graph,i) 
   # print(p)
    for i in range(len(p)-1):
        a,b=p[i],p[i+1]
        a,b=min(a,b),max(a,b)
        ans[(a,b)]=1 
#print(ans)
#print(pa)
# This code is contributed by Neelam Yadav 
cnt=0 
for i in edge: 
    if ans.get((i[0],i[1]),-1)!=-1:
        cnt+=1 
print(m-cnt)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
INF = 10**5
D=[[INF]*N for _ in range(N)]
for i in range(N):
  D[i][i]=0
path=[]
for i in range(M):
  a,b,c = map(int,input().split())
  D[a-1][b-1]=c
  D[b-1][a-1]=c
  path.append([a-1,b-1,c])
for k in range(N):
  for i in range(N-1):
    for j in range(i+1,N):
      D[i][j]=min(D[i][j],D[i][k]+D[j][k])
      D[j][i]=D[i][j]
ans=0
for a,b,c in path:
  if D[a][b]>c:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

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

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

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


#nは頂点、mは辺、a、bは頂点、cはaとbの距離


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])


res = 0
for i in range(m):
	if c[i] > dist[a[i]-1][b[i]-1]:
		res += 1

print (res)

Submission status: Wrong Answer

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

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

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

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


#nは頂点、mは辺、a、bは頂点、cはaとbの距離


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])


res = 0
for i in range(m):
	if c[i] > dist[a[i]-1][b[i]-1]:
		res += 1

print (res)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
cs = [[float('inf')] * n for _ in range(n)]
ns = [[0] * n for _ in range(n)]
for i in range(n):
    cs[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    cs[a - 1][b - 1] = cs[b - 1][a - 1] = c
    ns[a - 1][b - 1] = b - 1
    ns[b - 1][a - 1] = a - 1
for i in range(n):
    for j in range(n):
        for k in range(n):
            s = cs[i][k] + cs[k][j]
            if s < cs[i][j]:
                cs[i][j] = s
                ns[i][j] = ns[i][k]
used = []
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        path = [i]
        while path[-1] != j:
            s = path[-1]
            t = ns[s][j]
            path.append(t)
            used.append(tuple(sorted([s, t])))
print(m - len(set(used)))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]
print(m - n + 1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from copy import deepcopy

def main():
    N,M = map(int,input().split())
    INF = 10**6
    l = [[INF for _ in range(N)] for _ in range(N)]
    X = [list(map(int,input().split())) for _ in range(M)]
    for i in range(M):
        l[X[i][0]-1][X[i][1]-1] = X[i][2]
        l[X[i][1]-1][X[i][0]-1] = X[i][2]
    d = deepcopy(l)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                d[i][k] = min(d[i][k],d[i][j]+d[j][k])

    count = 0
    for i in range(N):
        for j in range(N):
            if l[i][j] == d[i][j]:
                count += 1

    print(M-count//2)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    D = [[float("inf")]*(N+1) for i in range(N+1)]
    ID = [[float("inf")]*(N+1) for i in range(N+1)]
    NEX = [[set() for j in range(N+1)] for i in range(N+1)]
    
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = c
        D[b][a] = c
        ID[a][b] = i
        ID[b][a] = i
        NEX[a][b].add(b)
        NEX[b][a].add(a)
        
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                if D[i][j] > D[i][k]+D[k][j]:
                    D[i][j] = D[i][k]+D[k][j]
                    NEX[i][j] = NEX[i][k]
                elif D[i][j] == D[i][k]+D[k][j] and i!=j and j!=k and k!=i and D[i][j]<float("inf"):
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
    S = set()
    for i in range(1,N+1):
        for j in range(1,N+1):
            if i != j:
                for l in NEX[i][j]:
                    S.add(ID[i][l])
                #print(i,j,D[i][j],NEX[i][j])
    #print(S)            
    print(M-len(S))
            
    
    
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    D = [[[float("inf"),float("inf"),[]]]*(N+2) for i in range(N+2)]
    
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = [c,i,[i]]
        D[b][a] = [c,i,[i]]
        
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                if D[i][j][0] > D[i][k][0]+D[k][j][0]:
                    D[i][j][0] = D[i][k][0]+D[k][j][0]
                    D[i][j][2] = D[i][k][2]+D[k][j][2]
    S = set()
    for i in range(1,N+1):
        for j in range(1,N+1):
            if i != j:
                for k in D[i][j][2]:
                    S.add(k)
                
    print(M-len(S))
            
    
    
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    D = [[[float("inf"),float("inf")]]*(N+2) for i in range(N+2)]
    NEX = [[set()]*(N+2) for i in range(N+2)]
    
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = [c,i]
        D[b][a] = [c,i]
        NEX[a][b] = {b}
        NEX[b][a] = {a}
        
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                if D[i][j][0] > D[i][k][0]+D[k][j][0]:
                    D[i][j][0] = D[i][k][0]+D[k][j][0]
                    NEX[i][j] = NEX[i][k]
                if D[i][j][0] == D[i][k][0]+D[k][j][0]:
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
    S = set()
    T = set()
    for i in range(1,N+1):
        for j in range(1,N+1):
            #print(i,j,D[i][j][2])
            if i!=j:
                for k in NEX[i][j]:
                    T.add(D[i][k][1])
                
    #print(M-len(S))
    print(M-len(T))
            
    
    
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    D = [[[float("inf"),float("inf"),[]]]*(N+2) for i in range(N+2)]
    NEX = [[set()]*(N+2) for i in range(N+2)]
    
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = [c,i,[i]]
        D[b][a] = [c,i,[i]]
        NEX[a][b] = {b}
        NEX[b][a] = {a}
        
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                if D[i][j][0] > D[i][k][0]+D[k][j][0]:
                    D[i][j][0] > D[i][k][0]+D[k][j][0]
                    D[i][j][2] = D[i][k][2]+D[k][j][2]
                    NEX[i][j] = NEX[i][k]
                if D[i][j][0] == D[i][k][0]+D[k][j][0]:
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
    S = set()
    T = set()
    for i in range(1,N+1):
        for j in range(1,N+1):
            #print(i,j,D[i][j][2])
            if i!=j:
                for k in NEX[i][j]:
                    T.add(D[i][k][1])
                for k in D[i][j][2]:
                    S.add(k)
                
    #print(M-len(S))
    print(M-len(T))
            
    
    
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    D = [[[float("inf"),float("inf"),[]]]*(N+2) for i in range(N+2)]
    NEX = [[set()]*(N+2) for i in range(N+2)]
    
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = [c,i,[i]]
        D[b][a] = [c,i,[i]]
        NEX[a][b] = {b}
        NEX[b][a] = {a}
        
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                if D[i][j][0] > D[i][k][0]+D[k][j][0]:
                    D[i][j][0] > D[i][k][0]+D[k][j][0]
                    D[i][j][2] = D[i][k][2]+D[k][j][2]
                    NEX[i][j] = NEX[i][k]
                if D[i][j][0] == D[i][k][0]+D[k][j][0]:
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
    S = set()
    T = set()
    for i in range(1,N+1):
        for j in range(1,N+1):
            #print(i,j,D[i][j][2])
            if i!=j:
                for k in NEX[i][j]:
                    T.add(k)
                for k in D[i][j][2]:
                    S.add(k)
                
    #print(M-len(S))
    print(M-len(T))
            
    
    
main()