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: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n,m = map(int,input().split())
d = [[inf]*n for i in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
edge = 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])
ans = set()
for i in range(n):
    for j in range(n):
        if edge[i][j] < inf and edge[i][j] > 0:
            ans.add((i,j))
for i in range(n):
    a = set()
    for j in range(n):
        if edge[i][j] !=inf and edge[i][j] > d[i][j]:
            a.add((i,j))
    ans = ans & (ans-a)
print(m-len(ans)//2)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
INF = 10 ** 9
dist = [[INF]*N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

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

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 i in range(M):
    a, b, c = mem[i]
    if c != dist[a][b]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from functools import reduce
from operator import or_

# 入力
N, M = map(int, input().split())
a, b, c = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)

# 各頂点に対してダイクストラ法により最短経路を求める
G = [{} for _ in range(N + 1)]
for x, y, w in zip(a, b, c):
    G[x][y] = w
    G[y][x] = w

INF = 10**10


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    res = set()
    heappush(q, (0, s, s))
    while q:
        c, i, p = heappop(q)
        if c < dp[i]:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j, i))
        if c == dp[i] and i != p:
            res.add((p, i))
    return res


# 最短経路に含まれない辺の数を求める
ans = M - len(reduce(or_, (dijkstra(G, i) for i in range(1, N + 1)))) // 2

# 出力
print(ans)

Submission status: Accepted

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

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
edges = ABC[:]

graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shrtest = [[0]*(N+1)]
for a in range(1, N+1):
    sub_shrtest = dijkstra(graph, a)
    shrtest.append(sub_shrtest)
#print(shrtest)

ans = 0
for a,b,c in edges:
    if shrtest[a][b] != c:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
abc= [list(map(int,input().split())) for _ in [0]*M]
d = [[10000*N]*N for _ in [0]*N]
for a,b,c in abc:
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
ans=sum(d[a-1][b-1]<c for a,b,c in abc)
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
N, M = map(int, input().split())
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = c


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


ans = 0
for i in range(N):
    for j in range(N):
        if G[i][j] == float('inf'):
            continue
        if G[i][j] != Shortest[i][j]:
            ans += 1

print(ans // 2)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra

#sys.setrecursionlimit(10000)

N, M = [int(i) for i in input().split()]

rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
d1, pre = dijkstra(graph, directed=False, unweighted=False, return_predecessors =True)
#print(d1)
#print(pre)

path = [[0] * N for j in range(N)]
for i in range(N):
    for j in range(N):
        if pre[i][j] != -9999:
            if j < pre[i][j]:
                path[j][pre[i][j]] = 1
            else:
                path[pre[i][j]][j] = 1

print(M-sum(map(sum, path)))

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra

#sys.setrecursionlimit(10000)

N, M = [int(i) for i in input().split()]

rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
d1, pre = dijkstra(graph, directed=False, unweighted=False, return_predecessors =True)
#print(d1)
#print(pre)

path = []
for i in range(N):
    for j in range(N):
        if pre[i][j] != -9999:
            if j < pre[i][j]:
                path.append([j,pre[i][j]])
            else:
                path.append([pre[i][j], j])
path = list(map(list, set(map(tuple, path))))
print(M-len(path))

Submission status: Accepted

Solution code:
import copy
N, M = map(int, input().split())
INF = 2 ** 63 - 1
d = [[INF for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
    d[i][i] = 0

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

d_original = copy.deepcopy(d)

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

ans = 0
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if d_original[i][j] != INF and d[i][j] != d_original[i][j]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
	INF = 10**9+7
	N, M = map(int, input().split())
	dist = [[INF for _ in range(N+1)] for _ in range(N+1)]
	for i in range(1, N+1):
		for j in range(1, N+1):
			if i == j:
				dist[i][j] = 0
	a, b, c = [0]*M, [0]*M, [0]*M
	for i in range(M):
		a[i], b[i], c[i] = map(int, input().split())
		dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i])
		dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i])
	for k in range(1, N+1):
		for i in range(1, N+1):
			for j in range(1, N+1):
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
	ans = M
	for i in range(M):
		shrotest = False
		for j in range(1, N+1):
			if dist[j][a[i]]+c[i] == dist[j][b[i]]:
				shrotest = True
		if shrotest:
			ans -= 1
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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:
    # dにx,y,z の情報が残っていたら利用されている
    if d[x][y] == z:
        ans -= 1
