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:
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]
                elif D[i][j][0] == D[i][k][0]+D[k][j][0] and D[i][j][0]<float("inf"):
                    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(i+1,N+1):
            #print(i,j,D[i][j][2])
            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)]
    
    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]
                elif 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(i+1,N+1):
            #print(i,j,D[i][j][2])
            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)]
    
    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):
            for k in D[i][j][2]:
                S.add(k)
                
    print(M-len(S))
            
    
    
main()

Submission status: Wrong Answer

Solution code:
from queue import Queue
import copy

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

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

T=[[1000]*N for i in range(N)]
U=[[[]for i in range(N)] for i in range(N)]

for i in range(N):
	q=Queue()
	seen=[False]*N
	q.put([i,0,[i]])
	seen[i]=True
	while not(q.empty()):
		t,d,u=q.get()
		seen[t]=True
		if T[i][t]>d:
			T[i][t]=d
			U[i][t]=u
			T[t][i]=d
			U[t][i]=u
		for x,c in G[t]:
			if seen[x]==False:
				l=copy.copy(u)
				l.append(x)
				q.put([x,d+c,l])

A=[[False]*N for i in range(N)]
for i in range(N-1):
	for j in range(i+1,N):
		u=U[i][j]
		for k in range(len(u)-1):
			a,b=min(u[k],u[k+1]),max(u[k],u[k+1])
			A[a][b]=True

ans=M
for i in range(N-1):
	for j in range(i+1,N):
		ans-=int(A[i][j])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
input = sys.stdin.readline

class Edge:
    def __init__(self, id, node1=-1, node2=-1, cost=-1):
        self.id = id
        self.node1 = node1
        self.node2 = node2
        self.cost = cost
    
    def next(self, num):
        if num == self.node1:
            return self.node2
        elif num == self.node2:
            return self.node1
        else:
            return False

def main():
    N, M = map(int, input().split())

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

    ans = set([i for i in range(M)])
    for start in range(N):
        q = []
        check = [False] * N
        heapq.heappush(q, (0, start, None))
        used_edge = set()
        while len(q) > 0:
            cost, node, pre_edge = heapq.heappop(q)
            if check[node]:
                continue
            check[node] = True
            if pre_edge != None:
                used_edge.add(pre_edge)
            for edge in edges[node]:
                next_node = edge.next(node)
                if not check[next_node]:
                    heapq.heappush(q, (cost + edge.cost, next_node, edge.id))
        ans -= used_edge
    print(len(ans))




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
inf = float("inf")
N, M = map(int, input().split())
e = set()
n = [[[j] for j in range(N)] for _ in range(N)]
d = [[inf] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    e.add((a-1, b-1))
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]:
                d[i][j] = d[i][k] + d[k][j]
                n[i][j] = [k]
            if d[i][j] == d[i][k] + d[k][j]:
                n[i][j].append(k)
for i in range(N-1):
    for j in range(i+1, N):
        for k in n[i][j]:
            e.discard((i, k))
            e.discard((k, i))
print(len(e))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        A[a][b]=c
        A[b][a]=c
    from copy import deepcopy
    C=deepcopy(A)
    # Warshall-Floyd
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])
    # count
    B=set()
    for s,i,j in product(range(n),repeat=3):
        if (C[i][j]!=INF) and (s!=i) and (s!=j) and (A[s][i]+C[i][j]==A[s][j]):
            B.add((min(i,j),max(i,j)))
    print(m-len(B))

resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        A[a][b]=c
        A[b][a]=c
    from copy import deepcopy
    C=deepcopy(A)
    # Warshall-Floyd
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])
    # count
    B=set()
    for s,i,j in product(range(n),repeat=3):
        if (C[i][j]!=INF) and (A[s][i]+C[i][j]==A[s][j]):
            B.add((min(i,j),max(i,j)))

    print(m-len(B))


