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 heapq

def dijkstra(s):
    inf = 1145141919810
    dist = [inf] * v
    dist[s] = 0
    c = [0] * v
    p = []
    heapq.heapify(p)
    heapq.heappush(p, (dist[s], s))
    while p:
        d, u = heapq.heappop(p)
        if dist[u] < d:
            continue
        c[u] = 1
        for g in G[u]:
            if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
                dist[g[0]] = dist[u] + g[1]
                heapq.heappush(p, (dist[g[0]], g[0]))
    return dist

n, m = map(int, input().split())
v = n
G = [[] for _ in range(v)]
E = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append([b, c])
    G[b].append([a, c])
    E.append([a, b, c])
mindist = [dijkstra(i) for i in range(v)]
ans = m
for e in E:
    for i in range(n):
        if mindist[i][e[0]] - mindist[i][e[1]] == e[2]:
            ans -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

used=set()

for i in range(n):
    q=[(0,i,-1)]
    dist=[10**10]*n
    dist[i]=0
    edge=[0]*n

    while len(q)>0:
        d,u,v=heapq.heappop(q)

        if d>dist[u]:
            continue

        edge[u]=v

        for w,nd in g[u]:
            tmp=nd+dist[u]
            if tmp<dist[w]:
                dist[w]=tmp
                heapq.heappush(q,(tmp,w,u))
    
    for u,v in enumerate(edge):
        if v==-1:
            continue
        used.add((max(u,v),min(u,v)))

print(m-len(used))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Edge = [tuple(map(int, input().split())) for _ in range(M)]

import numpy as np
Graph = np.array([[0 if i == j else np.inf for i in range(N)] for j in range(N)])
for a,b,c in Edge:
    Graph[a-1,b-1] = c
from scipy.sparse.csgraph import dijkstra 
Graph = dijkstra(Graph,directed=False)
ans = 0
for a,b,c in Edge:
    if Graph[a-1,b-1] != c:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
edges = [(i - 1, j - 1, c) for i, j, c in edges]

INF = int(10000)

dp = [[INF for _ in range(N)] for _ in range(N)]
for i, j, cost in edges:
    dp[i][j] = cost
    dp[j][i] = cost

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            if dp[i][k] != INF and dp[k][j] != INF:
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

count = 0
for i, j, cost in edges:
    if dp[i][j] < cost:
        count += 1

print(count)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

INF = float("inf")
import copy

def warshall_floyd(d):
    n = len(d)
    wf = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    return wf #d[i][j]に頂点i, j間の最短距離を格納

##############################

n, m = map(int,input().split()) #N:頂点数 m:辺の数
d = [[INF] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
edges = []
for i in range(m):
    u, v, w = map(int,input().split())
    d[u-1][v-1] = w
    d[v-1][u-1] = w
    edges.append((u-1,v-1))
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

fwd = warshall_floyd(d)   #d[i][j]に頂点i, j間の最短距離を格納

ret = 0
for u,v in edges:
    if fwd[u][v] < d[u][v]:
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
Node,Path = map(int,input().split())
ad_mat = [[float('inf')]*Node for _ in range(Node)]
path_ls = [[0,0,0] for _ in range(Path)]
for i in range(Path):
    a,b,c = map(int,input().split())
    ad_mat[a-1][b-1] = c
    ad_mat[b-1][a-1] = c
    path_ls[i] = a-1,b-1,c
for i in range(Node):
    ad_mat[i][i] = 0

for stop in range(Node):
    for start in range(Node):
        for end in range(Node):
            ad_mat[start][end] = min(ad_mat[start][end],ad_mat[start][stop]+ad_mat[stop][end])

ans = 0
for a,b,cost in path_ls:
    if cost > ad_mat[a][b]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
conns = [tuple(map(int, input().split())) for _ in range(M)]
cost = [[float("INF")]*N for _ in range(N)]

# make same node cost zeros
for i in range(N):
  cost[i][i] = 0

# update edge cost
for a,b,c in conns:
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c

# find minimum cost across all pairs of nodes
for k in range(N):
  for i in range(N):
    for j in range(N):
      cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

# find edges without shortest path
cnt = 0
for a,b,c in conns:
  if c > cost[a-1][b-1]:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# D - Candidates of No Shortest Paths
# ワーシャルフロイド法で、任意の2頂点間の最短距離を求める。
# すべての辺に対して、その距離と、辺の両端間の最短距離を比較し、
# 辺の距離 > 辺の両端間の最短距離なら、その辺は最短経路に使われていないことがわかる。
n,m = map(int,input().split())
e = []
for i in range(m):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  e.append((a,b,c))

INF = float('inf')
d = [[INF for _ in range(n)] for _ in range(n)]
for a,b,c in e:
  d[a][b] = c
  d[b][a] = c
for i in range(n):
  d[i][i] = 0
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j] = min(d[i][k]+d[k][j],d[i][j])
ans = 0
for a,b,c in e:
  if d[a][b] < c:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
