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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

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

N,M = inputIL()


class WarshallFloyd():
  def __init__(self, N):
    self.N = N
    self.d = [[float("inf") for i in range(N)] for j in range(N)]
    self.prev = [[i for j in range(N)] for i in range(N)]
    for i in range(N):
      self.prev[i][i] = i

  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):
          if self.d[i][j] > self.d[i][k] + self.d[k][j]:
            self.d[i][j] = self.d[i][k] + self.d[k][j]
            if i!=j:
              self.prev[i][j] = self.prev[k][j]
          
    hasNegativeCycle = False
    for i in range(self.N):
      if self.d[i][i] < 0:
        hasNegativeCycle = True
        break
    for i in range(self.N):
      self.d[i][i] = 0
    return hasNegativeCycle, self.d

dic = set()  
graph = WarshallFloyd(N)
for _ in range(M):
  u, v, c = inputIL()
  dic.add((u-1,v-1))
  dic.add((v-1,u-1))
  graph.add(u-1,v-1,c)
graph.WarshallFloyd_search()

used = set()
for i in range(N):
  for j in range(i+1,N):
    now = j
    while now != i:
      prev = graph.prev[i][now]
      used.add((now,prev))
      used.add((prev,now))
      now = prev

print(len(dic-used)//2)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, m = map(int, readline().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]
abc = [list(map(int, readline().split())) for _ in range(m)]
for a, b, c in abc:
    graph[a][b] = c
    graph[b][a] = c
cost = floyd_warshall(csr_matrix(graph))
cnt = 0
for a, b, c in abc:
    if cost[a][b] < c:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import networkx as nx
import itertools

N, M = map(int, input().split())
G = nx.Graph()
G.add_weighted_edges_from([map(int, input().split()) for _ in range(M)])
S = nx.floyd_warshall(G)

ans = M
for i, j, d in G.edges(data=True):
    for s, t in itertools.combinations(G.nodes(), 2):
        if S[s][i] + d['weight'] + S[j][t] == S[s][t]:
            ans -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    root = [[] for _ in range(N)]
    for i in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c,i))
        root[b-1].append((a-1,c,i))

    rest = [1] * M
    q = []
    heapify(q)

    for i in range(N):
        node = [INF] * N
        heappush(q,(0,i,-1))
        while q:
            d,v,m = heappop(q)
            if node[v] < d: continue
            if m >= 0: rest[m] = 0
            for u,c,n in root[v]:
                if d + c < node[u]:
                    node[u] = d + c
                    heappush(q,(d+c,u,n))
    print(sum(rest))




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Used = [1] * M
Q = []

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

for i in range(N):
    now = (0, i)
    Seen = [-1] * N
    used = [-1] * N
    wait = []
    heapq.heappush(wait, now)
    Seen[i] = 0
    while len(wait) > 0:
        time, now = heapq.heappop(wait)
        for nex, cost, bridgenum in Edge[now]:
            if Seen[nex] == -1:
                Ne = (time + cost, nex)
                Seen[nex] = time + cost
                heapq.heappush(wait, Ne)
                used[nex] = bridgenum
            elif Seen[nex] > time + cost:
                Ne = (time + cost, nex)
                Seen[nex] = time + cost
                heapq.heappush(wait, Ne)
                used[nex] = bridgenum
    for j in range(N):
        if used[j] != -1:
            Used[used[j]] = 0
print(sum(Used))

Submission status: Accepted

Solution code:
import itertools
from scipy.sparse.csgraph import floyd_warshall

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

# Floyd-Warshallでよくやる初期化
dist = []
for i in range(N):
  tmp = []
  for _ in range(N):
    tmp.append(float('inf'))
  dist.append(tmp)
  dist[i][i] = 0  # ここがポイント

# 隣接行列を作る
a = []
b = []
c = []
for _ in range(M):
  x = list(map(int, input().split()))
  a.append(x[0] - 1)
  b.append(x[1] - 1)
  c.append(x[2])
  dist[a[-1]][b[-1]] = x[2]
  dist[b[-1]][a[-1]] = x[2]