resolve()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int,input().split())
    prm = [[1001 for _ in range(N)] for _ in range(N)]
    d = [tuple(map(int,input().split())) for _ in range(M)]
    min_path = 1001 * N
    for a,b,c in d:
        prm[a-1][b-1] = c
    for i in range(N):
        for j in range(N):
            if i == j:
                prm[i][j] = 0
                continue
            if prm[i][j] < prm[j][i]:
                prm[j][i] = prm[i][j]
            else:
                prm[i][j] = prm[j][i]
        tmp =sum(prm[i])
        if tmp < min_path:
            min_path = tmp
    res = 0
    for a,b,c in d:
        if min_path < c:
            res +=1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

dist=[[float('inf')]*N for _ in range(N)]

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

for i in range(M):
  a=abc[i][0]-1
  b=abc[i][1]-1
  c=abc[i][2]-1
  dist[a][b]=c
  dist[b][a]=c

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

A = []
B = []
C = []

inf = 1*10**-7
max_n = 110
G = [[inf] * max_n for i in range(max_n)]
for i in range(N):
    G[i][i] = 0


for i in range(M):
    a, b, c = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)
    G[A[i]][B[i]] = C[i]
    G[B[i]][A[i]] = C[i]

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

ans = 0
for i in range(M):
    if (G[A[i]][B[i]] < C[i]):
        ans += 1

# print(G)


print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

A = []
B = []
C = []

inf = 1*10**-7

G = [[inf] * N for i in range(N)]
for i in range(N):
    G[i][i] = 0


for i in range(M):
    a, b, c = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)
    G[A[i]][B[i]] = C[i]
    G[B[i]][A[i]] = C[i]

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

ans = 0
for i in range(M):
    if (G[A[i]][B[i]] < C[i]):
        ans += 1

# print(G)


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy
input = sys.stdin.readline
n,m=map(int,input().split())
d=[[100000]*n for _ in range(n)]
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
  a0,b0,c0=map(int,input().split())
  a[i]=a0-1
  b[i]=b0-1
  c[i]=c0
  d[a0-1][b0-1]=c0
  d[b0-1][a0-1]=c0
for i in range(n):
  d[i][i]=0
d2=deepcopy(d)
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])
count=0
for i in range(n):
  for j in range(i):
    if d[i][j]!=d2[i][j]:
      count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy
input = sys.stdin.readline
n,m=map(int,input().split())
d=[[100000]*n for _ in range(n)]
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
  a0,b0,c0=map(int,input().split())
  a[i]=a0-1
  b[i]=b0-1
  c[i]=c0
  d[a0-1][b0-1]=c0
  d[b0-1][a0-1]=c0
for i in range(n):
  d[i][i]=0
d2=deepcopy(d)
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])
count=0
for i in range(n):
  for j in range(i):
    if d[i][j]!=d[i][j]:
      count+=1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve(graph, edges, n, start_idx):
  flg = [False for _ in range(n)] #未検索のノードはFlase
  flg[start_idx] = True
  
  cost = [float('inf') for _ in range(n)]
  cost[start_idx] = 0
  
  prv_edges = [[] for _ in range(n)]
  
  prv_node = start_idx
  tmp_idx = prv_node
  while not all(flg):
    prv_node = tmp_idx
    flg[prv_node] = True
    for node, dis in graph[prv_node]: 
      tmp_cost = cost[node] 
      tmp_dis = dis + cost[prv_node]
      if tmp_cost >= tmp_dis:
        cost[node] = tmp_dis
        
        tmp_edge = sorted([prv_node, node])
        if tmp_edge in edges:
          edges.remove(tmp_edge)
        for prv_edge in prv_edges[node]:
          if prv_edge not in edges:
            edges.append(prv_edge)

      if tmp_cost > tmp_dis:
        prv_edges[node] = [tmp_edge]
      elif tmp_cost == tmp_dis:
        prv_edges[node].append(tmp_edge)
    
    min_cost = float('inf')
    tmp_idx = -1
    for i in range(n):
      if flg[i] is False and min_cost > cost[i]:
        min_cost = cost[i]
        tmp_idx = i
  return edges

