Problem:


Score : 400 points

Problem Statement

You are given an undirected connected weighted graph with N vertices and M edges that contains neither self-loops nor double edges.

The i-th (1≤i≤M) edge connects vertex a_i and vertex b_i with a distance of c_i.

Here, a self-loop is an edge where a_i = b_i (1≤i≤M), and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).

A connected graph is a graph where there is a path between every pair of different vertices.

Find the number of the edges that are not contained in any shortest path between any pair of different vertices.  

Constraints

2≤N≤100 

N-1≤M≤min(N(N-1)/2,1000) 

1≤a_i,b_i≤N 

1≤c_i≤1000

c_i is an integer.

The given graph contains neither self-loops nor double edges.

The given graph is connected.

Input

The input is given from Standard Input in the following format:

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

Output

Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.

Sample Input 1

3 3
1 2 1
1 3 1
2 3 3

Sample Output 1

1

In the given graph, the shortest paths between all pairs of different vertices are as follows:

The shortest path from vertex 1 to vertex 2 is: vertex 1 → vertex 2, with the length of 1.

The shortest path from vertex 1 to vertex 3 is: vertex 1 → vertex 3, with the length of 1.

The shortest path from vertex 2 to vertex 1 is: vertex 2 → vertex 1, with the length of 1.

The shortest path from vertex 2 to vertex 3 is: vertex 2 → vertex 1 → vertex 3, with the length of 2.

The shortest path from vertex 3 to vertex 1 is: vertex 3 → vertex 1, with the length of 1.

The shortest path from vertex 3 to vertex 2 is: vertex 3 → vertex 1 → vertex 2, with the length of 2.

Thus, the only edge that is not contained in any shortest path, is the edge of length 3 connecting vertex 2 and vertex 3, hence the output should be 1.

Sample Input 2

3 2
1 2 1
2 3 1

Sample Output 2

0

Every edge is contained in some shortest path between some pair of different vertices.



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


Sample output:
1

Submission status: Accepted

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

# dijkstra
def dijkstra( start ):
    prev_node = [ -1 ] * ( n + 1 )
    INF = 10 ** 10
    VISITED = 1
    NOT_VISITED = 0
    cost = [ INF ] * ( n + 1 )
    cost[ start ] = 0
    visit = [ NOT_VISITED ] * ( n + 1 )
    queue = [ ( cost[ start ], start ) ]
    while len( queue ) > 0:
        c, v = heapq.heappop( queue )
        visit[ v ] = VISITED
        for u, cost_vu in adj_list[v]:
            if visit[ u ] == VISITED:
                continue
            if cost[u] > cost[v] + cost_vu:
                cost[u] = cost[v] + cost_vu
                heapq.heappush( queue, ( cost[u], u ) )
                prev_node[ u ] = v
    return prev_node

used_edge = [ [ False ] * ( n+1 ) for i in range( n+1 ) ]

used_count = 0
for s in range( 1, n+1 ):
    prev_node = dijkstra( s )
    for i in range( 1, n+1 ):
        j = prev_node[ i ]
        if j == -1:
            continue
        if used_edge[ i ][ j ] == False:
            used_count += 1
            used_edge[ i ][ j ] = True
            used_edge[ j ][ i ] = True

print( m - used_count )

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
from collections import deque
v = [deque([]) for _ in range(N)]

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

s = deque([])
for i in range(N):
    ls = [[-1,M*10000]]*N
    ls[i] =  [-1,0]
    q = [deque(j for j in k) for k in v]
    l = deque([i])
    while l:
        u = l.popleft()
        x = len(q[u])
        for i in range(x):
            e = q[u].popleft()
            if ls[u][1] + e[1] < ls[e[0]][1]:
                ls[e[0]] = [u, ls[u][1] + e[1]]
                l.append(e[0])
            q[u].append(e)
    for j,e in enumerate(ls):
        if e[0] != -1:
             s.append([min(j,e[0]),max(j,e[0])])

s = list(map(list, set(map(tuple, s))))
print(M-len(s))

Submission status: Accepted

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

def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    last=[-1]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        for c,v in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                last[v]=u
                heappush(que,(dist[v],v))
    return dist,last