to = [[float("INF")] * N for i in range(N)]
aa = []

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

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

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

#print(to)

c = 0
for i in range(M):
    for j in range(N):
        if to[j][aa[i][1]] == to[j][aa[i][0]] + aa[i][2]:
            c += 1
            break


print(M - c)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]

INF = float('inf')
ds = [[INF]*N for _ in range(N)]
for i in range(N):
    ds[i][i] = 0
for a,b,c in ABC:
    a,b = a-1,b-1
    ds[a][b] = ds[b][a] = c

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

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

Submission status: Accepted

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

G = [[] for _ in range(N)]
INF = 10**9
D = [[ INF for _ in range(N)] for _ in range(N)]
for i in range(N):
  D[i][i] = 0

E = []
for _ in range(M):
  a,b,c = map(int, input().split())
  a,b = a-1, b-1
  G[a].append((b,c))
  G[b].append((a,c))
  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):
      if D[i][k] + D[k][j] < D[i][j]:
        D[i][j] = D[i][k] + D[k][j]
        D[j][i] = D[i][k] + D[k][j]
  
ans = 0
for a,b,c in E:
  flg = False
  for i in range(N):
    if D[i][a] + c == D[i][b]:
      flg = True
      break
   
  if not flg:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
INF = 10**18

def main():
    N, M = map(int, input().split())
    repn = [[] for _ in range(N)]
    edge = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        repn[a - 1].append((c, b - 1))
        repn[b - 1].append((c, a - 1))
        edge.append((a - 1, b - 1, c))

    # 全点間最短距離をワーシャルフロイドで求める
    dist = [[INF] * N for _ in range(N)]
    for i in range(N): dist[i][i] = 0
    for i in range(N):
        for cost, j in repn[i]: dist[i][j] = cost

    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 a, b, c in edge:
        no_need = True
        for i in range(N):
            for j in range(N):
                if dist[i][j] > dist[i][a] + (c - 1) + dist[b][j]:
                    no_need = False
                    break
        if no_need: ans += 1
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dis = [[float("inf") for i in range(n)] for j in range(n)]
for i in range(n):
    dis[i][i] = 0
abc = []
for i in range(m):
    a, b, c = map(int, input().split())
    abc.append([a, b, c])
    dis[a-1][b-1] = c
    dis[b-1][a-1] = c