n, m = map(int, input().split())
graph = defaultdict(list)
edges = []

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

for i in range(2,3):
  edges = solve(graph, edges, n, i)
print(len(edges))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve(graph, edges, n, start_idx):
  flg = [False for _ in range(n)] #未検索のノードはFlase
  flg[start_idx] = True
  
  cost = [float('inf') for _ in range(n)]
  cost[start_idx] = 0
  
  prv_edges = [[] for _ in range(n)]
  
  prv_node = start_idx  
  while not all(flg):
    for node, dis in graph[prv_node]:
      tmp_cost = cost[node] 
      tmp_dis = dis + cost[prv_node]
      if tmp_cost >= tmp_dis:
        cost[node] = tmp_dis
        
        tmp_edge = sorted([prv_node, node])
        if tmp_edge in edges:
          edges.remove(tmp_edge)
        for prv_edge in prv_edges[node]:
          if prv_edges[node] not in edges:
            edges.append(prv_edge)

      if tmp_cost > tmp_dis:
        prv_edges[node] = [tmp_edge]
      elif tmp_cost == tmp_dis:
        prv_edges[node].append(tmp_edge)
    
    min_cost = float('inf')
    tmp_idx = -1
    for i in range(n):
      if flg[i] is False and min_cost > cost[i]:
        min_cost = cost[i]
        tmp_idx = i
    prv_node = tmp_idx
    flg[prv_node] = True
    #print(start_idx, prv_node, cost, edges, prv_edges)
  return edges

n, m = map(int, input().split())
graph = defaultdict(list)
edges = []

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

for i in range(n):
  edges = solve(graph, edges, n, i)
print(len(edges))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve(graph, edges, n, start_idx):
  flg = [False for _ in range(n)] #未検索のノードはFlase
  flg[start_idx] = True
  
  cost = [float('inf') for _ in range(n)]
  cost[start_idx] = 0
  
  prv_edges = [[] for _ in range(n)]
  
  prv_node = start_idx  
  while not all(flg):
    for node, dis in graph[prv_node]:
      if cost[node] >= dis + cost[prv_node]:
        cost[node] = dis + cost[prv_node]
        
        tmp_edge = sorted([prv_node, node])
        if tmp_edge in edges:
          edges.remove(tmp_edge)
        for prv_edge in prv_edges[node]:
          if prv_edges[node] not in edges:
            edges.append(prv_edge)
      if cost[node] > dis + cost[prv_node]:
        prv_edges[node] = [tmp_edge]
      elif cost[node] == dis + cost[prv_node]:
        prv_edges[node].append(tmp_edge)
    
    min_cost = float('inf')
    tmp_idx = -1
    for i in range(n):
      if flg[i] is False and min_cost > cost[i]:
        min_cost = cost[i]
        tmp_idx = i
    prv_node = tmp_idx
    flg[prv_node] = True
    #print(start_idx, prv_node, cost, edges, prv_edges)
  return edges

n, m = map(int, input().split())
graph = defaultdict(list)
edges = []

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

for i in range(n):
  edges = solve(graph, edges, n, i)
print(len(edges))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve(graph, edges, n, start_idx):
  flg = [False for _ in range(n)] #未検索のノードはFlase
  flg[start_idx] = True
  
  cost = [float('inf') for _ in range(n)]
  cost[start_idx] = 0
  
  prv_edges = [[] for _ in range(n)]
  
  prv_node = start_idx  
  while not all(flg):
    for node, dis in graph[prv_node]:
      if cost[node] >= dis + cost[prv_node]:
        cost[node] = dis + cost[prv_node]
        
        tmp_edge = sorted([prv_node, node])
        if tmp_edge in edges:
          edges.remove(tmp_edge)
        for prv_edge in prv_edges[node]:
          if prv_edges[node] not in edges:
            edges.append(prv_edge)
        prv_edges[node].append(tmp_edge)
    
    min_cost = float('inf')
    tmp_idx = -1
    for i in range(n):
      if flg[i] is False and min_cost > cost[i]:
        min_cost = cost[i]
        tmp_idx = i
    prv_node = tmp_idx
    flg[prv_node] = True
    #print(start_idx, prv_node, cost, edges, prv_edges)
  return edges