# Floyd-Warshall
dist = floyd_warshall(dist)
dist = dist.astype(int).tolist()

# 集計
res = 0
for i in range(M):
  if c[i] > dist[a[i]][b[i]]:
    res += 1
    
print(res)

Submission status: Accepted

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

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

edges = []

d = [[float("inf")]*n for _ in range(n)]
for i in range(w):
    x,y,z = map(int, input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
    edges.append((x,y,z))

for i in range(n):
    d[i][i] = 0
# print("d",d)

csr = csr_matrix(d)
dp = floyd_warshall(csr)
ans = 0
# print("dp",dp)

for i, j, c in edges:
    # print(i,j,c)
    if dp[i,j] < c:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
class WarshallFloyd:
#O(V^3)で任意２頂点の最短距離
    def __init__(self,n,_first_index=0):
        self.v = n
        self._first_idx=_first_index
        self.d = [[1e100]*(n+_first_index) for _ in range(n+_first_index)]
        for i in range(n+_first_index):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        f=self._first_idx
        for k in range(f,self.v+f):
            for i in range(f,self.v+f):
                for j in range(f,self.v+f):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d
w=WarshallFloyd(n,1)
l=[]
for i in range(m):
    x,y,c=map(int,input().split())
    w.path(x,y,c)
    x,y=sorted([x,y])
    l.append([x,y,c])
d=w.build()
ans=0
for a,s,c in l:
    f=1
    for y in range(1,n+1):
        if d[y][s]==d[y][a]+c:f=0;break
    ans+=f
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import numpy as np

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

row,col,data = zip(*abc)
L = csr_matrix((data, (row,col)), shape=(n+1,n+1))
_,path = dijkstra(L,directed = False, return_predecessors = True)

s,e = np.where(path>0)
path_use = set(map(tuple,np.vstack([path[s,e],e]).T))

print( m - len(path_use)//2)

Submission status: Accepted

Solution code:
def main():
	n,m=map(int,input().split())
	inf=10**15
	dis=[[inf for _ in range(n)]for _ in range(n)]
	for i in range(n):
		dis[i][i]=0
	node=[]
	for i in range(m):
		a,b,c=map(int,input().split())
		dis[a-1][b-1]=c
		dis[b-1][a-1]=c
		node.append((a-1,b-1,c))
	for i in range(n):
		for j in range(n):
			for k in range(n):
				dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k])
	ans=0
	for x in node:
		f=0
		for i in range(n-1):
			if f:
				break
			for j in range(i+1,n):
				if dis[i][j]==dis[i][x[0]]+x[2]+dis[x[1]][j]:
					f=1
					break
				elif dis[i][j]==dis[i][x[1]]+x[2]+dis[x[0]][j]:
					f=1
					break
		if f==0:
			ans+=1
	print(ans)
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
'''
ダイクストラ法。
始点を固定した時にすべての頂点に対する最短経路を計算する。
O(|E|log|V|)でベルマンフォードより速いが、
負の辺が含まれる場合は使えない。

'''