dic={}
N,M=map(int,input().split())
G=[[] for i in range(N)]
Edges=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    G[a].append((c,b))
    G[b].append((c,a))
    Edges.append(tuple(sorted([a,b])))

for i in range(N):
    dist,last=dijkstra(G,i,N)
    for j in range(i):
        now=j
        while(now!=i):
            nex=last[now]
            dic[tuple(sorted([now,nex]))]=1
            now=nex
ans=len(Edges)
for u,v in Edges:
    if (u,v) in dic:
        ans-=1
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
N,M=map(int,input().split())
table=[[float("inf") for _ in range(N)] for _ in range(N)]
used=[[-float("inf") for _ in range(N)] for _ in range(N)]
tree=[[] for _ in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    used[a-1][b-1]=0
    used[b-1][a-1]=0
for i in range(N):
    table[i][i]=0
#print(used)
for i in range(N):
    d=[float("inf") for _ in range(N)]
    d[i]=0
    q=[]
    prev=[-1]*N
    q.append([0,i])
    heapq.heapify(q)
    while len(q)>0:
        dist,u=heapq.heappop(q)
        if d[u]<dist: continue
        piv=prev[u]
        v=u
        while piv!=-1:
            #print(piv)
            used[piv][v] = 1
            used[v][piv] = 1
            v = piv
            piv=prev[piv]
        for i in tree[u]:
            alt=d[u]+table[u][i]
            if d[i]>alt:
                d[i]=alt
                heapq.heappush(q,[alt,i])
                prev[i]=u
        #print(q,d,prev)
        #input()
    #print(d)
#print(used)
ans=0
for i in range(N):
    for j in range(N):
        if used[i][j]==0:
            ans=ans+1
print(ans//2)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
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

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, m = map(int, input().split())
d = [[INF for j in range(n)] for i in range(n)]
x = []
for i in range(m):
    a, b, c = map(int, input().split())
    x.append([a - 1, b - 1, c])
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c
d2 = warshall_floyd(d, n)
# print(d2)
ans = 0
for i in x:
    if d2[i[0]][i[1]] != i[2]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

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

edge = [[float("inf") for i in range(N)] for j in range(N) ]

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

dist = floyd_warshall(edge)

ans = 0

for a,b,c in abc:
    if dist[a-1][b-1] != c:
        ans += 1

print(ans)

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())
ma = [[0]*n for _ in range(n)]
list_ABC = [ list(map(int,input().split(" "))) for i in range(m)]

for a, b, c in list_ABC:
  ma[a-1][b-1] = c
  ma[b-1][a-1] = c
  
y = dijkstra(ma, directed=False).astype(int)
 
ans = 0
 
for a, b, c in list_ABC:
  if y[a-1][b-1] != c:
    ans += 1
    
print(ans)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    class PQueueMin:
        def __init__(self):
            self.pq = []    # 第一要素に cost、第二要素に ind が来る様にする
        
        def push(self, ind, cost):
            heappush(self.pq, [cost, ind])
        
        def pop(self):
            cost, ind = heappop(self.pq)
            return [ind, cost]
    
        def is_empty(self):
            return len(self.pq)==0
    
    
    
    def dijkstra(adj_with_weight, start):
        '''
        Dijkstra 法 O((E+V)lgV) (頂点を回るときに最小のものを取り出していくのに VlgV, cost の更新で ElgV)
        負辺を含まぬ重みつきグラフについて、ある頂点から他の頂点までの最短コストを貪欲に計算する
        '''
        V = len(adj_with_weight)
        cost = [float('inf')] * V
        previous = [None] * V
        cost[start] = 0
        fixed = [False] * V
        pq = PQueueMin()
        # 最初は始点が必ずコスト最小。pq に突っ込む
        pq.push(start, cost[start])
        while not pq.is_empty():
            # 現段階で最短のコストとなっている頂点を選択
            u, cost_of_u = pq.pop()
            fixed[u] = True
            for v, weight_of_uv in adj_with_weight[u]:
                if not fixed[v] and cost[v] > cost_of_u + weight_of_uv:
                    cost[v] = cost_of_u + weight_of_uv
                    previous[v] = u
                    pq.push(v, cost[v])
        return cost, previous
    
    n, m = mi()
    adj_with_weight = [[] for _ in range(n)]
    edge_matrix = [[False] * n for _ in range(n)]    # あとで最短経路として使ったかどうかのメモ
    for _ in range(m):
        a, b, c = mi()
        a -= 1
        b -= 1
        adj_with_weight[a].append((b, c))
        adj_with_weight[b].append((a, c))
    
    for i in range(n):
        _, previous = dijkstra(adj_with_weight, i)
        # print(previous)
        for j in range(n):
            if j != i:
                u = previous[j]
                j, u = min(j, u), max(j, u)
                edge_matrix[j][u] = True
    # print(edge_matrix)
    
    cnt = 0
    for u in range(n):
        for v, _ in adj_with_weight[u]:
            if u < v and not edge_matrix[u][v]:
                cnt += 1
    print(cnt)
    

    



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in range(M)]

