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
import sys
import heapq
import copy

inf = float('inf')

def findedge(E, vv):
    e = (min(vv), max(vv))
    if e in E:
        return e
    return None


def dijkstra(V, E, L, s, g):
    D = [0 if v == s else inf for v in V]

    prev = [None for v in V]
    Q = [(d, v) for v, d in enumerate(D)]
    heapq.heapify(Q)

    while len(Q) > 0:
        u, du = heapq.heappop(Q)
        for v in V:
            e = findedge(E, (u, v))
            if not e:
                continue
            alt = du + L[e]
            if D[v] > alt:
                D[v] = alt
                prev[v] = u
                heapq.heappush(Q, (D[v], v))
    
    return D[g]


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    V = list(range(N))
    E = set()
    L = dict()
    
    for i in range(M):
        e = tuple(sorted([a[i], b[i]]))
        E.add(e)
        L[e] = c[i]

    count = 0
    E2 = copy.deepcopy(E)
    for e in E:
        alt = dijkstra(V, E2, L, e[0], e[1])
        if alt < L[e]:
            count += 1
            E2.remove(e)

    print(count)
    return


# Generated by 1.1.4 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))-1
        b[i] = int(next(tokens))-1
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
D = [[None] * N for _ in range(N)]
R = [[None] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for a, b, c in L:
    D[a - 1][b - 1] = c
    R[a - 1][b - 1] = [(a - 1, b - 1)]
    D[b - 1][a - 1] = c
    R[b - 1][a - 1] = [(b - 1, a - 1)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] is None or D[i][k] is None or D[k][j] is None:
                continue
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]
                if (i, j) in R[i][j]:
                    R[i][j] = []
                R[i][j].extend(R[i][k])
                R[i][j].extend(R[k][j])
R = set([r3 for r1 in R for r2 in r1 if r2 is not None for r3 in r2])
num = 0
for a, b, _ in L:
    if (a - 1, b - 1) not in R:
        num += 1
print(num)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
D = [[None] * N for _ in range(N)]
R = [[None] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for a, b, c in L:
    D[a - 1][b - 1] = c
    R[a - 1][b - 1] = [(a - 1, b - 1)]
    D[b - 1][a - 1] = c
    R[b - 1][a - 1] = [(b - 1, a - 1)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] is None or D[i][k] is None or D[k][j] is None:
                continue
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]
                R[i][j] = []
                R[i][j].extend(R[i][k])
                R[i][j].extend(R[k][j])
R = set([r3 for r1 in R for r2 in r1 if r2 is not None for r3 in r2])
num = 0
for a, b, _ in L:
    if (a - 1, b - 1) not in R:
        num += 1
print(num)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
D = [[None] * N for _ in range(N)]
R = [[None] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for a, b, c in L:
    D[a - 1][b - 1] = c
    R[a - 1][b - 1] = [(a - 1, b - 1)]
    D[b - 1][a - 1] = c
    R[b - 1][a - 1] = [(b - 1, a - 1)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] is None or D[i][k] is None or D[k][j] is None:
                continue
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]
                R[i][j] = [(i, k), (k, j)]
R = set([r3 for r1 in R for r2 in r1 if r2 is not None for r3 in r2])
num = 0
for a, b, _ in L:
    if (a - 1, b - 1) not in R:
        num += 1