import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        d:int
            cost
        directed:bool
            there is direction
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        """
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        Parameters
        ----------
        s:int
            始点

        Return
        ----------
        d:dict(int:int)
            shortest cost from start node to each node 
            {to : cost}

        prev:dict(int:int)
            previous node on the shortest path
            {from : to}
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        """
        Parameters
        ----------
        start:int
            start node
        goal:int
            goal node

        Return
        ----------
        ShortestPath:list(int)
            shortest path
        """
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]


'''
ABC051-D
N頂点M辺の重み付き無向連結グラフがあり、
頂点a_iから頂点b_iを重みc_iで結んでいる。
どの最短経路にも含まれない辺の数を求めよ。

term:
2<=N<=100
N-1<=M<=min(N(N-1)/2,1000)
1<=a_i,b_i<=N
1<=c_i<=10**3

input:
3 3
1 2 1
1 3 1
2 3 3

output:
    1
'''

N, M = map(int, input().split())
graph = Dijkstra()
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a, b, c, directed=False)

usedPaths = collections.defaultdict(set)
for i in range(1,N+1):
    for j in range(i+1, N+1):
        path = graph.getDijkstraShortestPath(i, j)
        if len(path) == 2:
            usedPaths[path[0]].add(path[1])
            usedPaths[path[1]].add(path[0])
        else:
            for idx, v in enumerate(path[:-1]):
                usedPaths[v].add(path[idx + 1])
                usedPaths[path[idx + 1]].add(v)

ans = M - sum([len(a) for a in list(usedPaths.values())])//2
print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    dp = [[float("inf")] * N for _ in range(N)]
    edges = list()
    for i in range(N):
        dp[i][i] = 0

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

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

    ans = 0
    for i, j, c in edges:
        if dp[i][j] < c:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, M = map(int, input().split())
    S = []

    d = [[float("inf")] * N for _ in range(N)]
    L = []
    for i in range(M):
        a, b, c = map(int, input().split())
        d[a - 1][b - 1] = c
        d[b - 1][a - 1] = c
        if a < b:
            L.append((a - 1, b - 1))
        else:
            L.append((b - 1, a - 1))
    for i in range(N):
        d[i][i] = 0
    L = set(L)

    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][j] > d[i][k] + d[k][j]:
                        d[i][j] = d[i][k] + d[k][j]
                        if i < j:
                            if (i, j) in L:
                                S.append((i, j))
                        else:
                            if (j, i) in L:
                                S.append((j, i))
        return d

    warshall_floyd(d)
    print(len(set(S)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

graph = [[] for _ in range(N)]
for a, b, c in X:
    graph[a - 1].append((b - 1, c))
    graph[b - 1].append((a - 1, c))


def dijkstra(s):
    inf = 10 ** 9 + 7
    d = [inf] * N
    d[s] = 0
    pq = []
    heappush(pq, (0, s))
    while pq:
        _, u = heappop(pq)
        for v, c in graph[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heappush(pq, (d[v], v))

    return d


dist = [dijkstra(s) for s in range(N)]
ans = [False] * M
for n, (a, b, c) in enumerate(X):
    for i in range(N):
        for j in range(N):
            ans[n] |= dist[i][j] == dist[i][a - 1] + c + dist[j][b - 1]

print(M - sum(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict
  
n,m = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(m)]
INF = 10 ** 18
d = [[INF] * n for i in range(n)]
for i in range(n):
  d[i][i] = 0
road = defaultdict(int)
for a,b,c in abc:
  a -= 1
  b -= 1
  road[(a, b)] = 1
  d[a][b] = c
  d[b][a] = 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]
        road[(i,j)] = 0
        road[(j,i)] = 0
ans = m - sum(road.values())
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import defaultdict
import sys
input = lambda: sys.stdin.readline().rstrip()
INF = 10**12
edges = defaultdict(lambda: defaultdict(lambda: INF))
n, m = map(int, input().split())
for i in range(m):
    a, b, c =map(int, input().split())
    edges[a-1][b-1] = (c, i)
    edges[b-1][a-1] = (c, i)

def dijkstra(s, n, w, cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    que = [[0, s]] # (dist, node_num)
    prev = {}
    heapify(que)
    while len(que) > 0:
        u_dist, u = heappop(que)
        #まだ使われてない頂点の中から最小の距離のものを探す
        for v in cost[u].keys():
            alt = d[u] + cost[u][v][0]
            edge_num = cost[u][v][1]
            if d[v] > alt:
                prev[v] = (u, edge_num)
                d[v] = alt
                heappush(que, [alt, v])
    cnt = defaultdict(int)
    for goal in range(s, n):
        if goal == s:
            continue
        u = goal
        while u != s:
            cnt[prev[u][1]] += 1
            u = prev[u][0]
    return cnt

ans = set()
cnt_paths = defaultdict(int)
for start in range(n-1):
    cnt = dijkstra(start, n, m, edges)
    for k, v in cnt.items():
        cnt_paths[k] += v
    ans = ans | set(cnt_paths.keys())
print(m - len(ans))

Submission status: Accepted

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

a = [0]*M
b = [0]*M
c = [0]*M

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

d = [[float("inf")]*N for i in range(N)]

for i in range(M):
    d[a[i]][b[i]] = c[i]
    d[b[i]][a[i]] = c[i]
    
for i in range(N):
    d[i][i] = 0

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

count = 0
for i in range(M):
    if d[a[i]][b[i]] < c[i]:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import copy
def warshall_floyd(d):
    cnt = 0
    d_first = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    for i in range(len(d)):
        for fir, rev in zip(d_first[i], d[i]):
            if (rev < fir) and fir != float('inf'):
                cnt += 1
    return cnt//2

if __name__ == '__main__':
    n,w = map(int,input().split()) #n:頂点数　w:辺の数

    d = [[float("inf")]*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
    for i in range(n):
        d[i][i] = 0 #自身のところに行くコストは０
    print(warshall_floyd(d))

Submission status: Accepted

Solution code:
import copy
n, m = map(int, input().split())
# 隣接行列
e = [[float('inf')]*n for i in range(n)]
for i in range(m):
    a, b,c = map(int, input().split())
    e[a-1][b-1]=c
    e[b-1][a-1]=c


ans=[[float('inf')]*n for i in range(n)]
d=copy.deepcopy(e)
# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
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 i==j or k==i or k==j:
                    continue
                if d[i][j]==float('inf') and (d[i][k]==float('inf') or d[k][j]==float('inf')):
                    continue
                else:
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j]=d[i][k]+d[k][j]

warshall_floyd(d)
x=0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float('inf'):
            if e[i][j]>d[i][j]:
                x+=1
print(x//2)

Submission status: Accepted

Solution code:
def resolve():
    from scipy.sparse.csgraph import shortest_path
    import scipy
    import numpy as numpy
    n, m = map(int, input().split())
    row = [None] * m
    col = row[:]
    data = row[:]
    for i in range(m):
        row[i], col[i], data[i] = map(int, input().split())
        row[i] -= 1
        col[i] -= 1
    a = scipy.sparse.csr_matrix((data, (row, col)), shape=(n, n)).toarray()
    s, p = shortest_path(a, return_predecessors=True, directed=False)
    l = [[True] * n for _ in range(n)]
    for start in range(n - 1):
        for goal in range(start + 1, n):
            path = get_path(start, goal, p)
            for i in range(len(path) - 1):
                l[path[i]][path[i + 1]] = False
                l[path[i + 1]][path[i]] = False
    ans = 0
    for i, j in zip(row, col):
        if l[i][j]:
            ans += 1
    print(ans)


def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


resolve()

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
INF = float('inf')
edges = []
for _ in range(M):
    edges.append(list(map(int,input().split())))
graph = [[INF if i != j else 0 for i in range(N)] for j in range(N)]
for i in range(M):
    a, b, c = edges[i]
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
ans = 0
for i in range(M):
    a, b, c = edges[i]
    if c != graph[a-1][b-1]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# solution

import numpy as np
import io
import math
from scipy.sparse.csgraph import shortest_path

nim,mike = map(int,input().split())

array = [[int(x) for x in input().split()] for _ in range(mike)]

graph = np.zeros((nim,nim)) # 0-indexed
for a,b,c in array:
  graph[a-1,b-1] = c

dist = shortest_path(graph,directed=False).astype(int)

answer = 0
for a,b,c in array:
  if c != dist[a-1,b-1]:
    answer += 1
print(answer)

Submission status: Accepted

Solution code:
def main():
    import sys
    # readline = sys.stdin.readline
    readlines = sys.stdin.readlines
    N, M = map(int, input().split())
    edge = []
    dp = [[10 ** 9] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0
    for s in readlines():
        a, b, c = map(int, s.split())
        a -= 1; b -= 1
        edge.append((a, b, c))
        dp[a][b] = c
        dp[b][a] = c
    
    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])

    cnt = 0
    for a, b, c in edge:
        if dp[a][b] < c:
            cnt += 1
    
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = float("inf")

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M


N, M, *ABC = map(int, open(0).read().split())

E = [[INF] * (N + 1) for _ in range(N + 1)]
for a, b, c in zip(*[iter(ABC)] * 3):
    E[a][b] = c
    E[b][a] = c

D = WarshallFloyd(E)

print(sum(D[a][b] < c for a, b, c in zip(*[iter(ABC)] * 3)))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
graph = [[float("inf")]*(n+1) for _ in range(n+1)]
for i in range(m):
  a,b,c = map(int,input().split())
  graph[a][b] = c
  graph[b][a] = c

    

def dijkstra(s,cost):
  d = [float("inf")]*(n+1)
  used = [False]*(n+1)
  d[s] = 0
  
  while True:
    v = -1
    for i in range(1,n+1):
      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(1,n+1):
      d[j] = min(d[j],d[v]+cost[v][j])
  return d

ans = 0
for i in range(1,n):
  d = dijkstra(i,graph)
  for j in range(i+1,n+1):
    if i == j:
      continue
    if graph[i][j] != float("inf") and graph[i][j] > d[j]:
      ans += 1
print(ans)

Submission status: Accepted

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

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])

n,m = map(int,input().split())
ABC = [tuple() for _ in range(m)]
wf = WarshallFloyd(n)
for i in range(m):
    a,b,c = map(int,input().split())
    wf.path(a-1,b-1,c)
    ABC[i] = (a-1,b-1,c)
ans = 0
wf.build()
for a,b,c in ABC:
    ans += (c > wf.d[a][b])
print(ans)

Submission status: Accepted

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

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

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

ans = M
for u, v, w in C:
    Flg = False
    for i in range(N):
        if(graph[i][v] + w == graph[i][u]):
            Flg = True
    if Flg:
        ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときは'inf')

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行ける
        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])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d

n,m = na()
g = WarshallFloyd(n)
abc = []

for i in range(m):
    a,b,c = na()
    g.add(a-1,b-1,c)
    abc.append([a-1,b-1,c])

dp = g.WarshallFloyd_search()

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

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc051/tasks/abc051_d
# 想定解法
# 最短距離の隣接行列Dが与えられたときに、edges[a, b]が最短経路に含まれるかどうか考える
# 2点s,tについて、最短距離であれば、D[s,t]=D[s,i]+edges[i,j]+D[j,t]を満たすi,jの組み合わせは最短経路辺である
# 5000*1000の探索なので間に合う

from scipy.sparse import csr_matrix  # 自分で配列を作ってからcsrに入れよう(lilに打ち込んでいくのは非常に遅い)

# ダイクストラ法 (正の単一始点最短経路) (全点間最短経路)
from scipy.sparse.csgraph import dijkstra
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


N, M = read_ints()
adj_mat = [[0] * N for _ in range(N)]
INF = 10 ** 9
from collections import defaultdict
from itertools import combinations
edges = defaultdict(lambda: INF)
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj_mat[a][b] = c
    adj_mat[b][a] = c
    edges[a, b] = c

adj_mat = csr_matrix(adj_mat, dtype='int')
D = dijkstra(adj_mat, directed=False)
# print(D)

# 最短経路じゃない辺全探索
edge_not_use = set()
# 辺を固定してs,tを全探索したほうが良さそう
# だけどこれはTLE(pythonが遅いせい)
# for (i, j), e in edges.items():
#     for s, t in combinations(range(N), 2):
#         d = D[s, t]
#         if d == D[s, i] + e + D[j, t] or d == D[t, i] + e + D[j, s]:
#             break
#     else:
#         edge_not_use.add((i, j))

# よく考えてみれば
# D[s,j]=D[s,i]+edges[i,j]のedges[i,j]は最短経路の一部になっているはず(s→jの最短経路の一部を成す)
# sを全探索するだけでいい

for (i, j), e in edges.items():
    for s in range(N):
        d = D[s, j]
        if d == D[s, i] + e or d == D[s, j] + e:
            break
    else:
        edge_not_use.add((i, j))


print(len(edge_not_use))
# print(edge_not_use)