n, m = map(int, input().split())
graph = defaultdict(list)
edges = []

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

for i in range(n):
  edges = solve(graph, edges, n, i)
print(len(edges))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve(graph, edges, n, start_idx):
  flg = [False for _ in range(n)] #未検索のノードはFlase
  flg[start_idx] = True
  
  cost = [float('inf') for _ in range(n)]
  cost[start_idx] = 0
  
  prv_edges = [None for _ in range(n)]
  
  prv_node = start_idx  
  while not all(flg):
    for node, dis in graph[prv_node]:
      if cost[node] > dis + cost[prv_node]:
        cost[node] = dis + cost[prv_node]
        
        tmp_edge = sorted([prv_node, node])
        if tmp_edge in edges:
          edges.remove(tmp_edge)
        if prv_edges[node] is not None and prv_edges[node] not in edges:
          edges.append(prv_edges[node])
        prv_edges[node] = tmp_edge
    
    min_cost = float('inf')
    tmp_idx = -1
    for i in range(n):
      if flg[i] is False and min_cost > cost[i]:
        min_cost = cost[i]
        tmp_idx = i
    prv_node = tmp_idx
    flg[prv_node] = True
    #print(start_idx, prv_node, cost, edges, prv_edges)
  return edges

n, m = map(int, input().split())
graph = defaultdict(list)
edges = []

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

for i in range(n):
  edges = solve(graph, edges, n, i)
print(len(edges))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def solve(graph, edges, n, start_idx):
  flg = [False for _ in range(n)] #未検索のノードはFlase
  flg[start_idx] = True
  
  cost = [float('inf') for _ in range(n)]
  cost[start_idx] = 0
  
  prv_edges = [None for _ in range(n)]
  
  prv_node = start_idx  
  while not all(flg):
    for node, dis in graph[prv_node]:
      if cost[node] > dis:
        cost[node] = dis
        
        tmp_edge = sorted([prv_node, node])
        if tmp_edge in edges:
          edges.remove(tmp_edge)
        if prv_edges[node] is not None and prv_edges[node] not in edges:
          edges.append(prv_edges[node])
        prv_edges[node] = tmp_edge
    
    min_cost = float('inf')
    tmp_idx = -1
    for i in range(n):
      if flg[i] is False and min_cost > cost[i]:
        min_cost = cost[i]
        tmp_idx = i
    prv_node = tmp_idx
    flg[prv_node] = True
    #print(start_idx, prv_node, cost, edges, prv_edges)
  return edges

n, m = map(int, input().split())
graph = defaultdict(list)
edges = []

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

for i in range(n):
  edges = solve(graph, edges, n, i)
print(len(edges))

Submission status: Wrong Answer

Solution code:
import heapq,sys
input=sys.stdin.readline
INF=float('inf')
heappush=heapq.heappush
heappop=heapq.heappop

n,m=map(int,input().split())
graph=[[] for _ in range(n)]
minway=[]
bridges=[]
ans=0
for _ in range(m):
    a,b,c=map(int,input().split())
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))
    bridges.append((a-1,b-1,c))

def dijkstra(graph,n,start):
    Q=[]
    distance=[]
    dappend=distance.append
    for i in range(n):
        dappend([INF,i])
    distance[start][0]=0
    for j in distance:
        heappush(Q,j)
    while Q!=[]:
        q=heappop(Q)
        for v,vl in graph[q[1]]:
            alt=vl+q[0]
            if alt<distance[v][0]:
                distance[v][0]=alt
                heappush(Q,[alt,v])
    return distance