print(num)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
abc = [LIST() for _ in range(M)]
# ワーシャルフロイド法
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = [[INF for i in range(N)] for i in range(N)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for x, y, z in abc:
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0 #自身のところに行くコストは０
# print(warshall_floyd(d))
count = 0
for a, b, c in abc:
	for i in range(N):
		if d[i][a-1] + c == d[a-1][b-1]:
			break
	else:
		count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
abc = [[int(item) for item in input().split()] for _ in range(m)]
edge = []
for a, b, c in abc:
    edge.append([a-1, b-1, c])
edge.sort(key=lambda x:x[2])

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * n
        self.rank = [0] * n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        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

count = 0
valid_v = 0
UF = UnionFind(n)
for a, b, c in edge:
    if not UF.same_check(a-1, b-1):
        UF.union(a-1, b-1)
        valid_v += 1
    else:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
abc = [[int(item) for item in input().split()] for _ in range(m)]
edge = []
for a, b, c in abc:
    edge.append([a-1, b-1, c])
edge.sort(key=lambda x:x[2])

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * n
        self.rank = [0] * n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        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

count = 0
valid_v = 0
UF = UnionFind(n)
for a, b, c in edge:
    if not UF.same_check(a, b):
        UF.union(a, b)
        valid_v += 1
    else:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
abc = [[int(item) for item in input().split()] for _ in range(m)]
edge = []
for a, b, c in abc:
    edge.append([a-1, b-1, c])
edge.sort(key=lambda x:x[2])

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.size = [1] * (n+1)
        self.rank = [0] * (n+1)
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        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

count = 0
UF = UnionFind(n)
for a, b, c in edge:
    if not UF.same_check(a, b):
        UF.union(a, b)
    else:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d,n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d
def solve():
  n,m = (int(i) for i in input().split())
 
  upper = 10**10
  dist = [[0 if x == i else upper for x in range(n)] for i in range(n)]
  edge_list = []
  for i in range(m):
    a, b, c = (int(i) for i in input().split())
    edge = [a, b, c]
    edge_list.append(edge)
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
  #print(edge_list)
  #print(dist)
  
  warshall_floyd(dist,n)
  #print(dist)
  
  
  ans = 0
  for edge in edge_list:
    a, b, c = edge

    if dist[a-1][b-1] != c:
        ans += 1
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d):
 
    n = len(d)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d
def solve():
  n,m = (int(i) for i in input().split())
 
  upper = 10**10
  dist = [[0 if x == i else upper for x in range(n)] for i in range(n)]
  edge_list = []
  for i in range(m):
    a, b, c = (int(i) for i in input().split())
    edge = [a, b, c]
    edge_list.append(edge)
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
  #print(edge_list)
  #print(dist)
  
  warshall_floyd(dist)
  #print(dist)
  
  
  ans = 0
  for edge in edge_list:
    a, b, c = edge
    #最短距離か
    if dist[a-1][b-1] < c:
        ans += 1
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d):
 
    n = len(d)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

def solve():
  n,m = (int(i) for i in input().split())
 
  upper = 10**10
  dist = [[0 if x == i else upper for x in range(n)] for i in range(n)]
  edge_list = []
  for i in range(m):
    a, b, c = (int(i) for i in input().split())
    edge = [a, b, c]
    edge_list.append(edge)
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
  #print(edge_list)
  #print(dist)
  
  warshall_floyd(dist)
  #print(dist)
  
  
  ans = 0
  for edge in edge_list:
    a, b, c = edge
    #最短距離か
    if dist[a-1][b-1] < c:
        ans += 1
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d):
    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]
    return d

n,w = map(int,input().split())
INF = 10**5
d = [[INF for i in range(n)] for i in range(n)]
e_list = []
for i in range(w):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
    e_list.append([x,y,z])
for i in range(n):
    d[i][i] = 0

warshall_floyd(d)
ans = w
for x,y,z in e_list:
    ok = False
    for i in range(n):
        for j in range(n):
            if d[i][x] + z == d[y][j]:
                ans -= 1
                ok = True
                break
        if ok:
            break
print(ans)

Submission status: Wrong Answer

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

MAX = 10*10
dist = [[0 if x == i else MAX for x in range(N)] for i in range(N)]
edge_list = []
for i in range(M):
    a, b, c = map(int, input().split())
    edge = [a, b, c]
    edge_list.append(edge)
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c

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

ans = 0
for edge in edge_list:
    a, b, c = edge
    if dist[a-1][b-1] < c:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def gen_graph(input_list):
    graph = {}

    for item in input_list:
        if not item[0] in graph:
            graph[item[0]] = {}
        if not item[1] in graph:
            graph[item[1]] = {}
        graph[item[0]][item[1]] = item[2]
        graph[item[1]][item[0]] = item[2]

    return graph