def warshall_floyd(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis1 = dis[i][j]
                dis2 = dis[i][k] + dis[k][j]
                dis[i][j] = min(dis1, dis2)
    return dis
data = warshall_floyd(dis)
ans = 0
for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    for j in range(n):
        if c + data[b-1][j] == data[a-1][j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = (int(x) for x in input().split())
graph = [[1000] * N for _ in range(N)]
before = []
for _ in range(M):
    a,b,c = (int(x) for x in input().split())
    before.append((a-1,b-1,c))
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

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

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

ans = 0
for x in before:
    if graph[x[0]][x[1]] != x[2]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq


def dijkstra(s):
    dist[s] = 0
    que = []
    heapq.heappush(que, (0, s))
    while len(que) != 0:
        p = heapq.heappop(que)
        v = p[1]
        if (dist[v] < p[0]):
            continue
        for e in graph[v]:
            if dist[e[0]] > dist[v] + e[1]:
                dist[e[0]] = dist[v] + e[1]
                prev[e[0]] = v
                heapq.heappush(que, (dist[e[0]], e[0]))


def get_path(t):
    path = []
    while t != -1:
        path.append(t)
        t = prev[t]
    path = path[::-1]
    return path


N, W = map(int, input().split())
graph = [[] for i in range(N)]
edges = {}
for i in range(W):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    graph[x].append((y, z))
    graph[y].append((x, z))
    edges[(x, y)] = True

for st in range(N):
    dist = [float("inf")] * N
    prev = [-1] * N
    dijkstra(st)
    for i in range(N):
        gp = get_path(i)
        for i in range(1, len(gp)):
            edges[(gp[i-1], gp[i])] = False

print(sum(edges.values()))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
inf = float("inf")
edges = [[inf]*n for _ in range(n)]
path = [[inf]*n for _ in range(n)]
edges_list = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a][b] = c
    edges[b][a] = c
    path[a][b] = c
    path[b][a] = c
    edges_list.append((a, b))

for i in range(n):
    path[i][i] = 0

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

count = 0
for a, b in edges_list:
    if path[a][b] < edges[a][b]:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import *
import numpy as np
N,M = map(int,input().split())
E = [list(map(int,input().split())) for m in range(M)]
G = np.zeros((N,N))
ans = 0

for a,b,c in E:
  G[a-1][b-1] = c
  G[b-1][a-1] = c

F = shortest_path(G).astype(int)
for a,b,c in E:
  if F[a-1][b-1]!=c:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        i -= 1
        j -= 1
        tree[i].append((k, j))
        tree[j].append((k, i))

    # dijkstra
    import heapq

    ans = 0
    for i in range(n):
        for j in tree[i]:
            seen = [0] * n
            goal = j[1]
            base = j[0]
            seen[i] = 1
            todo = []
            heapq.heapify(todo)
            for k in tree[i]:
                if k[0] < base and k != j:
                    heapq.heappush(todo, k)
            while len(todo) > 0:
                k = heapq.heappop(todo)
                if k[1] == goal:
                    if k[0] < base:
                        ans += 1
                    break
                seen[k[1]] = 1
                for l in tree[k[1]]:
                    if seen[l[1]] == 0 and k[0] + l[0] < base:
                        heapq.heappush(todo, (k[0] + l[0], l[1]))

    print(ans // 2)

main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        i -= 1
        j -= 1
        tree[i].append((k, j))
        tree[j].append((k, i))

    # dijkstra
    import heapq
    from numpy import zeros

    ans = 0
    for i in range(n):
        for j in tree[i]:
            seen = zeros(n)
            goal = j[1]
            base = j[0]
            seen[i] = 1
            todo = []
            heapq.heapify(todo)
            for k in tree[i]:
                if k[0] < base and k != j:
                    heapq.heappush(todo, k)
            while len(todo) > 0:
                k = heapq.heappop(todo)
                if k[1] == goal:
                    if k[0] < base:
                        ans += 1
                    break
                seen[k[1]] = 1
                for l in tree[k[1]]:
                    if seen[l[1]] == 0 and k[0] + l[0] < base:
                        heapq.heappush(todo, (k[0] + l[0], l[1]))

    print(ans // 2)

main()

Submission status: Accepted

Solution code:
import sys

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

memo = [[sys.maxsize]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
  memo[i][i] = 0

lst = []
for _ in range(M):
  a,b,c = map(int, input().split())
  memo[a][b] = c
  memo[b][a] = c
  lst.append((a,b,c))
  
for k in range(1,N+1):
  for i in range(1,N+1):
    for j in range(1,N+1):
      memo[i][j] = min(memo[i][j], memo[i][k] + memo[k][j])
      
cnt = 0
for a,b,c in lst:
  if memo[a][b] < c:
    cnt += 1
    
print(cnt)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        cost[i][i] = 0

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

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

    res = 0
    for d, x, y in edge:
        if cost[x][y] < d:
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
from heapq import heappush, heappop
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

V,E = map(int, readline().split())
edges = [[] for _ in range(V+1)]

INF = 10**31

for _ in range(E):
    x,y,t = map(int, readline().split())
    edges[x].append((t,y))
    edges[y].append((t,x))
    

def dijkstra(q,dist,prev):
    while q:
        cost, v_from = heappop(q)
        if dist[v_from] < cost:
            continue
        for _cost,v_to in edges[v_from]:
            newcost = cost+_cost
            if newcost < dist[v_to]:
                prev[v_to] = v_from
                dist[v_to] = newcost #最短経路用
                heappush(q,(newcost,v_to))

pp = []
for i in range(1,V+1): 
    for j in range(i+1,V+1):
        dist = [INF]*(V+1) #最短距離用
        dist[i] = 0 #最短経路用
        prev=[None]*(V+1) 
        q = [(0,i)]
        dijkstra(q,dist,prev)
        p = [j]
        while prev[p[-1]]!=None:
            x,y = p[-1],prev[p[-1]]
            if x > y:
                x,y = y,x
            pp.append((x,y))
            p.append(prev[p[-1]])

print(E - len(set(pp)))

Submission status: Accepted

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

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    import numpy as np    
    from scipy.sparse import csr_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    omat = csr_matrix((c, (a, b)), shape=(N+1, N+1), dtype=np.int32)
    smat = floyd_warshall(omat, directed=False)
    return ((smat-omat) < 0).sum()


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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))
    print(solve(N, M, a, b, c))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

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

d=[[float("inf")]*N for i in range(N)]
A=[]
for i in range(M):
  x,y,z=map(int, input().split())
  x-=1
  y-=1
  d[x][y]=z
  d[y][x]=z
  A.append((x,y,z))
  
for i in range(N):
  d[i][i]=0 
  
D=warshall_floyd(d)

ans=0
for x,y,z in A:
  if D[x][y]!=z:
    ans+=1
print(ans)

Submission status: Accepted

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

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    import numpy as np    
    from scipy.sparse import csr_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    omat = csr_matrix((c+c, (a+b, b+a)), shape=(N+1, N+1), dtype=np.int32)
    smat = floyd_warshall(omat)
    return ((omat-smat) > 0).sum() // 2


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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))
    print(solve(N, M, a, b, c))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