for k in range(n):
    minway.append(dijkstra(graph,n,k))

for l in bridges:
    flag=0
    x,y,z=l[0],l[1],l[2]
    for p in range(n):
        if p!=x and p!=y:
            if minway[p][x][0]+z==minway[p][y][0] or minway[p][y][0]+z==minway[p][x][0]:
                flag=1
    if flag==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq,sys
input=sys.stdin.readline
INF=float('inf')
heappush=heapq.heappush
heappop=heapq.heappop

n,m=map(int,input().split())
graph=[[] for _ in range(n)]
minway=[]
bridges=[]
ans=0
for _ in range(m):
    a,b,c=map(int,input().split())
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))
    bridges.append((a-1,b-1))

def dijkstra(graph,n,start):
    Q=[]
    distance=[]
    dappend=distance.append
    for i in range(n):
        dappend([INF,i])
    distance[start][0]=0
    for j in distance:
        heappush(Q,j)
    while Q!=[]:
        q=heappop(Q)
        for v,vl in graph[q[1]]:
            alt=vl+q[0]
            if alt<distance[v][0]:
                distance[v][0]=alt
                heappush(Q,[alt,v])
    return distance

for k in range(n):
    minway.append(dijkstra(graph,n,k))

for l in bridges:
    flag=0
    x,y=l[0],l[1]
    for p in graph[x]:
        if p!=y:
            if minway[x][p[0]][0]+minway[x][y][0]==minway[p[0]][y][0]:
                flag=1
    for q in graph[y]:
        if q!=x:
            if minway[x][y][0]+minway[y][q[0]][0]==minway[x][q[0]][0]:
                flag=1
    if flag==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

def WarshallFloyd(V: int, cost: "List[List[int]]"):
    """
    全ての頂点対の間の最短距離を求めます。
    ==============
    V: 頂点数
    cost: 隣接行列(辺が存在しない部分はINF)
    --------------
    cost: 最短距離の行列
    """
    INF = 1e18
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    INF = 1e18
    cost = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(M):
        cost[a[i] - 1][b[i] - 1] = c[i]
        cost[b[i] - 1][a[i] - 1] = c[i]
    cost = WarshallFloyd(N, cost)
    counter = 0
    for i in range(M):
        flag = False
        for j in range(N):
            if cost[j][a[i]-1] + c[i] == cost[j][b[i]-1]:
                flag = True
        if not flag:
            counter += 1
    print(counter)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

def WarshallFloyd(V: int, cost: "List[List[int]]"):
    """
    全ての頂点対の間の最短距離を求めます。
    ==============
    V: 頂点数
    cost: 隣接行列(辺が存在しない部分はINF)
    --------------
    cost: 最短距離の行列
    """
    INF = 1e18
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    INF = 1000000000000000000
    cost = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(M):
        cost[a[i] - 1][b[i] - 1] = c[i]
        cost[b[i] - 1][a[i] - 1] = c[i]
    cost = WarshallFloyd(N, cost)
    counter = 0
    for i in range(M):
        flag = False
        for j in range(N):
            if cost[j][a[i]-1] + cost[a[i]-1][b[i]-1] == cost[j][b[i]-1]:
                flag = True
        if not flag:
            counter += 1
    print(counter)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
n,k = map(int,input().split())
path = [[] for _ in range(n+1)]
mem = {}
rem_mem = set()
ans = []
for i in range(k):
    a,b,c = map(int,input().split())
    path[a].append(b)
    path[b].append(a)
    t = str(a)+'-'+str(b)
    mem[t] = c
    rem_mem.add(t)
    t = str(b) + '-' + str(a)
    mem[t] = c