def get_lowest_cost_vertex(costs, processed):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


def get_best_routes(graph, start):
    costs = {}
    parents = {}
    processed = []

    costs[start] = 0
    parents[start] = None
    processed.append(start)

    for item in graph[start].keys():
        costs[item] = graph[start][item]
        parents[item] = start

    for item in graph.keys():
        if not (item in costs.keys() or item == start):
            costs[item] = float("inf")
            parents[item] = None

    node = get_lowest_cost_vertex(costs, processed)

    while node is not None:
        cost = costs[node]
        neighbors = graph[node]

        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        node = get_lowest_cost_vertex(costs, processed)

    routes = []
    for item in graph.keys():
        if item != start:
            route = []
            route.append(item)
            parent = parents[item]
            while 1:
                route.append(parent)
                if parent == start:
                    break
                parent = parents[parent]
            route.reverse()
            routes.append(route)
    return routes


def main(vertex_count, input_list):
    graph = gen_graph(input_list)

    routes = []
    for start in range(1, vertex_count+1):
        for route in get_best_routes(graph, start):
            routes.append(route)

    route_sides = []
    for route in routes:
        for i, vertex in enumerate(route):
            if i == len(route)-1:
                break
            route_side = [route[i], route[i+1]]
            route_side_sorted = sorted(route_side)
            if not route_side_sorted in route_sides:
                route_sides.append(route_side_sorted)

    sides = []
    for item in input_list:
        sides.append([item[0], item[1]])

    count = 0
    for side in sides:
        if not side in route_sides:
            count += 1

    return count


if __name__ == "__main__":
    input_1 = input()
    vertex_count, sides_count = list(map(int, input_1.split()))
    input_list = []
    for _ in range(sides_count):
        vertex_1, vertex_2, distance = list(map(int, input().split()))
        input_list.append((vertex_1, vertex_2, distance))
    print(main(vertex_count, input_list))

Submission status: Wrong Answer

Solution code:
def gen_graph(input_list):
    graph = {}

    for item in input_list:
        if not item[0] in graph:
            graph[item[0]] = {}
        if not item[1] in graph:
            graph[item[1]] = {}
        graph[item[0]][item[1]] = item[2]
        graph[item[1]][item[0]] = item[2]

    return graph


def get_lowest_cost_vertex(costs, processed):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


def get_best_routes(graph, start):
    costs = {}
    parents = {}
    processed = []

    costs[start] = 0
    parents[start] = None
    processed.append(start)

    for item in graph[start].keys():
        costs[item] = graph[start][item]
        parents[item] = start

    for item in graph.keys():
        if not (item in costs.keys() or item == start):
            costs[item] = float("inf")
            parents[item] = None

    node = get_lowest_cost_vertex(costs, processed)

    while node is not None:
        cost = costs[node]
        neighbors = graph[node]

        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        node = get_lowest_cost_vertex(costs, processed)

    routes = []
    for item in graph.keys():
        if item != start:
            route = []
            route.append(item)
            parent = parents[item]
            while 1:
                route.append(parent)
                if parent == start:
                    break
                parent = parents[parent]
            route.reverse()
            routes.append(route)
    return routes


def main(vertex_count, input_list):
    graph = gen_graph(input_list)

    routes = []
    for start in range(1, vertex_count+1):
        for route in get_best_routes(graph, start):
            routes.append(route)

    route_sides = []
    for route in routes:
        for i, vertex in enumerate(route):
            if i == len(route)-1:
                break
            route_side = [route[i], route[i+1]]
            route_side_sorted = sorted(route_side)
            if not route_side_sorted in route_sides:
                route_sides.append(route_side_sorted)

    print(route_sides)
    sides = []
    for item in input_list:
        sides.append([item[0], item[1]])

    count = 0
    for side in sides:
        if not side in route_sides:
            count += 1

    return count


