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:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *ABC = map(int, read().split())
    G = [[INF] * N for _ in range(N)]
    edge = [0] * M
    for i, (a, b, c) in enumerate(zip(*[iter(ABC)] * 3)):
        edge[i] = (a - 1, b - 1, c)
        G[a - 1][b - 1] = G[b - 1][a - 1] = c
    for i in range(N):
        G[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]

    ans = 0
    for a, b, c in edge:
        used = False
        for i in range(N):
            if G[i][b] == G[i][a] + c or G[i][a] == G[i][b] + c:
                used = True
                break
        if not used:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for i, (a, b, c) in enumerate(zip(*[iter(AB)] * 3)):
        G[a - 1].append((b - 1, c, i))
        G[b - 1].append((a - 1, c, i))

    vec = [False] * M
    for i in range(N):
        dist = [INF] * N
        dist[i] = 0
        from_edge = [[] for _ in range(N)]
        hq = [(0, i)]

        while hq:
            d, v = heappop(hq)
            if dist[v] < d:
                continue
            for nv, cost, edge in G[v]:
                if dist[nv] > d + cost:
                    dist[nv] = d + cost
                    heappush(hq, (dist[nv], nv))
                    from_edge[nv] = [edge]
                elif dist[nv] == d + cost:
                    from_edge[nv].append(edge)

        for edges in from_edge:
            for e in edges:
                vec[e] = True

    ans = sum(1 for flag in vec if not flag)
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy
INF = 1 << 32
n, m = map(int, input().split())
d = [[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
    d[a][b] = c
    d[b][a] = c # 無向グラフ
for i in range(n):
    d[i][i] = 0

dist = deepcopy(d)
# FloydWarshall
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])
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if d[i][j] < INF and d[i][j] != dist[i][j]:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys 
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

N,M=map(int,input().split())
G= [[0]*(N+1) for _ in range(N+1)]
abc = [list(map(int,input().split())) for _ in range(M)]

for a, b, c in abc:
  G[a][b] = c
  G[b][a] = c