g = [[0 for _ in range(N)] for _ in range(N)]

for a,b,c in ABC:
    g[a-1][b-1] = c

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
csg = csgraph_from_dense(g)
d = floyd_warshall(csg, directed=False)

ans = 0
for a,b,c in ABC:
    if c != d[a-1][b-1]:
        ans += 1

print(ans)

Submission status: Accepted

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

INF = 10**10

# Warshall-Floyd
dist = [[INF for _ in range(n)] for _ in range(n)]
edge = []
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1
    dist[a][b] = c
    dist[b][a] = c
    edge.append([a, b, c])

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

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 e in edge:
    flag = False
    i, j, c = e
    for s in range(n):
        if flag:
            break
        for t in range(n):
            if dist[s][i]+c+dist[j][t] == dist[s][t]:
                flag = True
                break
    if flag:
        ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7
# mod = 998244353


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class UF:
    def __init__(self, N):
        self.state = [-1] * N
        self.rank = [0] * N
        self.num_group = N

    def get_parent(self, a):
        p = self.state[a]
        if p < 0:
            return a

        q = self.get_parent(p)
        self.state[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return

        if self.rank[pa] > self.rank[pb]:
            pa, pb = pb, pa
            a, b = b, a
        elif self.rank[pa] == self.rank[pb]:
            self.rank[pb] += 1

        self.state[pb] += self.state[pa]
        self.state[pa] = pb
        self.state[a] = pb
        self.num_group -= 1

    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def get_size(self, a):
        return -self.state[self.get_parent(a)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, M = read_values()
    L = []
    D = [[10 ** 10 for _ in range(N)] for __ in range(N)]
    for _ in range(M):
        a, b, c = read_values()
        a -= 1
        b -= 1
        D[a][b] = c
        D[b][a] = c
        L.append((c, a, b))
    L.sort()

    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])
    res = 0
    for c, a, b in L:
        if D[a][b] < c:
            res += 1

    print(res)


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())
ma = [[0]*n for _ in range(n)]
list_ABC = [ list(map(int,input().split(" "))) for i in range(m)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

x = csr_matrix(ma)
y = dijkstra(x, directed=False).astype(int)

ans = 0

for a, b, c in list_ABC:
  if y[a-1][b-1] != c:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    d=[[INF]*N for _ in range(N)]
    for _ in range(M):
        a,b,c=map(int1,input().split())
        c+=1
        d[a][b]=c
        d[b][a]=c
    d2=[d[i][:] for i in range(N)]
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d2[i][j]=min(d2[i][j],d2[i][k]+d2[k][j])
    ans=0
    for i in range(N):
        for j in range(N):
            if d[i][j]!=INF and d[i][j]!=d2[i][j]:
                ans+=1
    print(ans//2)

if __name__ == '__main__':
    main()

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):
        self.graph[src].append((dst, weight))
    def get_nodes(self):
        return self.graph.keys()

class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda : float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[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):
        return self.dist[goal]
    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

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

g = Graph()
for i in range(m):
    a, b, c = map(int, input().split())
    g.add_edge(a-1, b-1, c)
    g.add_edge(b-1, a-1, c)

A = []
for i in range(n):
    d = Dijkstra(g, i)
    for j in range(i+1, n):
        p = d.shortest_path(j)
        for k in range(len(p) - 1):
            A.append("{0},{1}".format(p[k], p[k+1]))
            A.append("{0},{1}".format(p[k+1], p[k]))

print((m*2 - len(set(A)))//2)

Submission status: Accepted

Solution code:
import sys
N, M = map(int, sys.stdin.readline().strip().split())
 
def warshall_floyd(d):
    # d[i][j]: iからjへの最短距離
    for k in range(size_v):
        for i in range(size_v):
            for j in range(size_v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
 
edges = []
for i in range(M):
    a, b, c = map(int, sys.stdin.readline().strip().split())
    edges.append((a, b, c))
#print(graph)
 
size_v = N + 1
dist=[[float("inf")] * size_v for i in range(size_v)] 
 
for a, b, c in edges:
    dist[a][b] = c
    dist[b][a] = c
for i in range(size_v):
    dist[i][i] = 0
 
dist = warshall_floyd(dist)
#print(dist)
  
answer_set = set()
for a, b, c in edges:
    if dist[a][b] == c:
        answer_set.add((a, b, c))
    
print(M - len(answer_set))

Submission status: Accepted

Solution code:
import sys

#O(ElogV)
import heapq
def dijkstra_heap(s, n, edges):
    # 始点sから各頂点への最短距離
    dist = [float("inf")] * n
    used = [True] * n # True:未確定
    dist[s] = 0
    used[s] = False
    used_edges = set()
    edgelist = []
    for (d, e) in edges[s]:
        # 利用した辺を管理するため、sも入れていることに注意
        heapq.heappush(edgelist, (d, e, s))
    while edgelist:
        d, e, s = heapq.heappop(edgelist)
        if dist[e] >= d:
            if s < e:
                used_edges.add((s, e))
            else:
                used_edges.add((e, s))

        # まだ使われてない頂点の中から最小の距離のものを探す
        if not used[e]:
            continue
        dist[e] = d
        used[e] = False

        """
        if s < e:
            used_edges.add((s, e))
        else:
            used_edges.add((e, s))
        """
        for (nd, ne) in edges[e]:
            if used[ne]:
                heapq.heappush(edgelist, (nd + dist[e], ne, e))
    return dist, used_edges

N, M = map(int, sys.stdin.readline().strip().split())

edges = [[] for _ in range(N)]
all_edges = set()
for _ in range(M):
    a, b, c = map(int, sys.stdin.readline().strip().split())
    edges[a-1].append((c, b-1))
    edges[b-1].append((c, a-1))
    if a < b:
        all_edges.add((a-1, b-1))
    else:
        all_edges.add((b-1, a-1))

for i in range(N):
    min_d, used_edges = dijkstra_heap(i, N, edges)
    # 利用した辺を取り除く
    all_edges -= used_edges

print(len(all_edges))

Submission status: Accepted

Solution code:
N, M = map(int, input().split(' '))
dist = [[10 ** 9 for _ in range(N)] for _ in range(N)]
edges = []

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

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

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

ans = 0
for (u, v, cost) in edges:
    flag = False
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            flag |= ((dist[i][u] + cost + dist[v][j]) == dist[i][j])
    ans += 1 - int(flag)
print(ans)

Submission status: Accepted

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

import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist=[float("inf")]*size_v  
  used=[False]*size_v
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w,i in graph[s]:
    heapq.heappush(hq_edge,(w,v,i))

  while hq_edge:
    min_w,min_v,ei=heapq.heappop(hq_edge)
    if dist[min_v]>=min_w:
      answer_set.add(ei)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    for v,w,ei2 in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v,ei2))

  return dist

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

size_v=N+1
answer_set=set()
for i in range(1,N+1):
  dist=dijkstra_heap(i)
  #print(dist)
    
#print(sorted(list(answer_set)))
print(M-len(answer_set))

Submission status: Accepted

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

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

abclist=[]
for i in range(M):
  a,b,c=map(int,input().split())
  abclist.append((a,b,c))
#print(graph)

size_v=N+1
dist=[[float("inf")]*size_v for i in range(size_v)] 

for a,b,c in abclist:
  dist[a][b]=c
  dist[b][a]=c
for i in range(size_v):
  dist[i][i]=0

dist=warshall_floyd(dist)
#print(dist)
  
answer_set=set()
for a,b,c in abclist:
  if dist[a][b]==c:
    answer_set.add((a,b,c))
    
print(M-len(answer_set))