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 copy import deepcopy


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

INF = 10**9
N, M = map(int, input().split())
G = [[INF] * N for _ in range(N)]
for i in range(N):
    G[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G[a][b] = G[b][a] = c
dist = deepcopy(G)
floyd_warshall(dist)
used = set()
for i in range(N-1):
    checked = set()
    for j in range(i+1, N):
        stack = [j]
        while stack:
            v = stack.pop()
            if v in checked:
                continue
            checked.add(v)
            for k in range(N):
                if v == k:
                    continue
                if G[k][v] == INF:
                    continue
                if dist[i][v] == dist[i][k] + G[k][v]:
                    stack.append(k)
                    used.add((k, v) if k < v else (v, k))
print(M - len(used))

Submission status: Accepted

Solution code:
import copy
n, m = map(int ,input().split())
inf = 10**8
edges = []
graph = [[inf for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    a,b,c = map(int, input().split())
    graph[a][b] = graph[b][a] = c
    edges.append([a,b,c])
ans = 0
for i in range(n+1):
    graph[i][i] = 0
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if graph[i][k] + graph[k][j] < graph[i][j]:
                graph[i][j] = graph[i][k] + graph[k][j]
for i in range(m):
    flag = False
    a,b,c = edges[i]
    for j in range(1,n+1):
        for k in range(1,n+1):
            if graph[j][a] + c + graph[b][k] == graph[j][k]:
                flag = True
    if flag:
        ans += 1
print(m-ans)

Submission status: Accepted

Solution code:
import heapq
def dijkstra(adj, start, goal=None):
    num = len(adj)          # グラフのノード数
    dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
    #prev = [None for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する
    dist[start] = 0
    # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
    q = []
    heapq.heappush(q, (0, start))  # 始点をpush
    while q:
        prov_cost, src = heapq.heappop(q)  # pop
        # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
        #if dist[src] < prov_cost:
            #continue
        # 他の頂点の探索
        for dest in range(num):
            cost = adj[src][dest]
            if cost != float('inf') and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost  # distの更新
                # キューに新たな仮の距離の情報をpush
                heapq.heappush(q, (dist[dest], dest))
                #prev[dest] = src                      # 前の頂点を記録
    return dist
n, m = map(int, input().split())
mat = [[float('inf')] * n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c
for i in range(n):
    mat[i][i] = 0
mat2 = []
for i in range(n):
    mat2.append(dijkstra(mat, i))
ans = 0
for i in range(n):
    for j in range(i, n):
        if mat[i][j] != float('inf') and mat[i][j] != mat2[i][j]:
            ans += 1
print(ans)
'''input
3 3
1 2 1
1 3 1
2 3 3
'''

Submission status: Accepted

Solution code:
import heapq


def dijkstra(adj, start, goal=None):
    num = len(adj)          # グラフのノード数
    dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
    prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

    dist[start] = 0
    # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
    q = []
    heapq.heappush(q, (0, start))  # 始点をpush

    while q:
        prov_cost, src = heapq.heappop(q)  # pop

        # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
        if dist[src] < prov_cost:
            continue

        # 他の頂点の探索
        for dest in range(num):
            cost = adj[src][dest]
            if cost != float('inf') and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost  # distの更新
                # キューに新たな仮の距離の情報をpush
                heapq.heappush(q, (dist[dest], dest))
                prev[dest] = src                      # 前の頂点を記録

    return dist


n, m = map(int, input().split())
mat = [[float('inf')] * n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c
for i in range(n):
    mat[i][i] = 0
mat2 = []
for i in range(n):
    mat2.append(dijkstra(mat, i))
ans = 0
for i in range(n):
    for j in range(i, n):
        if mat[i][j] != float('inf') and mat[i][j] != mat2[i][j]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline

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

used = [False] * (M + 1)


def dijkstra(start):
    inf = 10**18
    dist = [inf] * (N + 1)
    visited = [False] * (N + 1)
    dist[start] = 0
    visited[start] = False
    node = [(0, start, 0)]
    while node:
        d, s, e = heapq.heappop(node)
        if dist[s] < d:
            continue
        used[e] = True

        for t, cost, ind in edge[s]:
            if dist[t] > d + cost:
                dist[t] = d + cost
                heapq.heappush(node, (d + cost, t, ind))
    return


for i in range(1, N + 1):
    dijkstra(i)

ans = used.count(False)
print(ans)

Submission status: Accepted

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

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
ABC = np.array(read().split(), dtype=np.int64).reshape(m, 3)
A, B, C = ABC.T
csr = csr_matrix((C, (A, B)), shape=(n+1, n+1))
F = floyd_warshall(csr, directed=False)
ans = 0
for a, b, c in ABC:
  if c != F[a, b]:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m, = map(int,input().split())
E = [[] for i in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append((c,b))
    E[b].append((c,a))


def dijkstra(x):
    dis = [float("inf")]*n
    dis[x] = 0
    q = []
    heapq.heappush(q,(0,x))
    
    while q:
        cost,bef = heapq.heappop(q)

        if dis[bef] < cost:
            continue

        for ncost,nex in E[bef]:
            dist = ncost+cost

            if dist < dis[nex]:
                dis[nex] = dist
                heapq.heappush(q,(dist,nex))
    return dis

short = []
for i in range(n):
    short.append(dijkstra(i))
count = 0
for i in range(n):
    for dist,nex in E[i]:
        if short[i][nex] < dist:
            count += 1
print(count//2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_2
# CreatedDate:  2020-02-21 20:39:32 +0900
# LastModified: 2020-02-21 23:32:20 +0900
#


import heapq
def initial_signal(i,adj,N):
    d = [float("inf") for _ in range(N)]
    d[i] = 0
    Q = [(0,i)]
    return d,Q

def relax(n_cost, u, v, adj,d,Q):
    if d[v] > d[u]+n_cost:
        d[v]=d[u]+n_cost
        heapq.heappush(Q,(d[v],v))



def dijkstra(i,adj,N):
    d,Q = initial_signal(i,adj,N)
    while Q:
        cost, u = heapq.heappop(Q)
        for n_cost, v in adj[u]:
            relax(n_cost, u, v, adj, d, Q)
        
    return d



def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = map(int, input().split())
        adj[a-1].append((c,b-1))
        adj[b-1].append((c,a-1))
    shortest = []
    for i in range(N):
        shortest.append(dijkstra(i,adj,N))
    ans = 0
    for i in range(N):
        for cost, j in adj[i]:
            if cost>shortest[i][j]:
                ans+=1
    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
## https://atcoder.jp/contests/abc051/submissions/3281251
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]
    
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    
    while q:
        cost, cur_node = heapq.heappop(q)
        
        if dist[cur_node] < cost:
            continue
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist

def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]
    for i in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append((c, b))
        adj[b].append((c, a))
    shortest = []
    for i in range(n):
        shortest.append(dijkstra(adj, n, i))
    ans = 0
    for i in range(n):
        for cost, j in adj[i]:
            if cost > shortest[i][j]:
                ans += 1
    print(ans // 2)
                                                                                                                                                                                                     
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

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

es = []
for i in range(m):
    es.append(list(map(int, input().split())))

for (i, j, w) in es:
    d[i - 1][j - 1] = w
    d[j - 1][i - 1] = w


for k in range(n):
    for i in range(n):
        for j in range(n):
            l = d[i][k] + d[k][j]
            if d[i][j] > l:
                d[i][j] = l

c = 0
for (i, j, w) in es:
    if d[i - 1][j - 1] < w:
        c += 1

print(c)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path
N, M = map(int, input().split())
dic = [[0]*N for i in range(N)]
Els = []
for i in range(M):
  a, b, c = map(int, input().split())
  dic[a-1][b-1] = c
  dic[b-1][a-1] = c
  Els += [(a-1,b-1,c)]
d, p = shortest_path(dic, return_predecessors=True, method='D')

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

Submission status: Accepted

Solution code:
import numpy as np

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

d = np.ones((n, n)) * 1001

es = []
for i in range(m):
    es.append(list(map(int, input().split())))

for (i, j, w) in es:
    d[i - 1][j - 1] = w
    d[j - 1][i - 1] = w


for k in range(n):
    for i in range(n):
        for j in range(n):
            l = d[i][k] + d[k][j]
            if d[i][j] > l:
                d[i][j] = l

c = 0
for (i, j, w) in es:
    if d[i - 1][j - 1] < w:
        c += 1

print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
N, M = map(int, input().split())
dic = defaultdict(list)
Els = []
for i in range(M):
  a, b, c = map(int, input().split())
  dic[a-1] += [(b-1,c)]
  dic[b-1] += [(a-1, c)]
  Els += [(a-1,b-1,c)]

def dijkstra(s,e):
  dist = [float('inf')]*N
  dist[s] = 0
  q = [(0,s)]
  z = -1
  while q:
    c, v = heappop(q)
    if dist[v]<c:
      continue
    dist[v] = c
    for u, m in dic[v]:
      if dist[u]>dist[v]+m:
        dist[u] = dist[v]+m
        heappush(q,(dist[u],u))
        if u==e:
          z = v
  return z

ans = 0
for a, b, c in Els:
  if dijkstra(a,b)!=a:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq
class Graph():
    def __init__(self,vertex_num,node_num,naive_input,start_zero=True,direction=False):
        self.vertex_num=vertex_num
        self.node_num=node_num
        #nodeには入力時のインデックスも含む
        #[接続ノード , インッデクス]のarray
        node=[{} for _ in range(vertex_num)]
        for i in range(node_num):
            u,v,w=naive_input[i]
            if not start_zero:
                u-=1
                v-=1
            node[u][v]={"weight":w,"index":i}
            #node[v][u]={"weight":w,"index":i}
            if not direction:
                node[v][u]={"weight":w,"index":i}
                #node[u][v]["reverse"]={"weight":w,"index":i}
        self.node=node
        #それぞれの頂点の辺の数
        self.node_num_arr=list(map(lambda x:len(x),node))

    def djikstra(self,s=0):
        distance=[float("inf") for _ in range(self.vertex_num)]
        distance[s]=0
        #visitedにしたけど正確には訪問済みではなく最短距離確定済みが適切
        #いい名前教えて
        #visited_vertex=[False for _ in range(self.vertex_num)]
        #visited_vertex[s]=True
        visited_vertex={s}
        before_vertex=[float("inf") for _ in range(self.vertex_num)]
        node_index_arr=[float("inf") for _ in range(self.vertex_num)]
        while len(visited_vertex)<self.vertex_num:
            #will_visit_node=cal_will_visit_node(self.node,visited_vertex)
            will_visit_node=set()
            for now_node_num in visited_vertex:
                for next_node_num in self.node[now_node_num].keys():
                    if next_node_num in visited_vertex:
                        continue
                    will_visit_node.add(next_node_num)
                    next_node=self.node[now_node_num][next_node_num]
                    cal_d=distance[now_node_num]+next_node["weight"]
                    if cal_d<distance[next_node_num]:
                        distance[next_node_num]=cal_d
                        before_vertex[next_node_num]=now_node_num
                        node_index_arr[next_node_num]=next_node["index"]
                    #distance_vertex[distance[next_node_num]]=next_node_num
                    #heapq.heappush(min_distance_heap,distance[next_node_num])
            #add_vertex=distance_vertex[min_distance_heap[0]]
            add_vertex=[float("inf"),float("inf")]
            for i in will_visit_node:
                if distance[i]<add_vertex[1]:
                    add_vertex[0]=i
                    add_vertex[1]=distance[i]
            visited_vertex.add(add_vertex[0])
        return node_index_arr
        





n,m=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(m)]
G=Graph(n,m,a,start_zero=False)  
ans=[True for _ in range(m)]
for i in range(n):
    tmp=G.djikstra(i)
    for j in tmp:
        if j!=float("inf"):
            ans[j]=False

print(sum(ans))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np
N,M=map(int,input().split())
abc = [tuple(map(int,input().split())) for i in range(M)]
g = [[10**9]*N for i in range(N)]
for a,b,c in abc:
  a,b = a-1,b-1
  g[a][b]=c
  g[b][a]=c
g = np.array(g)
G,P=shortest_path(g,return_predecessors=True)
ans=set()
for i in range(N):
  for j in range(N):
    if P[i][j]>0 and (P[i][j],j) not in ans:
      ans.add((j,P[i][j]))

print(M-len(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy
import math
from collections import defaultdict

def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d
MOD = 10**9 + 7
INF = 10**10

def dijkstra(n, graph, start):
    visited = [0 for i in range(n)]
    cost = [INF for i in range(n)]
    parents = [[] for i in range(n)]
    visited[start] = 1
    cost[start] = 0
    # cur = start
    pq = []
    for g in graph[start]:
        heapq.heappush(pq, g)
    while(pq):
        nxt = heapq.heappop(pq)
        # print(nxt)
        # print(cost)
        tcos, cur, tdist = nxt
        if cost[tdist] == cost[cur] + tcos:
            parents[tdist].append(cur)
        elif cost[tdist] > cost[cur] + tcos:
            cost[tdist] = cost[cur] + tcos
            parents[tdist] = [cur]
            for g in graph[tdist]:
                heapq.heappush(pq, g)

    res = []
    # print(parents)
    for i, par in enumerate(parents):
        for ppar in par:
            res.append((i, ppar))

    return res


def main():
    n, m = getlist()
    graph = [[] for i in range(n)]

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

    cands = []

    for start in range(n):
        res = dijkstra(n, graph, start)
        # print(res)
        for re in res:
            if re[0] < re[1]:
                cands.append(re)
            else:
                cands.append((re[1], re[0]))

    print(m - len(list(set(cands))))

if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

INF = 10 ** 18
N, M = map(int, input().split())
d = [[INF for _ in range(N)] for _ in range(N)]
abc = []

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

wf = floyd_warshall(d)
cnt = 0
for i in range(M):
    if abc[i][2] > wf[abc[i][0]][abc[i][1]]:
        cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
E=[]
for i in range(M):
    a,b,c=map(int, input().split())
    E.append((a-1,b-1,c))
INF=1<<60

D=[[INF]*N for _ in range(N)]
for a,b,c in E:
    D[a][b]=D[b][a]=c
for z in range(N):
    for x in range(N):
        Dx=D[x]
        for y in range(N):
            Dx[y]=min(Dx[y], Dx[z]+D[z][y])

ans=M
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())
E=[[] for _ in range(N)]
for i in range(M):
    a,b,c=map(int, input().split())
    E[a-1].append((b-1,c,i))
    E[b-1].append((a-1,c,i))

ans=[1]*M

import heapq
def dijkstra(s):
    distance=[-1]*N
    parent_n=[-1]*N
    parent_e=[-1]*N
    distance[s]=0
    parent_n[s]=s
    q=[(0,s)]
    while q:
        nc,n=heapq.heappop(q)
        for to,c,eid in E[n]:
            if distance[to]<0 or nc+c<distance[to]:
                distance[to]=nc+c
                parent_n[to]=n
                parent_e[to]=eid
                heapq.heappush(q,(nc+c,to))
    checked=[False]*N
    checked[s]=True
    for i in range(N):
        if checked[i]: continue
        n=i
        while n!=s:
            checked[n]=True
            ans[parent_e[n]]=0
            n=parent_n[n]

for i in range(N): dijkstra(i)
print(sum(ans))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra as di

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

g = di(grid)
ans = 0
for a,b,c in edges:
    if g[a][b] < c:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]
ms = []
for i in range(N):
    dp[i][i] = 0

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

g = copy.deepcopy(dp)

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min([dp[i][j], dp[i][k]+dp[k][j]])

# 全頂点でmが使われたかどうか
ans = M
for m in ms:
    a, b, c = m
    for n in range(N):
        if dp[n][b] == (dp[n][a]+c):
            ans -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
N, M = map(int, input().split())

graph = [[float('infinity')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c
ans = 0
# 頂点g -> eまでの最短経路コストと、その経路を記録する

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

original = deepcopy(graph)

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

warshall_floyd(graph, N)

ans = 0
for i in range(N):
    for j in range(i):
        if original[i][j] != float('infinity') and graph[i][j] != original[i][j]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
INF = 10**10
N,M=map(int,input().split())
e=[]
w=[[INF for j in range(N)]for i in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    w[a-1][b-1]=c
    w[b-1][a-1]=c
    e.append((a-1,b-1,c))

class lheapq():
#最小値を取り出す優先度付きキュー
    def __init__(self,p):
        self.l = []
        if p:
            for sp in p:
                self.heappush(sp)

    def heappush(self,a):
        n=len(self.l)
        self.l.append(a)
        t = n
        while t != 0:
            if self.l[t][1] < self.l[(t-1)//2][1]:
                self.l[t],self.l[(t-1)//2] = self.l[(t-1)//2],self.l[t]
                t = (t-1)//2
            else:break

    def heappop(self):
        n=len(self.l)
        if n == 0:
            return (-1,0)
        if n == 1:
            return self.l.pop()
        ret = self.l[0]
        self.l[0] = self.l.pop()
        n -= 1
        t = 0
        while t<n:
            child1 = t*2+1
            child2 = t*2+2
            if child1 >= n:
                break
            elif child2 >= n:
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t],self.l[child1] = self.l[child1],self.l[t]
                    t = child1
                else:break
            else:
                if self.l[child2][1] < self.l[child1][1]:
                    child1,child2 = child2,child1
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t],self.l[child1] = self.l[child1],self.l[t]
                    t = child1
                elif self.l[t][1] > self.l[child2][1]:
                    self.l[t],self.l[child2] = self.l[child2],self.l[t]
                    t = child2
                else:break
        return ret
    
    def isnotblank(self):
        if self.l:return True
        else:return False

def dijkstra(s,g,N,e):
    INF =10**10
    res = [INF for _ in range(N)]
    q=lheapq([(s,0)])
    while q.isnotblank():
        while q.isnotblank():
            des,dis = q.heappop()
            if res[des] == INF:
                res[des] = dis
                break
        for se in e[des]:
            if res[se[0]] == INF:
                q.heappush((se[0],se[1]+res[des]))
    return res[g]

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

res = 0
for i in range(M):
    g=[[] for _ in range(N)]
    for j in range(M):
        if j!=i:
            a,b,c = e[j][0],e[j][1],e[j][2]
            g[a].append((b,c))
            g[b].append((a,c))
    a,b,c = e[i][0],e[i][1],e[i][2]
    if c != w[a][b] and dijkstra(a,b,N,g) == w[a][b]:
        res += 1

print(res)

Submission status: Accepted

Solution code:
from itertools import combinations
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
n,m = map(int,input().split())
abc = [list(map(int,input().split())) for i in range(m)]
abc = [[abc[i][0]-1,abc[i][1]-1,abc[i][2]] for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b,c in abc:
  graph[a].append((b,c))
  graph[b].append((a,c))
v1,v2,edge = zip(*abc)
csr = csr_matrix((edge,(v1,v2)),shape = (n,n))
dist = floyd_warshall(csr, directed = False)
ans = 0
for i,j in combinations(range(n),2):
  fs1,fs2 = zip(*graph[i])
  if j in fs1:
    x = fs1.index(j)
    if fs2[x] > dist[i][j]:
      ans += 1
print(ans)

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    dist = [[float('inf') for i in range(N)] for j in range(N)]
    
    r = [[-1 for i in range(N)] for j in range(N)]
    
    for i in range(N): dist[i][i] = 0
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1; b -= 1
        dist[a][b] = c
        dist[b][a] = c
        
        r[a][b] = i
        r[b][a] = i
        
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dist[i][j] > dist[i][k]+dist[k][j]:
                    dist[i][j] = dist[i][k]+dist[k][j]
                    r[i][j] = r[k][j]
        
    ans = set()    
    for a in r: ans.update(set(a))    
    print(M-len(ans)+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.stdin.readline

def main():
    N, M = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    INF = float("inf")
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    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 = M - sum(any(D[i][a-1] + c == D[i][b-1] for i in range(N)) for a, b, c in ABC)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7


def main():
    # sys.stdin = open("sample.txt")
    N, M = Scanner.map_int()

    class Edge():
        def __init__(self, a, b, c):
            self.from_ = a
            self.to_ = b
            self.cost_ = c
    edges = [] * M
    for _ in range(M):
        a, b, c = Scanner.map_int()
        a -= 1
        b -= 1
        edges.append(Edge(a, b, c))
    d = [[int(1e09) for _ in range(N)] for _ in range(N)]
    for e in edges:
        d[e.from_][e.to_] = e.cost_
        d[e.to_][e.from_] = e.cost_
    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][j], d[i][k] + d[k][j])
    visited = [False] * M
    for s in range(N):
        for i, e in enumerate(edges):
            if d[s][e.from_] + e.cost_ == d[s][e.to_]:
                visited[i] = True
            if d[s][e.to_] + e.cost_ == d[s][e.from_]:
                visited[i] = True
    print(visited.count(False))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

mp = [[100000 for i in range(N)] for j in range(N)]
mp2 = []
for i in range(M):
  a,b,c = map(int, input().split())
  mp[a-1][b-1] = c
  mp[b-1][a-1] = c
  mp2.append([a,b,c])
  
D = shortest_path(np.array(mp))

ans = [1 for i in range(M)]
for i,edge in enumerate(mp2):
  #print("{} {}".format(D[edge[0]-1, edge[1]-1], edge[2]))
  if D[edge[0]-1, edge[1]-1] >= edge[2]:
    ans[i] = 0
    
print(sum(ans))