cost = floyd_warshall(csr_matrix(G))
cnt = 0
for a, b, c in abc:
  if cost[a][b] < c:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def warshall_floyd(d,n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if(i!=j):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
def main():

    n,m=map(int, input().split())
    edge = [[] for _ in range(n)]
    d = [[float("inf")]*n for i in range(n)]
    d_1 = [[float("inf")]*n for i in range(n)]
    e_lis = [0]*m
    for i in range(m):
        a,b,c=map(int, input().split())
        d[a-1][b-1]=d[b-1][a-1]=d_1[a-1][b-1]=d_1[b-1][a-1]=c
    res = warshall_floyd(d,n)
    cnt=0
    for i in range(n):
        for j in range(n):
            if(res[i][j]!=d_1[i][j] and d_1[i][j]<10000):
                cnt+=1
    print(cnt//2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

edges = [[] for _ in range(n)]
for a,b,dis in abc:
    edges[a-1].append((b-1, dis))
    edges[b-1].append((a-1, dis))

def dijkstra(edges, s):
    hq = []
    d = [-1] * n
    d[s] = 0
    heapq.heappush(hq, (0, s))
    while hq:
        d1, p = heapq.heappop(hq)
        for p2, d2 in edges[p]:
            if d[p2] == -1 or d[p2] > d1 + d2:
                d[p2] = d1 + d2
                heapq.heappush(hq, (d1+d2, p2))
    return d

d = []

for i in range(n):
    d.append(dijkstra(edges, i))

ans = 0

for a,b,dis in abc:
    if dis > d[a-1][b-1]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
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
 
 
n,w = map(int,input().split()) #n:頂点数　w:辺の数
 
d = [[float("inf")]*n for i in range(n)]

E = [tuple(map(int, input().split())) for _ in range(w)]

#d[u][v] : 辺uvのコスト(存在しないときはinf)
for x,y,z in E:
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

root = warshall_floyd(d)

ans = 0

for x,y,z in E:
    if d[x-1][y-1] != z:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial, gcd
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
import sys  # def input(): return sys.stdin.readline().rstrip() # sys.setrecursionlimit(10**6)

from collections import defaultdict, deque
from heapq import heappush, heappop

class DiGraph:
    def __init__(self, n, edges, weight=False):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.reverse_adj = [[] for _ in range(n)]
        self.degree = [0] * n
        self.weight = defaultdict(lambda: 10**18)
        if weight:
            for u, v, weight in edges:
                self.adj[u].append(v)
                self.reverse_adj[v].append(u)
                self.degree[v] += 1
                self.weight[(u, v)] = weight
        else:
            for u, v in edges:
                self.adj[u].append(v)
                self.reverse_adj[v].append(u)
                self.degree[v] += 1
                self.weight[(u, v)] = 1

    def dijkstra(self, start, goal=None):  # O((V+E)logV)
        INF = 10**18
        dist = [INF] * self.n
        dist[start] = 0
        heap = [(0, start)]  # (dist, v)
        sp_prev = [None] * self.n  # previous node in shortest path (sp)
        while heap:
            dist_v, v = heappop(heap)
            if dist[v] < dist_v:
                continue
            for adj in self.adj[v]:
                edge_weight = self.weight[(v, adj)]
                if dist[v] + edge_weight < dist[adj]:
                    dist[adj] = dist[v] + edge_weight
                    sp_prev[adj] = v
                    heappush(heap, (dist[adj], adj))

        if goal is not None:
            if dist[goal] == INF:
                return dist, []
            else:
                path = [goal]
                v = goal
                while v != start:
                    v = sp_prev[v]
                    path.append(v)
                path.reverse()
                return dist, path
        else:
            return dist, sp_prev

    def scc_decompose(self):  # strongly connected components decomposition (強連結成分分解) O(V+E)
        used = [False] * self.n
        order = []  # 帰りがけ順
        for i in range(self.n):
            if not used[i]:
                stack = [i]
                used[i] = True
                while stack:
                    u = stack.pop()
                    u_movable = False
                    for v in self.adj[u]:  # u -> v
                        if not used[v]:
                            u_movable = True
                            used[v] = True
                            stack.append(u)
                            stack.append(v)
                            break
                    if not u_movable:
                        order.append(u)

        used = [False] * self.n
        group = [None] * self.n
        label = 0
        for v in reversed(order):
            if not used[v]:
                stack = [v]
                group[v] = label
                while stack:
                    v = stack.pop()
                    used[v] = True
                    for u in self.reverse_adj[v]:  # v -> u (reverse)
                        if not used[u]:
                            group[u] = label
                            stack.append(u)
                label += 1

        # construct reduction graph
        reduction_graph = [[] for _ in range(len(set(group)))]
        reduction_components = [[] for _ in range(len(set(group)))]
        for u in range(self.n):
            for v in self.adj[u]:  # u -> v
                if group[u] == group[v]:
                    continue
                reduction_graph[group[u]].append(group[v])
            reduction_components[group[u]].append(u)
        return reduction_graph, reduction_components, group

# ---------------------- #

def topological_sort(DAG):  # O(V+E)
    n = len(DAG)
    degree = [0] * n
    for u in range(n):
        for v in DAG[u]:  # u -> v
            degree[v] += 1
    ret = [i for i in range(n) if degree[i] == 0]
    queue = deque(ret)
    while queue:
        u = queue.popleft()
        for v in DAG[u]:
            degree[v] -= 1
            if degree[v] == 0:
                queue.append(v)
                ret.append(v)
    return ret

# ---------------------- #

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

G = DiGraph(n, edges, weight=True)
ANS = set()
for u, v in combinations(range(n), 2):
    _, path = G.dijkstra(u, v)
    for a, b in zip(path[:], path[1:]):
        ANS.add((a, b))

ans = 0
for a, b, _ in edges:
    if (a, b) in ANS or (b, a) in ANS:
        continue
    else:
        ans += 1
print(ans//2)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
INF=10**18
e=[[INF for _ in range(n)]for _ in range(n)]
d=[]
for i in range(m):
  a,b,c=map(int,input().split())
  e[a-1][b-1]=c
  e[b-1][a-1]=c
  d.append((a-1,b-1,c))
for k in range(n):
  for i in range(n):
    for j in range(n):
      e[i][j]=min(e[i][j],e[i][k]+e[k][j])
ans=0
for i,j,k in d:
  if e[i][j]!=k:ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
graph=[[] for _ in range(N)]
cost=[[float("inf")]*N for _ in range(N)]
for _ in range(M):
    a,b,c=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1][b-1]=c
    cost[b-1][a-1]=c

def dijkstra(S,N,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[S]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
    
    return d

dist=[]
for s in range(N):
    dist.append(dijkstra(s,N,cost))

checked=[[False]*N for _ in range(N)]
ans=M
for s in range(N):
    for i in range(s,N):
        for j in graph[i]:
            if checked[i][j]:
                continue
            
            if dist[s][i]+cost[i][j]==dist[s][j]:
                ans-=1
                checked[i][j]=True
                checked[j][i]=True
print(ans)

Submission status: Accepted

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

def main():
  n, m = map(int, input().split())
  road = [[100000]*n for _ in range(n)]
  count = [[-1]*n for i in range(n)]
  for _ in range(m):
    a, b, c = map(int, input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
    count[a-1][b-1] = 0
    count[b-1][a-1] = 0
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if road[i][k]+road[k][j] < road[i][j]:
          if count[i][j] == 0:
            count[i][j] = 1
          road[i][j] = road[i][k]+road[k][j]
  ans = 0
  for i in range(n):
    ans += count[i].count(1)
  print(ans//2)
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
              #if (d[i][k] != float("INF")) and (d[k][j] != float("INF")):
                d[i][j] = min(d[i][k] + d[k][j], d[i][j])
                
        #print(d)
    return d

##############################
n,m = map(int,input().split()) #n:頂点数　m:辺の数

d = [[float("INF")] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)

hen = [0] * m
for i in range(m):
    x,y,z = map(int,input().split())
    d[x - 1][y - 1] = z
    d[y - 1][x - 1] = z
    hen[i] = [x - 1, y - 1, z]
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

ans = warshall_floyd(d)
#それぞれの出発地点ごとにmaxをとり、そのmaxが最小の地点に引っ越し
#そのときの所要時間がp
#print(used)
answer = 0
for i in range(m):
  now = hen[i]
  if d[now[0]][now[1]] != now[2]:
    answer += 1
  
print(answer)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a,b,c=0,0,0
E=[]
INF=10**12
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())
  a,b=a-1,b-1
  D[a][b]=c
  D[b][a]=c
  E.append((a,b,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])
P=0
for i in range(M):
  if D[E[i][0]][E[i][1]]!=E[i][2]:
    P+=1
print(P)

Submission status: Accepted

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

import numpy as np
from scipy.sparse import *

N, M = ri_()
a = [0] * M
b = [0] * M
c = [0] * M
for i in range(M):
    ai, bi, ci = ri_()
    a[i], b[i], c[i] = ai - 1, bi - 1, ci
G = csr_matrix((c, (a, b)), shape=(N, N))
d = csgraph.floyd_warshall(G, directed=False)
ans = 0
for i in range(M):
    if d[a[i], b[i]] != c[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    dist = [
        [math.inf]*N for _ in range(N)
    ]

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

    A, B, C = [], [], []
    for _ in range(M):
        a, b, c = read_ints()
        a -= 1
        b -= 1
        A.append(a)
        B.append(b)
        C.append(c)
        dist[a][b] = 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][k]+dist[k][j], dist[i][j])

    count = M
    for i in range(M):
        is_shortest = False
        for j in range(N):
            if dist[j][A[i]] == dist[j][B[i]]+C[i]:
                is_shortest = True
        if is_shortest:
            count -= 1
    return count


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

Submission status: Accepted

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

n,w = map(int,input().split(" "))

a = []

d = [[10 ** 10] * n for i in range(n)]
k = [n for i in range(n)]

for i in range(w):
    x,y,z = map(int,input().split(" "))
    d[x-1][y-1] = z
    d[y-1][x-1] = z
    a.append([x,y,z])
for i in range(n):
    d[i][i] = 0

d = warshall_floyd(d)

ans = w
for i in range(len(a)):
    for s in range(n):
        if d[s][a[i][1]-1] + a[i][2] == d[s][a[i][0]-1]:
            ans -= 1
            break

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    from collections import defaultdict
    from copy import copy
    n, m = map(int, readline().split())

    used = dict()
    for i in range(n):
        used[i] = dict()

    edge = defaultdict(list)

    for i in range(m):
        a, b, c = map(int, readline().split())
        edge[a].append((b, c))
        edge[b].append((a, c))
        if a < b:
            used[a][b] = False
        else:
            used[b][a] = False

    for i in range(1,n+1):
        dist = [100000000000] * (n+1)
        dist[i] = 0
        prev = defaultdict(list)
        hq = []
        heapq.heappush(hq, (0, i))
        while hq:
            cur, u = heapq.heappop(hq)
            for v, w in edge[u]:
                if dist[v] > cur + w:
                    dist[v] = cur + w
                    prev[v] = [u]
                    heapq.heappush(hq, (cur + w, v))
                elif dist[v] == cur + w:
                    prev[v].append(u)
                    heapq.heappush(hq, (cur + w, v))

        for v, val in prev.items():
            for u in val:
                if u < v:
                    used[u][v] = True
                else:
                    used[v][u] = True

    ans = 0

    for val in used.values():
        for x in val.values():
            if not x:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
es = []
for i in range(m):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    ns[v].add((c,u))
    es.append((u,v,c))
    
def dijkstra(start):
    import heapq
    vals = [None] * n
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if vals[v] is None or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
unused = [True]*m
for u in range(n):
    vals = dijkstra(u)
    for i,(a,b,c) in enumerate(es):
        if abs(vals[a]-vals[b])==c:
            unused[i] = False
ans = sum(unused)
print(ans)

Submission status: Accepted

Solution code:
#ワーシャルフロイド法
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


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

d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
edge=[]
for i in range(m):
    x,y,c = map(int,input().split())
    x-=1
    y-=1
    edge.append((x,y,c))
    d[x][y] = c
    d[y][x] = c
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
d=warshall_floyd(d)
ans=0
for x,y,c in edge:
    if d[x][y]<c:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M = getNM()
query = [getList() for i in range(M)]

dist = [[float('inf')] * N for i in range(N)]
for i in range(N):
    dist[i][i] = 0
for i in range(M):
    a, b, c = query[i]
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

def warshall_floyd(dist):
    for k in range(N):
        # i:start j:goal k:中間地点でループ回す
        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

warshall_floyd(dist)
ng_dist = [0] * M

for i in range(N):
    for j in range(M):
        s, t, c = query[j]
        if dist[i][s - 1] + c == dist[i][t - 1]:
            ng_dist[j] = 1

cnt = 0
for i in ng_dist:
    if i == 0:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import heapq

def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    used = set()
    for i in range(N):
        H = []
        for b, c in G[i]:
            heapq.heappush(H, (c, i, b))
        D = [10**10] * N
        D[i] = 0
        while H:
            c, a, b = heapq.heappop(H)
            if D[b] < c:
                continue
            D[b] = c
            if a < b:
                used.add((a, b))
            else:
                used.add((b, a))
            for d, cc in G[b]:
                if D[d] > c + cc:
                    D[d] = c + cc
                    heapq.heappush(H, (c + cc, b, d))
    return M - len(used)

print(main())

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
def main():
    N, M = map(int, input().split())
    w = [[0] * N for i in range(N)]
    l = []
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        w[a][b] = w[b][a] = c
        l.append((a,b,c))
    G = csr_matrix(w)
    d = floyd_warshall(G, directed=False)
    r = 0
    for a, b, c in l:
        if d[a][b] != c:
            r += 1
    return r
print(main())

Submission status: Accepted

Solution code:
class Graph():  #non-directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j, cost in self.graph[i]:
                dist[i][j] = cost
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist


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

g = Graph(N, E)
wf = g.warshall_floyd()

res = 0

for i in range(M):
    a, b, c = E[i]
    if wf[a - 1][b - 1] != c:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import heapq


def dijkstra(n, s, g):
    h = [(0, s)]
    heapq.heapify(h)
    cost = [float("Inf")] * (n + 1)  # cost: i -> j
    cost[s] = 0

    while h:
        c, v = heapq.heappop(h)
        if c > cost[v]:
            continue
        for d, u in g[v]:
            d_s_u = d + cost[v]
            if d_s_u < cost[u]:
                cost[u] = d_s_u
                heapq.heappush(h, (d_s_u, u))

    return cost


def main():
    n, m, *abc = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for a, b, c in zip(*[iter(abc)] * 3):
        g[a].append([c, b])
        g[b].append([c, a])

    ans = 0
    checked = [[False] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        cost = dijkstra(n, i, g)
        for j, k in g[i]:
            if checked[i][k]:
                continue
            if j > cost[k]:
                ans += 1

            checked[i][k] = True
            checked[k][i] = True

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq


def dijkstra(n, s, g):
    h = [(0, s)]
    heapq.heapify(h)
    cost = [float("Inf")] * (n + 1)  # cost: i -> j
    cost[s] = 0

    while h:
        c, v = heapq.heappop(h)
        if c > cost[v]:
            continue
        for d, u in g[v]:
            d_s_u = d + cost[v]
            if d_s_u < cost[u]:
                cost[u] = d_s_u
                heapq.heappush(h, (d_s_u, u))

    return cost


def main():
    n, m, *abc = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for a, b, c in zip(*[iter(abc)] * 3):
        g[a].append([c, b])
        g[b].append([c, a])

    ans = 0
    for i in range(1, n + 1):
        cost = dijkstra(n, i, g)
        for j, k in g[i]:
            if j > cost[k]:
                ans += 1

    print(ans//2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m, *abc = map(int, open(0).read().split())
    d = [[float("Inf")] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        d[i][i] = 0

    for a, b, c in zip(*[iter(abc)] * 3):
        d[a][b] = c
        d[b][a] = c

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

    ans = 0
    for a, b, c in zip(*[iter(abc)] * 3):
        if d[a][b] < c:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
E=[list(map(int,input().split())) for i in range(M)]
INF=10**12
D=[[INF]*N for i in range(N)]
for i in range(N):
  D[i][i]=0
for i in range(M):
  D[E[i][0]-1][E[i][1]-1]=E[i][2]
  D[E[i][1]-1][E[i][0]-1]=E[i][2]
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])
P=0
for i in range(M):
  for j in range(N):
    if D[j][E[i][0]-1]+E[i][2]==D[j][E[i][1]-1] or D[j][E[i][1]-1]+E[i][2]==D[j][E[i][0]-1]:
      break
    if j==N-1:
      P+=1
print(P)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = [[10 ** 9 for _ in range(n)] for _ in range(n)]
edge = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
    edge.append((a, b))
for i in range(n):
    graph[i][i] = 0

from copy import deepcopy
distance = deepcopy(graph)    
for k in range(n):
    for i in range(n):
        for j in range(n):
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
ans = 0
for i, j  in edge:
    if distance[i][j] < graph[i][j]:
        ans += 1
print(ans)