INF=10**20

def dijkstra(G, start = 0):
    d = [INF for i in range(len(G))]
    d[start] = 0
    prev = [0 for i in range(len(G))]
    
    que = []
    heappush(que, (0, start))

    while len(que) != 0:
        p = heappop(que)
        v = p[1]
        
        if d[v] < p[0]:
            continue
            
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                prev[u] = v
                heappush(que, (d[u], u))
    
    return d,prev

N,M=map(int,input().split())
G=[{} for _ in range(N+1)]

edgelist=[]
for i in range(M):
  a,b,c=map(int,input().split())
  G[a][b]=G[b][a]=c
  a,b=sorted([a,b])
  edgelist.append((a,b))
edgelist = set(edgelist)
  
shortest_edges=set()
for i in range(1,N+1):
  d,prev = dijkstra(G,i)
  for j in range(1,N+1):
    if j ==i:continue
    a,b = sorted([j,prev[j]])
    shortest_edges.add((a,b))
    
diff = edgelist.difference(shortest_edges)
print(len(diff))

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
N, M, *ABC = [int(_) for _ in open(0).read().split()]
ABC = np.array(ABC)
F = floyd_warshall(
    csr_matrix((ABC[2::3], (ABC[::3], ABC[1::3])), (N + 1, N + 1)), 0)
print(np.sum(F[ABC[::3], ABC[1::3]] != ABC[2::3]))

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,M = MI()


class WarshallFloyd():
    def __init__(self,N):  # Nは頂点の個数
        self.N = N
        self.d = [[float('inf')]*N for i in range(N)]  # d[i][j] = iからjへの最短距離,0-indexed
    def add(self,u,v,c,directed = False):
        if directed is False:  # 無向グラフの場合
            self.d[u][v] = c
            self.d[v][u] = c
        else:  # 有向グラフの場合
            self.d[u][v] = c
    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j],self.d[i][k] + self.d[k][j])
        return self.d


W = WarshallFloyd(N)
edges = [0]*M
for i in range(M):
    a,b,c = MI()
    W.add(a-1,b-1,c,directed=False)
    edges[i] = (a-1,b-1,c)
for i in range(N):
    W.add(i,i,0)

W.WarshallFloyd_search()

ans = 0
for i in range(M):
    a = 0
    for j in range(N):
        if W.d[edges[i][0]][edges[i][1]] == edges[i][2]:
            a = 1
    if a == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,M = MI()


class WarshallFloyd():
    def __init__(self,N):  # Nは頂点の個数
        self.N = N
        self.d = [[float('inf')]*N for i in range(N)]  # d[i][j] = iからjへの最短距離,0-indexed
    def add(self,u,v,c,directed = False):
        if directed is False:  # 無向グラフの場合
            self.d[u][v] = c
            self.d[v][u] = c
        else:  # 有向グラフの場合
            self.d[u][v] = c
    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j],self.d[i][k] + self.d[k][j])
        return self.d


