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:
#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, s, t, w):
        self.E[s].append([t, w])
        self.E[t].append([s, w])


def shortestPath(g: Graph, s: int):
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):

    g = Graph(N)
    flag = {}
    for aa, bb, cc in zip(a, b, c):
        g.add_edge(aa-1, bb-1, cc)

        if aa > bb:
            aa, bb = bb, aa
        flag[(aa-1, bb-1)] = False

    for i in range(N-1):
        dist, prev = shortestPath(g, i)

        for j, p in enumerate(prev):
            if p == None:
                continue
            a, b = p, j
            if b < a:
                a, b = j, p
            flag[(a, b)] = True
    tot = 0
    for k in flag:
        if flag[k] == False:
            tot += 1
    print(tot)
    return


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))
    solve(N, M, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

def dijkstra(i, V, E, INF=1e9):
    D = [INF for v in V]
    D[i] = 0
    Q = [(d, v) for v, d in enumerate(D)]
    heapq.heapify(Q)
    prev = [None for v in V]

    while len(Q) > 0:
        du, u = heapq.heappop(Q)
        for v, (duv, *_) in E[u].items():
            dv = du + duv
            if D[v] > dv:
                D[v] = dv
                prev[v] = u
                heapq.heappush(Q, (dv, v))
    return prev

def count_path(prev, E):
    x = [(i, p) for i, p in enumerate(prev)]
    while len(x) > 0:
        i, p = x.pop()
        if p is not None:
            E[i][p][-1] += 1
            E[p][i][-1] += 1
            x.append((p, prev[p]))
    return E

n, m = map(int, input().split())
E_list = [list(map(int, input().split())) for _ in range(m)]
E = defaultdict(dict)
for j in range(m):
    a, b, c = E_list[j]
    E[a][b] = [c, 0]
    E[b][a] = [c, 0]
V = list(range(n + 1))

for i in range(1, n + 1):
    prev = dijkstra(i, V, E)
    E = count_path(prev, E)

ans = 0
for v1 in E.values():
    for v2 in v1.values():
        ans += (v2[-1] == 0)
print(ans // 2)

Submission status: Accepted

Solution code:
N,M=[int(x) for x in input().split()]
INF=1000000000000000
adj=[[INF for i in range(N+1)] for j in range(N+1)]

for i in range(N+1):
	adj[i][i]=0
	
A=[]
B=[]
C=[]
ans=M

for i in range(M):
	a,b,c=[int(x) for x in input().split()]
	adj[a][b]=min(adj[a][b],c)
	adj[b][a]=min(adj[b][a],c)
	A.append(a)
	B.append(b)
	C.append(c)

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


for i in range(M):
	temp=1
	for j in range(1,N+1):
		if adj[j][A[i]]+C[i]==adj[j][B[i]]:
			temp=0
	if temp==0:
		ans-=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
inf=100000000
wf=[[inf]*n for i in range(n)]
wf_sub=[[inf]*n for i in range(n)]
for i in range(n):
    wf[i][i]=0
    wf_sub[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    wf[a-1][b-1]=c
    wf_sub[a-1][b-1]=c
    wf[b-1][a-1]=c
    wf_sub[b-1][a-1]=c
'''
for i in range(n):
    print(wf[i])
for i in range(n):
    print(wf_sub[i])
'''

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])
cnt=0
for i in range(n):
    for j in range(n):
        if wf_sub[i][j]!=0 and wf_sub[i][j]!=inf:
            if wf[i][j]!=wf_sub[i][j]:
                cnt+=1

'''
for i in range(n):
    print(wf[i])
for i in range(n):
    print(wf_sub[i])
'''

print(cnt//2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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
inf=float("inf")
n,m=map(int,input().split())
G=[[inf]*n for _ in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
#print(G)
from copy import deepcopy
H=deepcopy(G)
#print(H)
H=warshall_floyd(H)
#print(G,H)
cnt=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if G[i][j]==inf:
            continue
        if G[i][j]!=H[i][j]:
            cnt+=1
print(cnt//2)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split()))for i in range(m)]
dist=[[1<<29]*n for i in range(n)]
for i in range(n): dist[i][i]=0
for a in l:
  dist[a[0]-1][a[1]-1] = min(dist[a[0]-1][a[1]-1],a[2])
  dist[a[1]-1][a[0]-1] = min(dist[a[1]-1][a[0]-1],a[2])
# print(dist)
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# 経路復元
ans=m
for a in l:
  flag=False
  for j in range(n): 
    if dist[j][a[0]-1]+a[2]==dist[j][a[1]-1]: flag=True
  if flag: ans-=1
print(ans)

Submission status: Accepted

Solution code:
# ABC051 D - Candidates of No Shortest Paths
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
def WF():
    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])

n,m=nm()
aa=[]
bb=[]
cc=[]
d=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    aa.append(a)
    bb.append(b)
    cc.append(c)
for i in range(n):
    for j in range(n):
        if i==j:
            d[i][j]=0
        else:
            d[i][j]=10**5

for i in range(m):
    d[aa[i]][bb[i]]=min(d[aa[i]][bb[i]],cc[i])
    d[bb[i]][aa[i]]=min(d[bb[i]][aa[i]],cc[i])
WF()

ans=m
for i in range(m):
    short=False
    for j in range(n):
        if d[j][aa[i]]+cc[i]==d[j][bb[i]]:
            short=True
    if short:
        ans-=1
print(ans)

Submission status: Accepted

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

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
edges = [rl() for _ in range(M)]
graph = np.zeros((N, N))

for a, b, c in edges:
    graph[a-1, b-1] = c

dist = shortest_path(graph, directed=False).astype(int)
answer = 0
for a, b, c in edges:
    if c != dist[a-1, b-1]:
        answer += 1

print(answer)
#05

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def dijkstra(start):
    INF = 10 ** 5
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start)]
    while que:
        # (d, v) はdが現在の最小の交通費、vが現在の場所
        d, v = heappop(que)
        # 今より安い交通費で既に来たことがある場合、continue
        if dist[v] < d:
            continue
        for next_city, cost in edges[v].items():
            # modeによって円かスヌークを使うか選ぶ
            d1 = d + cost
            # 次の場所の交通費より安くなる場合は、データを更新
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    return dist