print(ans)

Submission status: Accepted

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

inf = float('inf')

def path(u, v):
    return frozenset((u, v))


class Graph_dijkstra(object):
    def __init__(self, V: "List[int]", E: "Set[FrozenSet[int, int]]", L: "Dict[FrozenSet[int, int], int]"):
        self.V = V
        self.E = E
        self.L = L
        self.E_shortest = copy.deepcopy(E)
        self.adjacent = self.init_adjacent() # type: Dict[int: List[int]]
        self.shortest_path = self.init_shortest_path() # type: Dict[FrozenSet[int, int], int]
    
    def init_adjacent(self):
        ret = {v: [] for v in self.V}
        for e in self.E:
            el = list(e)
            ret[el[0]].append(el[1])
            ret[el[1]].append(el[0])
        return ret
    
    def init_shortest_path(self):
        ret = {path(s, g): inf for s, g in itertools.permutations(self.V, 2)}
        for v in self.V:
            ret[path(v, v)] = 0
        return ret
    
    def dijkstra(self, s: int, g: int):
        d = self.shortest_path[path(s, g)]
        if d < inf:
            return d

        D = {v: inf for v in self.V}
        D[s] = 0
        prev = {v: None for v in self.V}
        Q = [(0, s)]

        while len(Q) > 0:
            du, u = heapq.heappop(Q)
            for v in self.adjacent[u]:
                e = path(u, v)
                alt = du + self.L[e]
                if alt < D[v]:
                    D[v] = alt
                    prev[v] = u
                    heapq.heappush(Q, (D[v], v))

        for v in self.V:
            self.shortest_path[path(s, v)] = D[v]

        return self.shortest_path[path(s, 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 = path(a[i], b[i])
        E.add(e)
        L[e] = c[i]

    G = Graph_dijkstra(V, E, L)
    count = 0
    for e in E:
        el = list(e)
        path_len = G.dijkstra(el[0], el[1])
        if path_len < L[e]:
            count += 1
    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: Accepted

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

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

MAX = 10**10
dist = [[MAX for j in range(N)] for i in range(N)]
#dist += MAX

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

for i in range(M):
    dist[a[i]][b[i]] = c[i]
    dist[b[i]][a[i]] = c[i]

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 i in range(M):
    if dist[a[i]][b[i]] < c[i]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

wf = [[float('inf')] * n for _ in range(n)]
for a, b, c in d:
    wf[a][b] = wf[b][a] = c
for i in range(n):
    wf[i][i] = 0

for k, i, j in itertools.product(range(n), repeat=3):
    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

ans = 0
for a, b, c in d:
    used = False
    for i in range(n):
        for j in range(i + 1, n):
            if wf[i][a] + c + wf[b][j] == wf[i][j] \
                    or wf[i][b] + c + wf[a][j] == wf[i][j] \
                    or wf[j][a] + c + wf[b][i] == wf[j][i] \
                    or wf[j][b] + c + wf[a][i] == wf[j][i]:
                used = True
            
    if not used:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class Dijkstra: # 最短経路問題
    def __init__(self, route_map, start_point, goal_point=None):
        self.route_map = route_map #
        self.start_point = start_point # スタート位置
        self.goal_point = goal_point

    def execute(self):
        import heapq
        num_of_city = len(self.route_map) # ノード数
        dist = [float("inf") for _ in range(num_of_city)] # startからの距離を格納する
        prev = [float("inf") for _ in range(num_of_city)] # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる

        dist[self.start_point] = 0 # スタート位置までのコストは0
        heap_q = [] # 優先度つきキュー
        heapq.heappush(heap_q, (0, self.start_point)) # タプル(0,スタート位置)をheap_qに追加
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q) # 直前にheap_qに入れたタプルから取り出す(src＝ソース)

            if dist[src] < prev_cost: # もし、スタート位置からsrcまでの距離がprev_costより小さいなら問題ないのでok
                continue

            for dest, cost in self.route_map[src].items(): # destはsrcから行ける頂点(目的地)
                if cost != float("inf") and dist[dest] > dist[src] + cost: # もし、destに有限のコストで行けて、srcからdestに行くのがスタートからの現状の最短距離になるなら、
                    dist[dest] = dist[src] + cost # 更新する
                    heapq.heappush(heap_q, (dist[dest], dest)) # 更新したのでheap_qに入れておく。次のノードに移動した時に取り出して無駄な変更がないか確認する
                    prev[dest] = src
        if self.goal_point is not None: # ゴールまでの最短経路を返す
            return self.get_path(self.goal_point, prev)
        else: # スタートから各頂点までの最短距離を格納したリストを返す
            return dist

    def get_path(self, goal, prev):  # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる
        global edge_num
        global used_edge
        path = [goal]
        dest = goal
        
        while prev[dest] != float("inf"): # prev[start]はfloat("inf")になり、停止する
            used_edge[edge_num[prev[dest]][dest]] += 1
            path.append(prev[dest]) # 後ろから戻っていく
            dest = prev[dest]

        return list(reversed(path)) # 逆から辿ったので順を元に戻す

import sys
input = sys.stdin.readline


N,M = map(int,input().split())
route_map = [dict() for _ in range(N)]
edge_num = [dict() for _ in range(N)]
for i in range(M): # M == エッジの数
    u, v, cost = map(int, input().split()) # cost は 辺　u -> v の重み(距離,コスト)
    u, v = u - 1, v - 1
    route_map[u][v] = cost # route_mapの第u番目のdictに{v:cost}が入る
    route_map[v][u] = cost # route_mapの第v番目のdictに{u:cost}が入る
    edge_num[u][v] = i # redge_numの第u番目のdictに{v:i}が入る
    edge_num[v][u] = i # redge_numの第v番目のdictに{u:i}が入る


used_edge = [0 for _ in range(M)]
checked_node = [[0 for _ in range(N)] for __ in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        if checked_node[i][j] != 0:
            continue
        dijkstra_result1 = Dijkstra(route_map, i, j).execute()
        for k in range(len(dijkstra_result1)-1):
            for l in range(k+1,len(dijkstra_result1)):
                checked_node[dijkstra_result1[k]][dijkstra_result1[l]] += 1
        """
        dijkstra_result2 = Dijkstra(route_map, N-1-i, N-1-j).execute()
        for k in range(len(dijkstra_result2)-1):
            for l in range(k+1,len(dijkstra_result2)):
                checked_node[dijkstra_result2[k]][dijkstra_result2[l]] += 1
        """

ans = used_edge.count(0)
print(ans)

Submission status: Accepted

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 #自身のところに行くコストは０
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: Accepted

Solution code:
n, m = [int(item) for item in input().split()]
abc = [[int(item) for item in input().split()] for _ in range(m)]
INF = 10 ** 9

edge = [[INF] * n for _ in range(n)]
v_edge = [[1] * n for _ in range(n)]
for a, b, c in abc:
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c

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

count = 0
for a, b, c in abc:
    if edge[a-1][b-1] != c:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import copy
from scipy.sparse.csgraph import floyd_warshall as wf

N, M = map(int, input().split())
INF = float('inf')

d = [[INF] * (N) for i in range(N)]
e_list = []
for i in range(N):
    d[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c
    e_list.append([a - 1, b - 1, c])
    
wf = wf(d)

cnt = M
for a, b, c in e_list:
    for i in range(N):
        if wf[i][a] + c == wf[i][b]:
            cnt -= 1
            break
    
print(cnt)

Submission status: Accepted

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):
        if d[i][x] + z == d[i][y]:
            ans -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(d,route):
    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]
                    route[i][j] = route[i][k] + route[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)]