def dfs(arr,node,end,cost):
    ar = arr[::]
    ar.append(node)
    for v in path[node]:
        if v not in arr:
            t = str(node)+'-'+str(v)
            if v == end:
                ans.append([cost+mem.get(t),ar+[v]])
            else:
                dfs(ar,v,end,cost+mem.get(t))
for i in range(1,n):
    ans =[]
    for j in range(i+1,n+1):
        dfs([],i,j,0)
        ans.sort()
        remove = ans[0][0]
        for _,v in ans:
            if _  == remove:
                for k in range(1,len(v)):
                    t = str(v[k-1])+'-'+str(v[k])
                    if t in rem_mem:
                        rem_mem.remove(t)
                    t = str(v[k])+'-'+str(v[k - 1])
                    if t in rem_mem:
                        rem_mem.remove(t)
print(len(rem_mem))

Submission status: Wrong Answer

Solution code:
def dijkstra(m, s, t):
    INF = 1e10
    D = [INF] * N
    D[s] = 0
    Q = [v for v in range(N)]

    while Q:
        d = INF
        v = None
        for x in Q:
            if D[x] <= d:
                d = D[x]
                v = x
        Q.remove(v)

        for u, w in enumerate(m[v]):
            if D[u] > D[v] + w:
                D[u] = D[v] + w
    return D[t] 

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

# N < 100
m = [[1e10]*N for i in range(N)]
E = [0] * M
for i in range(M):
    a, b, w = map(int, input().split())
    E[i] = a-1, b-1, w
    m[a-1][b-1] = w

count = 0
for a, b, w in E:
    d = dijkstra(m, a, b)
    if d < w:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
D = [[1000000]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
abcs = []
for i in range(M):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  abcs.append((a, b, c))
  D[a][b] = c
  D[b][a] = c
for a in range(N):
  for b in range(N):
    for k in range(N):
      D[a][b] = min(D[a][b], D[a][k]+D[k][b])
#print(D)
r = 0
for m in range(M):
  a, b, c = abcs[m]
  if c > D[a][b]:
    r += 1
print(r)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
D = [[float("inf")]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
abcs = []
for i in range(M):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  abcs.append((a, b, c))
  D[a][b] = c
  D[b][a] = c
for a in range(N):
  for b in range(N):
    for k in range(N):
      D[a][b] = min(D[a][b], D[a][k]+D[k][b])
#print(D)
r = 0
for m in range(M):
  a, b, c = abcs[m]
  if c > D[a][b]:
    r += 1
print(r)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
D = [[float("inf")]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
abcs = []
for i in range(M):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  abcs.append((a, b, c))
  D[a][b] = c
  D[b][a] = c
for a in range(N):
  for b in range(N):
    for k in range(N):
      D[a][b] = min(D[a][b], D[a][k]+D[k][b])
#print(D)
r = M
for m in range(M):
  a, b, c = abcs[m]
  ok = False
  for k in range(N):
    if c+D[b][k] == D[a][k]:
      ok = True
      break
  if ok:
    r -= 1
print(r)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
D = [[float("inf")]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
abcs = []
for i in range(M):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  abcs.append((a, b, c))
  D[a][b] = c
  D[b][a] = c
for a in range(N):
  for b in range(N):
    for k in range(N):
      D[a][b] = min(D[a][b], D[a][k]+D[k][b])
#print(D)
r = M
for m in range(M):
  a, b, c = abcs[m]
  for k in range(N):
    if c+D[b][k] == D[a][k]:
      r -= 1
      break
print(r)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
D = [[float("inf")]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
abcs = []
for i in range(M):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  abcs.append((a, b, c))
  D[a][b] = c
  D[b][a] = c
for a in range(N):
  for b in range(N):
    for k in range(N):
      D[a][b] = min(D[a][b], D[a][k]+D[k][b])
#print(D)
r = M
for m in range(M):
  a, b, c = abcs[m]
  for k in range(N):
    if c == D[b][k]-D[a][k]:
      r -= 1
      break
print(r)