N, M = rl()
INF = 10 ** 5
edges = [{} for _ in range(N+1)]
for _ in range(M):
    a, b, c = rl()
    edges[a][b] = c
    edges[b][a] = c

answer = 0
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if j not in edges[i]:
            continue
        A = dijkstra(i)
        if A[j] < edges[i][j]:
            answer += 1
            edges[i].pop(j)
            edges[j].pop(i)

print(answer)
# 00

Submission status: Accepted

Solution code:
MAX_D = 10**9
def solve():
    N,M = map(int, input().split())
    d = [[MAX_D]*N for _ in range(N)]
    edges = [[False]*N for _ in range(N)]
    base_edge = {}
    for _ in range(M):
        a,b,c = map(int, input().split())
        edges[a-1][b-1] = True
        edges[b-1][a-1] = True
        d[a-1][b-1] = c
        d[b-1][a-1] = c
        base_edge[(a-1,b-1)] = c
        base_edge[(b-1,a-1)] = c
        
    # ワーシャルフロイド法
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i != j and d[i][j] > d[i][k]+d[k][j]:
                    # print(i+1,k+1,j+1, d[i][j], d[i][k], d[k][j])
                    edges[i][j] = False
                    if (i,k) in base_edge and base_edge[(i,k)] == d[i][k]: edges[i][k] = True
                    if (k,j) in base_edge and base_edge[(k,j)] == d[k][j]: edges[k][j] = True
                    d[i][j] = d[i][k]+d[k][j]
                    
    # print(edges)
    print(M - sum(map(sum, edges))//2)
    
solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split(' '))
graph = [[float('inf') for _ in range(N)] for _ in range(N)]