route = [[[] for i in range(n)] for i in range(n)]
for i in range(w):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
    route[x][y].append(i)
    route[y][x].append(i)
for i in range(n):
    d[i][i] = 0

warshall_floyd(d,route)
ans = w
s = set()
for i in range(n):
    for j in range(n):
        for k in route[i][j]:
            if k not in s:
                ans -= 1
                s.add(k)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

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

    INF = 10**6
    A = np.array([[INF for _ in range(N)] for _ in range(N)])
    for i in range(N):
        A[i][i] = 0

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

    G = floyd_warshall(A)

    ans = 0
    for a, b, c in edges:
        if G[a][b] < c:
            ans += 1

    return ans


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

Submission status: Accepted

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: Accepted

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:
        side = [item[0], item[1]]
        side_sorted = sorted(side)
        sides.append(side_sorted)

    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: Accepted

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

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

INF = 10**9
# dist is minimal distance between node i and node j
dist = [[INF if i != j else 0 for i in range(N)] for j in range(N)]

# calculate minimal distance of all nodes combination
for i in range(M):
    dist[A[i]][B[i]] = min(dist[A[i]][B[i]], C[i])
    dist[B[i]][A[i]] = min(dist[B[i]][A[i]], C[i])

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

ans = M
for i in range(M):
    # isShortest = False
    for j in range(N):
        if dist[j][A[i]] + C[i] == dist[j][B[i]]:
            ans = ans - 1
            break