if __name__ == "__main__":
    input_1 = input()
    vertex_count, sides_count = list(map(int, input_1.split()))
    input_list = []
    for _ in range(sides_count):
        vertex_1, vertex_2, distance = list(map(int, input().split()))
        input_list.append((vertex_1, vertex_2, distance))
    print(main(vertex_count, input_list))

Submission status: Wrong Answer

Solution code:
def gen_graph(input_list):
    graph = {}

    for item in input_list:
        if not item[0] in graph:
            graph[item[0]] = {}
        if not item[1] in graph:
            graph[item[1]] = {}
        graph[item[0]][item[1]] = item[2]
        graph[item[1]][item[0]] = item[2]

    return graph


def get_lowest_cost_vertex(costs, processed):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


def get_best_routes(graph, start):
    costs = {}
    parents = {}
    processed = []

    costs[start] = 0
    parents[start] = None
    processed.append(start)

    for item in graph[start].keys():
        costs[item] = graph[start][item]
        parents[item] = start

    for item in graph.keys():
        if not (item in costs.keys() or item == start):
            costs[item] = float("inf")
            parents[item] = None

    node = get_lowest_cost_vertex(costs, processed)

    while node is not None:
        cost = costs[node]
        neighbors = graph[node]

        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        node = get_lowest_cost_vertex(costs, processed)

    routes = []
    for item in graph.keys():
        if item != start:
            route = []
            route.append(item)
            parent = parents[item]
            while 1:
                route.append(parent)
                if parent == start:
                    break
                parent = parents[parent]
            route.reverse()
            routes.append(route)
    return routes


def main(vertex_count, input_list):
    graph = gen_graph(input_list)

    routes = []
    for start in range(1, vertex_count+1):
        for route in get_best_routes(graph, start):
            routes.append(route)

    route_strs = []
    for route in routes:
        route_strs.append(''.join(list(map(str, route))))

    side_strs = []
    for item in input_list:
        side_strs.append(str(item[0]) + str(item[1]))
        # side_strs.append(str(item[1]) + str(item[0]))

    count = 0
    route_strs_joined = '/'.join(route_strs)

    for side_str in side_strs:
        if route_strs_joined.find(side_str) == -1:
            count += 1

    return count


if __name__ == "__main__":
    input_1 = input()
    vertex_count, sides_count = list(map(int, input_1.split()))
    input_list = []
    for _ in range(sides_count):
        vertex_1, vertex_2, distance = list(map(int, input().split()))
        input_list.append((vertex_1, vertex_2, distance))
    print(main(vertex_count, input_list))

Submission status: Wrong Answer

Solution code:
def gen_graph(input_list):
    graph = {}

    for item in input_list:
        if not item[0] in graph:
            graph[item[0]] = {}
        if not item[1] in graph:
            graph[item[1]] = {}
        graph[item[0]][item[1]] = item[2]
        graph[item[1]][item[0]] = item[2]

    return graph


def get_lowest_cost_vertex(costs, processed):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


def get_best_routes(graph, start):
    costs = {}
    parents = {}
    processed = []

    costs[start] = 0
    parents[start] = None
    processed.append(start)

    for item in graph[start].keys():
        costs[item] = graph[start][item]
        parents[item] = start

    for item in graph.keys():
        if not (item in costs.keys() or item == start):
            costs[item] = float("inf")
            parents[item] = None

    node = get_lowest_cost_vertex(costs, processed)

    while node is not None:
        cost = costs[node]
        neighbors = graph[node]

        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        node = get_lowest_cost_vertex(costs, processed)

    routes = []
    for item in graph.keys():
        if item != start:
            route = []
            route.append(item)
            parent = parents[item]
            while 1:
                route.append(parent)
                if parent == start:
                    break
                parent = parents[parent]
            route.reverse()
            routes.append(route)
    return routes