W = WarshallFloyd(N)
edges = [0]*M
for i in range(M):
    a,b,c = MI()
    W.add(a-1,b-1,c,directed=False)
    edges[i] = (a-1,b-1,c)
for i in range(N):
    W.add(i,i,0)

W.WarshallFloyd_search()

ans = 0
for i in range(M):
    a = 0
    for j in range(N):
        if W.d[j][edges[i][1]] == W.d[j][edges[i][0]] + edges[i][2]:
            a = 1
    if a == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,M = MI()


class WarshallFloyd():
    def __init__(self,N):  # Nは頂点の個数
        self.N = N
        self.d = [[float('inf')]*N for i in range(N)]  # d[i][j] = iからjへの最短距離,0-indexed
    def add(self,u,v,c,directed = False):
        if directed is False:  # 無向グラフの場合
            self.d[u][v] = c
            self.d[v][u] = c
        else:  # 有向グラフの場合
            self.d[u][v] = c
    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j],self.d[i][k] + self.d[k][j])
        return self.d


W = WarshallFloyd(N)
edges = [0]*M
for i in range(M):
    a,b,c = MI()
    W.add(a-1,b-1,c,directed=False)
    edges[i] = (a-1,b-1,c)
for i in range(N):
    W.add(i,i,0)

W.WarshallFloyd_search()

ans = 0
for i in range(M):
    a = 0
    for j in range(N):
        for k in range(N):
            if W.d[j][k] == W.d[j][edges[i][0]] + edges[i][2] + W.d[edges[i][1]][k]:
                a = 1
    if a == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
g = [[] for _ 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))
vs = [[False]*n for _ in range(n)]
for i in range(n):
    ds = [-1]*n
    hq = [(0,i,None)]
    while hq:
        c,idx,v = heapq.heappop(hq)
        if ds[idx] != -1:
            if ds[idx] == c:
                vs[v[0]][v[1]] = True
            continue
        ds[idx] = c
        if v != None:
            vs[v[0]][v[1]] = True
        for j in g[idx]:
            if ds[j[0]] == -1:
                heapq.heappush(hq,(c+j[1],j[0],(idx,j[0])))
            elif ds[j[0]] == c+j[1]:
                vs[idx][j[0]] = True
res = 0
for i in range(n):
    for j in g[i]:
        if vs[i][j[0]] == False:
            res += 1
print(res//2)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = [[float('inf')]*n for i in range(n)]
u_s=[]
v_s=[]
w_s=[]
for _ in range(m):
    u, v, w = map(int, input().split())
    u_s.append(u-1)
    v_s.append(v-1)
    w_s.append(w)
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[i][i] = 0


def warshall_floyd(adj_m):
    # _dist[i][j] : i から j への最短距離
    _dist=adj_m
    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=warshall_floyd(graph)

ans=0
for i in range(m):
    if w_s[i]>dist[u_s[i]][v_s[i]]:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = [[float('inf')]*n for i in range(n)]
u_s=[]
v_s=[]
w_s=[]
for _ in range(m):
    u, v, w = map(int, input().split())
    u_s.append(u-1)
    v_s.append(v-1)
    w_s.append(w)
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[i][i] = 0


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

dist=warshall_floyd(graph)

ans=0
for i in range(m):
    if w_s[i]>dist[u_s[i]][v_s[i]]:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd

N,M = map(int,input().split())
check = dd(int)
edge = []
res = 0
dist = [[10**18]*N for _ in range(N)]
for i in range(M):
    p,q,c = map(int,input().split())
    dist[p-1][q-1] = c
    dist[q-1][p-1] = c
    edge.append((p-1,q-1,c))
    check[(max(p-1,q-1),min(p-1,q-1))] = 1
for i in range(N):
    dist[i][i] = 0

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

for now in edge:
    for s in range(N):
        for t in range(N):
            if dist[s][t] == dist[s][now[0]] + now[2] + dist[now[1]][t]:
                check[(max(now[0],now[1]),min(now[0],now[1]))] = 0
for v in check.items():
    res += v[1]
    #print(v[0])
print(res)

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 -= 1
    b -= 1
    A.append(a)
    B.append(b)
    C.append(c)
inf = 10**18
dist = [[inf]*N for i in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 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 C[i] > dist[A[i]][B[i]]:
        ans += 1

print(ans)

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:
        if c > G[a][b]:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()