print(ans)

Submission status: Accepted

Solution code:
#D問題
N,M=map(int,input().split())

def warshall_floyd(dist,n):
    #dist[i][j]: iからjへの最短距離
    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])
    return dist

dist = [[float("inf") for i in range(N)] for i in range(N)] 
#dist[u][v] : 辺uvのコスト(存在しないときはinf)
xyz=[]
for i in range(M):
    x,y,z = map(int,input().split())
    xyz.append([x-1,y-1,z])
    dist[x-1][y-1] = z
    dist[y-1][x-1] = z
for i in range(N):
    dist[i][i] = 0 #自身のところに行くコストは０
wf=warshall_floyd(dist,N)
ans=M
for i in range(M):
    j=0
    flag=0
    for j in range(N):
        if wf[j][xyz[i][0]] + xyz[i][2] == wf[j][xyz[i][1]]:
            flag=1
            break
    if flag == 1:
        ans-=1
    flag=0
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

def main():
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N, M = (int(_) for _ in input().split())
    d = [[1e10 for _ in range(N)] for _ in range(N)]
    a = []
    b = []
    c = []
    for i in range(M):
        ai, bi, ci = (int(_) for _ in input().split())
        d[ai-1][bi-1] = ci
        d[bi-1][ai-1] = ci
        a.append(ai-1)
        b.append(bi-1)
        c.append(ci)
        
    for i in range(N):
        d[i][i] = 0       
        
    for i in range(N):
        for j in range(N):
            for k in range(N):
                d[j][k] = min(d[j][i]+d[i][k],d[j][k])

    ans = M
    for i in range(M):
        is_shortest = False
        for j in range(N):
            if(d[j][a[i]]+c[i] == d[j][b[i]]):
                is_shortest = True
        if is_shortest:
            ans -= 1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def candidates_of_no_shortest_paths(N: int, M: int, edges: list)->int:
    INF = float('inf')

    d = [[0 if i == j else INF for i in range(N)] for j in range(N)]

    for u, v, c in edges:
        d[u-1][v-1] = d[v-1][u-1] = c

    # warshall-floyd
    for k in range(N):
        for u in range(N):
            for v in range(N):
                if d[u][v] > d[u][k] + d[k][v]:
                    d[u][v] = d[u][k] + d[k][v]

    def used(edge: tuple)->bool:
        u, v, c = edge
        for s in range(N):
            if d[s][u-1] + c == d[s][v-1]:
                return True
        return False

    return sum(not used(edge) for edge in edges)


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(int(s) for s in input().split()) for _ in range(M)]
    ans = candidates_of_no_shortest_paths(N, M, edges)
    print(ans)

Submission status: Accepted

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

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):
        if ad[s][a] + c == ad[s][b]:
            ans -= 1
            break

print(ans)