edges = [list(map(int, input().split(' '))) for _ in range(M)]
for a, b, c in edges:
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = 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 a, b, c in edges:
    a -= 1
    b -= 1
    if graph[a][b] < c:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def warshall_floyd(N: int, graph: list) -> list:
    """ ワーシャルフロイド(頂点数, 隣接行列(0-indexed)) """
    from copy import deepcopy

    res = deepcopy(graph)
    for i in range(N):
        # 始点 = 終点、は予め距離0にしておく
        res[i][i] = 0
    # 全頂点の最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for i in range(N):
        if res[i][i] < 0:
            return []
    return res

N, M = MAP()
G = list2d(N, N, INF)
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    G[a][b] = c
    G[b][a] = c

wf = warshall_floyd(N, G)

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        # 辺があって、最短経路より長いなら使わない
        if G[i][j] != INF and G[i][j] > wf[i][j]:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
INF = 10**9
D = [[INF ]*N for _ in range(N)]
P = [[None]*N for _ in range(N)]
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    if a>b: a,b = b,a
    D[a-1][b-1] = D[b-1][a-1] = c
    P[a-1][b-1] = P[b-1][a-1] = (a-1)*N+b-1

for k in range(N):
    for i in range(N):
        for j in range(i+1, N):
            Dikj = D[i][k] + D[k][j]
            if D[i][j] > Dikj:
                D[i][j] = D[j][i] = Dikj
                P[i][j] = P[j][i] = (P[i][k], P[k][j])

E = set()
for i in range(N):
    for j in range(i+1, N):
        queue = [P[i][j]]
        while queue:
            queue_new = []
            for q in queue:
                if type(q) is tuple:
                    for x in q:
                        queue_new.append(x)
                else:
                    E.add(q)
            queue = queue_new

print(M-len(E))

Submission status: Accepted

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

INF = 10 ** 15
WF = [[INF for _ in range(N + 1)] for _ in range(N + 1)]

for a, b, c in ABC:
  WF[a][b] = c
  WF[b][a] = c
for k in range(1, N + 1):
  for i in range(1, N + 1):
    for j in range(1, N + 1):
      WF[i][j] = min(WF[i][j], WF[i][k] + WF[k][j])

answer = 0
for a, b, c in ABC:
  if WF[a][b] < c:
    answer += 1
print(answer)

Submission status: Accepted

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

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

l = np.array([[float("inf") for i in range(n)] for j in range(n)])
from collections import defaultdict
ans = defaultdict(int)
for _ in range(m):
   a,b,c = map(int,input().split())
   l[a-1][b-1] = c
   l[b-1][a-1] = c
   if a > b:
      ans[(b,a)] = 1
   else:
      ans[(a,b)] = 1

d, p = shortest_path(l, return_predecessors=True)


for pp in p:
   for idx, ppp in enumerate(pp):
      if idx < ppp:
         ans[(idx+1,ppp+1)] = 0
      else:
         ans[(ppp+1,idx+1)] = 0
print(sum(ans.values()))

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):  # デフォルトの距離は1
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法 (二分ヒープ) による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):  # graph: Graphオブジェクト, start: 始点のIndex
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # そのノードまでの最短経路を定義した時、どのノードから来たのかを記録する
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))  # そのノードまでの仮の最短距離, ノードのIndex
        # 本当の最短距離はself.distに格納する
        while self.Q:
            # 距離が最小であるものをキューから取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:  # 仮の距離より短い距離が正式に求まっているならスルー
                continue
            for v, weight in self.g[u]:  # 対象のノードに隣接しているノードに対して操作を行う, 始点はu
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))  # 更新された仮の距離, ノード

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:  # startノードはprevを持たないからこの条件でよい
            path.append(node)
            node = self.prev[node]
        return path[::-1]  # 逆順にして返す


N, M = map(int, input().split())
g = Graph()
visited_edges = {}
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g.add_edge(a, b, c)
    g.add_edge(b, a, c)
    visited_edges[(a, b)] = False
    visited_edges[(b, a)] = False