def main(vertex_count, input_list):
    graph = gen_graph(input_list)

    routes = []
    for start in range(1, vertex_count+1):
        for route in get_best_routes(graph, start):
            routes.append(route)

    route_strs = []
    for route in routes:
        route_strs.append(''.join(list(map(str, route))))

    side_strs = []
    for item in input_list:
        side_strs.append(str(item[0]) + str(item[1]))
        side_strs.append(str(item[1]) + str(item[0]))

    count = 0
    route_strs_joined = '/'.join(route_strs)

    for side_str in side_strs:
        if route_strs_joined.find(side_str) == -1:
            count += 1

    return count / 2


if __name__ == "__main__":
    input_1 = input()
    vertex_count, sides_count = list(map(int, input_1.split()))
    input_list = []
    for _ in range(sides_count):
        vertex_1, vertex_2, distance = list(map(int, input().split()))
        input_list.append((vertex_1, vertex_2, distance))
    print(main(vertex_count, input_list))

Submission status: Wrong Answer

Solution code:
inf = float('inf')

# dist[i][j]: iからjへのコスト,  n:頂点数
def warshall_floyd(dist,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

N,M = map(int,input().split())
edges = []
ad = [[inf]*N for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1;  b -= 1
    edges.append((a,b,c))
    ad[a][b] = c
    ad[b][a] = c

warshall_floyd(ad,N)
ans = M

for a,b,c in edges:
    for s in range(N):
        for e in range(s+1,N):
            if ad[s][a] + c + ad[b][e] == ad[s][e]:
                ans -= 1
                break
        else:
            continue
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=list(map(int, input().strip().split()))
abc={}
used={}
for _ in range(M):
    a,b,c=(list(map(int, input().strip().split())))
    abc[a,b]=c
    used[a,b]=False
spth=[[float("inf")]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if i==j:
            spth[i][j]=0
        if (i,j) in abc:
            spth[i][j]=abc[i,j]
        elif (j,i) in abc:
            spth[i][j]=abc[j,i]
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            d=spth[i][k]+spth[k][j]
            if spth[i][j] > d:
                spth[i][j]=d

for ab,c in abc.items():
    for s in range(1,N+1):
        if used[ab]:break
        if spth[s][ab[1]]==spth[s][ab[0]]+c:
            used[ab]=True
            break
print(sum(not i for i in used.values()))

Submission status: Wrong Answer

Solution code:
N,M=list(map(int, input().strip().split()))
abc={}
used={}
for _ in range(M):
    a,b,c=(list(map(int, input().strip().split())))
    abc[a,b]=c
    used[a,b]=False
spth=[[float("inf")]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if i==j:
            spth[i][j]=0
        if (i,j) in abc:
            spth[i][j]=abc[i,j]
        elif (j,i) in abc:
            spth[i][j]=abc[j,i]
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            d=spth[i][k]+spth[k][j]
            if spth[i][j] > d:
                spth[i][j]=d

for ab,c in abc.items():
    brk=False
    for s in range(1,N+1):
        if brk:break
        for t in range(1,N+1):
            if brk:break
            if used[ab]:break
            if spth[s][t]==spth[s][ab[0]]+c+spth[ab[1]][t]:
                used[ab]=True
                brk=True
                break
print(sum(not i for i in used.values()))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N,M=list(map(int, input().strip().split()))
abc={}
used={}
for _ in range(M):
    a,b,c=(list(map(int, input().strip().split())))
    abc[a,b]=c
    used[a,b]=False
spth=[[float("inf")]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if i==j:
            spth[i][j]=0
        if (i,j) in abc:
            spth[i][j]=abc[i,j]
        elif (j,i) in abc:
            spth[i][j]=abc[j,i]
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            d=spth[i][k]+spth[k][j]
            if spth[i][j] > d:
                spth[i][j]=d

for s in range(1,N+1):
    for ab,c in abc.items():
        if spth[s][ab[1]]==spth[s][ab[0]]+c:
            used[ab]=True
            break
print(sum(not i for i in used.values()))