for i in range(N):  # 始点
    shortest = Dijkstra(g, i)
    for j in range(i+1, N):  # 終点
        paths = shortest.shortest_path(j)
        for k in range(len(paths)-1):
            visited_edges[(paths[k], paths[k+1])] = True
            visited_edges[(paths[k+1], paths[k])] = True
print(M - sum(visited_edges.values())//2)

Submission status: Accepted

Solution code:
from scipy.sparse import*
n,_,*L=map(int,open(0).read().split())
s=csgraph.floyd_warshall(csr_matrix((L[2::3],(L[::3],L[1::3])),[n+1]*2),0)
print(sum(s[f,t]<c for f,t,c in zip(*[iter(L)]*3)))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
n,m,*L=map(int,open(0).read().split())
s=floyd_warshall(csr_matrix((L[2::3],(L[::3],L[1::3])),(n+1,n+1)),0)
ans=0
for f,t,c in zip(*[iter(L)]*3):ans+=s[f,t]<c
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
inf = float("inf")
dist = [[inf for _ in range(N)] for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

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

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

ans = M
for a, b, c in T:
    check = False
    for i in range(N):
        if dist[i][a] + c == dist[i][b]:
            check = True
    if check:
        ans -= 1
print(ans)

Submission status: Accepted

Solution code:
class DirectedEdge(object):
    def __init__(self, v, w, weight, id):
        self.v = v
        self.w = w
        self.weight = weight
        self.id = id

    def __str__(self):
        return "[{} -> {}: {}]".format(self.v, self.w, self.weight)

    def edge_from(self):
        return self.v

    def edge_to(self):
        return self.w

    def get_weight(self):
        return self.weight

    def get_id(self):
        return self.id



class EdgeWeightedDigraph(object):
    def __init__(self, vertex_size):
        self.VERTEX_SIZE = vertex_size
        self.adj = [set() for x in range(self.get_vertex_size())]

    def get_vertex_size(self):
        return self.VERTEX_SIZE

    def add_edge(self, edge):
        v = edge.edge_from()
        self.adj[v].add(edge)

    def get_adj(self, v):
        res = set()
        for edge in self.adj[v]:
            res.add(edge)
        return res


class IndexMinPQ(object):
    def __init__(self, size):
        self.keys = [None for x in range(size + 1)]  # key を格納
        self.pq = [None for x in range(size + 1)]    # tree 構造を形成する. key の id を格納

        self.qp = [None for x in range(size + 1)]

        self.n = 0

    def contains(self, i):
        if self.qp[i] is None:
            return False
        else:
            return True

    def is_empty(self):
        return self.n == 0

    def size(self):
        return self.n

    def decrease_key(self, i, key):
        self.keys[i] = key
        self._swim(self.qp[i])

    def insert(self, i, key):
        tail = self.n + 1
        self.pq[tail] = i
        self.qp[i] = tail
        self.keys[i] = key

        self._swim(tail)

        self.n += 1

    def _swim(self, i):
        while i != 1:
            p = self._get_parent_pos(i)
            if not self._is_less(p, i):
                self._exch(p, i)
                i = p
            else:
                break

    def del_min(self):
        head = self.pq[1]

        self.pq[1] = None
        self.keys[head] = None
        self.qp[head] = None

        self._exch(1, self.n)

        self.n -= 1
        self._sink(1)

        return head

    def _sink(self, i):
        while self._get_left_child_pos(i) <= self.n:
            left = self._get_left_child_pos(i)
            right = left + 1

            child = left
            if not left == self.n and not self._is_less(left, right):
                child = right

            if not self._is_less(i, child):
                self._exch(i, child)
                i = child
            else:
                break

    def _is_less(self, a, b):
        a_id = self.pq[a]
        b_id = self.pq[b]
        return self.keys[a_id] < self.keys[b_id]

    def _get_parent_pos(self, i):
        return i // 2

    def _get_left_child_pos(self, i):
        return i * 2

    def _exch(self, a, b):
        swap = self.pq[a]
        self.pq[a] = self.pq[b]
        self.pq[b] = swap

        if self.pq[a] is not None:
            self.qp[self.pq[a]] = a
        if self.pq[b] is not None:
            self.qp[self.pq[b]] = b


class DijkstraShortestPath(object):
    def __init__(self, edge_weighted_digraph, source):
        self.digraph = edge_weighted_digraph
        self.source = source

        self.edge_to = [None for x in range(self.digraph.get_vertex_size())]
        self.dist_to = [float("infinity") for x in range(self.digraph.get_vertex_size())]
        self.ipq = IndexMinPQ(self.digraph.get_vertex_size())

        self.dist_to[source] = 0.0
        self.ipq.insert(source, self.dist_to[source])

        while not self.ipq.is_empty():
            v = self.ipq.del_min()
            for edge in self.digraph.get_adj(v):
                self._relax(edge)

    def _relax(self, edge):
        v = edge.edge_from()
        w = edge.edge_to()
        if self.dist_to[v] + edge.get_weight() < self.dist_to[w]:
            self.dist_to[w] = self.dist_to[v] + edge.get_weight()
            self.edge_to[w] = edge

            if self.ipq.contains(w):
                self.ipq.decrease_key(w, self.dist_to[w])
            else:
                self.ipq.insert(w, self.dist_to[w])

    def has_path_to(self, v):
        return self.dist_to[v] < float("infinity")

    def path_to(self, v):
        path = []
        while self.edge_to[v] is not None:
            edge = self.edge_to[v]
            path.append(edge)
            v = edge.edge_from()
        return path


def solve():
    N, M = map(int, input().split())
    ABC = []
    for _ in range(M):
        ABC.append(tuple(map(int, input().split())))

    edges = []
    G = EdgeWeightedDigraph(N + 1)
    for a, b, c in ABC:
        edge_a = DirectedEdge(int(a), int(b), float(c), (a, b))
        edge_b = DirectedEdge(int(b), int(a), float(c), (a, b))

        G.add_edge(edge_a)
        G.add_edge(edge_b)

        edges.append((a, b))

    founds = set()
    for s in range(1, N + 1):
        sp = DijkstraShortestPath(G, s)
        for v in range(1, N + 1):
            if not v == s:
                for e in sp.path_to(v):
                    # print(s, v, e)
                    founds.add(e.get_id())

    ans = len(edges) - len(founds)

    return ans


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

Submission status: Accepted

Solution code:
# ワーシャルフロイド法
n,w = map(int,input().split()) #n:頂点数　w:辺の数

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

# 入力の辺リスト
e_list = []
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
    # 入力の辺リストに追加
    e_list.append([x-1,y-1,z])
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
    
#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])

# 移動コスト表示
#print(d)
##############################

# 辺の数から使用済みの数を引く
ans = w
for x, y, z in e_list:
    # dにx,y,z の情報が残っていたら利用されている
    if d[x][y] == z:
        ans -= 1
        
print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 9

n, m = map(int, input().split())
a = [[INF] * n for _ in range(n)]
e = [None] * m
for i in range(n): a[i][i] = 0
for i in range(m):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    e[i] = (u, v, w)
    a[u][v] = w
    a[v][u] = w
for k in range(n):
    for i in range(n):
        for j in range(n):
            a[i][j] = min(a[i][j], a[i][k] + a[k][j])
c = 0
for u, v, w in e:
    if a[u][v] != w: c += 1
print(c)

Submission status: Accepted

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

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m = I[:2]
a, b, c = I[2:].reshape(m, 3).T
a -= 1; b -= 1
graph = np.zeros((n, n))
graph[a, b] = c

def main():
    dist = floyd_warshall(csgraph=csr_matrix(graph), directed=False)
    bl =  (dist[:, a] == dist[:, b] + c) | (dist[:, b] == dist[:, a] + c)
    res = np.any(bl, axis=0)
    ans = m - np.count_nonzero(res)
    return ans

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

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

INF = 10 ** 7

n, m = map(int, sys.stdin.readline().split())
abc = map(int, sys.stdin.read().split())
abc = zip(*[abc] * 3)
graph = [[] for _ in range(n)]
for a, b, c in abc:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

def dijkstra(v):
    used_edges = [set() for _ in range(n)]
    hq = []
    heappush(hq, (0, v, None))
    dist = [INF] * n
    parents = [set() for _ in range(n)]
    while hq:
        d, cur, prev = heappop(hq)
        if dist[cur] != INF:
            if d == dist[cur]:
                parents[cur].add(prev)
                used_edges[cur] |= used_edges[prev]
                if prev < cur:
                    used_edges[cur].add((prev, cur))
                else:
                    used_edges[cur].add((cur, prev))
            continue   
        
        dist[cur] = d
        if cur != v:
            used_edges[cur] |= used_edges[prev]
            parents[cur].add(prev)
            if prev < cur:
                used_edges[cur].add((prev, cur))
            else:
                used_edges[cur].add((cur, prev))

        for (u, c) in graph[cur]:
            if u in parents[cur] or parents[u]:
                continue
            nex = u
            heappush(hq, (d+c, nex, cur))

    res = set()
    for i in range(n):
        res |= used_edges[i]
    return res

def main():
    res = set()
    for v in range(n):
        res |= dijkstra(v)
    
    ans = m - len(res)
    return ans

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

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

INF = 10 ** 7

n, m = map(int, sys.stdin.readline().split())
abc = map(int, sys.stdin.read().split())
abc = zip(*[abc] * 3)
graph = [[] for _ in range(n)]
for a, b, c in abc:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

def dijkstra(v):
    used_edges = [set() for _ in range(n)]
    hq = []
    heappush(hq, (0, v, None))
    dist = [INF] * n
    pars = [set() for _ in range(n)]
    while hq:
        d, x, z = heappop(hq)
        if dist[x] != INF:
            if d == dist[x]:
                pars[x].add(z)
                used_edges[x] |= used_edges[z]
                if z < x:
                    used_edges[x].add((z, x))
                else:
                    used_edges[x].add((x, z))
            continue   
        
        dist[x] = d
        if x != v:
            used_edges[x] |= used_edges[z]
            pars[x].add(z)
            if z < x:
                used_edges[x].add((z, x))
            else:
                used_edges[x].add((x, z))

        for (y, c) in graph[x]:
            if y in pars[x] or pars[y]:
                continue
            heappush(hq, (d+c, y, x))

    res = set()
    for i in range(n):
        res |= used_edges[i]
    return res

def main():
    res = set()
    for v in range(n):
        res |= dijkstra(v)
    
    
    ans = m - len(res)
    return ans

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

Submission status: Accepted

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

cost = [[] for _ in range(n)]
edges = dict()
for i in range(m):
    a = abc[i][0] - 1
    b = abc[i][1] - 1
    c = abc[i][2]
    cost[a].append((b, c))
    cost[b].append((a, c))

    edges[str(a) + ' ' + str(b)] = i
    edges[str(b) + ' ' + str(a)] = i

s = set()

# main
from heapq import heappop, heappush
for start in range(n):
    d = [float('inf') for i in range(n)] # 最短距離
    d[start] = 0

    q = [] # min-heap, (距離, 頂点)
    prev = [None] * n # 経路をたどるときに使う
    heappush(q, (d[start], start))
    while q:
        # print(q, d, prev)
        du, u = heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        for v, weight in cost[u]:
            alt = du + weight
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heappush(q, (alt, v))

    # print('最短距離: ', d)

    for goal in range(start + 1, n):
        goal = [goal]
        while prev[goal[-1]] != None:
            goal.append(prev[goal[-1]])
        goal = goal[::-1]

        for j in range(len(goal) - 1):
            edge_idx = edges[str(goal[j]) + ' ' + str(goal[j + 1])]
            s.add(edge_idx)

print(m - len(s))