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:
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in range(m)]
d=[[1<<32 for _ in range(n)] for _ in range(n)]
for a,b,c in abc:
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for i in range(n):
    d[i][i]=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=0
for a,b,c in abc:
    j=True
    for s in range(n):
        if d[s][a-1]+c==d[s][b-1]:
            j=False
    if j: ans+=1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = float('inf')

# 単一始点最短経路を求める（ダイクストラ法）
def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    prevs = [[] for _ in range(numV)] ###
    PQ = []
    heappush(PQ, (0, vSt))

    while PQ:
        c, vNow = heappop(PQ)
        if c > costs[vNow]: continue

        numUsed += 1
        if numUsed == numV: break

        costNow = c
        for v2, wt in adjList[vNow]:
            c2 = costNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                prevs[v2] = [vNow] ###
                heappush(PQ, (c2, v2))
            elif c2 == costs[v2]: ###
                prevs[v2].append(vNow) ###

    return prevs ###


N, M = map(int, input().split())
adjL = [[] for v in range(N)]
adjM = [[0] * N for v in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    adjL[a - 1].append((b - 1, c))
    adjL[b - 1].append((a - 1, c))
    if a > b: a, b = b, a
    adjM[a - 1][b - 1] = 1

for i in range(N):
    prevs = Dijkstra(adjL, i)
    for u in range(N):
        for v in prevs[u]:
            if u < v:
                adjM[u][v] = 0
            else:
                adjM[v][u] = 0

print(sum(map(sum, adjM)))

Submission status: Accepted

Solution code:
def d_candidates_of_no_shortest_paths(N, M, E):
    from scipy.sparse import csgraph

    graph = [[float('inf') for j in range(N)] for i in range(N)]
    for k in range(N):
        graph[k][k] = 0
    for a, b, c in E:
        graph[a - 1][b - 1] = c
        graph[b - 1][a - 1] = c
    dist = csgraph.floyd_warshall(graph)

    ans = M  # 最短経路として使われない辺の数
    for a, b, c in E:
        for s in range(N):
            if dist[s][a - 1] + c == dist[s][b - 1]:
                ans -= 1  # 条件を満たした辺は最短経路に使われる
                break
    return ans

N, M = [int(i) for i in input().split()]
E = [[int(i) for i in input().split()] for j in range(M)]
print(d_candidates_of_no_shortest_paths(N, M, E))

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

cost = [[INF] * N for i in range(N)]
for i in range(N):
    cost[i][i] = 0

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

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

ans = 0
for a, b, c in ls:
    if cost[a][b] != c:
        ans += 1

print ans

Submission status: Accepted

Solution code:
# ABC 051 D
INF = 7+10**9
N, M = map(int,input().split())
P = []
D = [[INF for k in range(N)] for l in range(N)]
for k in range(N):
    D[k][k] = 0
for k in range(M):
    a, b, c = map(int,input().split())
    P.append([a-1,b-1,c])
    D[a-1][b-1] = c
    D[b-1][a-1] = c

# Floyd-Warshall
for k in range(N):
    for l in range(N):
        for m in range(N):
            D[l][m] = min(D[l][m], D[l][k]+D[k][m])

ans = M
for p in P:
    a, b, c = p[0], p[1], p[2]
    for k in range(N):
        if D[a][k] + c == D[b][k]:
            ans -= 1
            break 
print(ans)

Submission status: Accepted

Solution code:
edges = []
n, m = map(int, input().split())
d = [[1000] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0

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

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

count = 0
for i, j, val in edges:
    isIncluded = False
    for s in range(n):
        if d[s][i] + val == d[s][j] or d[s][j] + val == d[s][i]:
            isIncluded = True
            break

    if not isIncluded:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import heapq

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

INF = float('inf')

def dijkstra(s):
    dist = [INF for i in range(n)]
    dist[s] = 0
    q = [(0, s, -1)]
    while q:
        cost, node, parent = heapq.heappop(q)
        if dist[node] < cost:
            continue
        if parent != -1:
            memo[parent][node] = 1
        for no, co in graph[node]:
            if dist[node] + co < dist[no]:
                dist[no] = dist[node] + co
                heapq.heappush(q, (dist[node]+co, no, node))

for v in range(n):
    dijkstra(v)

ans = 0
for i in range(n):
    for j in range(i+1, n):
        if memo[i][j] == 1:
            ans += 1

print(m - ans)

Submission status: Accepted

Solution code:
import heapq

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

INF = float('inf')

def dijkstra(s):
    dist = [INF for i in range(n)]
    dist[s] = 0
    q = [(0, s, -1)]
    while q:
        cost, node, parent = heapq.heappop(q)
        if dist[node] < cost:
            continue
        if parent != -1:
            memo[parent][node] = 1
        for no, co in graph[node]:
            if dist[node] + co < dist[no]:
                dist[no] = dist[node] + co
                heapq.heappush(q, (dist[node]+co, no, node))

for v in range(n):
    dijkstra(v)

ans = 0
for i in range(n):
    for j in range(n):
        if memo[i][j] == 1:
            ans += 1

print(m - ans//2)

Submission status: Accepted

Solution code:
def ABC051D():
    N, M = map(int, input().split())
    DP = [[10000 for i in range(N)] for j in range(N)]
    check = [[1 for i in range(N)] for j in range(N)]
    pointlist = []
    for i in range(M):
        a, b, c = map(int, input().split())
        DP[a - 1][b - 1] = c
        DP[b - 1][a - 1] = c
        pointlist.append([a, b, 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 i in pointlist:
        if DP[i[0] - 1][i[1] - 1] != i[2]:
            cnt += 1

    print(cnt)
ABC051D()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 9
g = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    g[i][i] = 0
for a, b, c in edge:
    g[a][b] = c
    g[b][a] = c
for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

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

Submission status: Accepted

Solution code:
import heapq

def Dijk(s): #始点Sのダイクストラ, すべての行先への最短距離のリストを返す
    Cost = [float("inf") for i in range(N)]
    Cost[s] = 0
    Q = [[0, s]]
    V = [False for i in range(N)]
    while Q:
        Next = heapq.heappop(Q)
        V[Next[1]] = True
        for node in Edge[Next[1]]:
            if V[node[1]] == False:
                if Next[0] + node[0] < Cost[node[1]]:
                    Cost[node[1]] = Next[0] +node[0]
                    heapq.heappush(Q, [Cost[node[1]], node[1]])
    return Cost


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

Ans = 0
Length = []
for i in range(N):
    Length.append(Dijk(i))

for s in Search:
    for i in range(N):
        if Length[i][s[0]] + s[2] == Length[i][s[1]]:
            break
    else:
        Ans += 1

print(Ans)

Submission status: Accepted

Solution code:
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)

        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

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)

Submission status: Accepted

Solution code:
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

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)

Submission status: Accepted

Solution code:
import heapq
INF = 10**7
N,M = map(int,input().split())
weight = [[INF for j in range(N)] for i in range(N)]
used = [[True for i in range(N)] for j in range(N)]
dist = [[INF if i != j else 0 for j in range(N)] for i in range(N)]
for i in range(M):
	a,b,c = map(int,input().split())
	a -= 1
	b -= 1
	weight[a][b] = c
	weight[b][a] = c
	used[a][b] = False
	used[b][a] = False

for i in range(N):
	hq = []
	heapq.heapify(hq)
	heapq.heappush(hq, (0, i, None))
	searched = [False for j in range(N)]
	while len(hq) > 0:
		cost, node, edge = heapq.heappop(hq)
		if searched[node]:
			if cost == dist[i][node] and edge != None:
				used[edge[0]][edge[1]] = True
				used[edge[1]][edge[0]] = True
			continue
		
		searched[node] = True
		dist[i][node] = cost
		if edge != None:
			used[edge[0]][edge[1]] = True
			used[edge[1]][edge[0]] = True
		for j in range(N):
			if weight[node][j] == INF or searched[j]:
				if cost + weight[node][j] == dist[i][j]:
					used[node][j] = True
					used[j][node] = True
				continue
			heapq.heappush(hq, (cost + weight[node][j], j, (node,j)))

print(sum([sum([1 for j in range(N) if not used[i][j]]) for i in range(N)]) // 2)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
list1=[]
list2=[]
list3=[]
for i in range(N):
    list2=[]
    for j in range(N):
        list2.append(1111)
    list1.append(list2)
    
#print(list1)
for k in range(M):
    a,b,c=map(int,input().split())
    list3.append([a,b,c])
    list1[a-1][b-1]=c
    list1[b-1][a-1]=c
#print(list1)
#print(list3)
list2=list1

for a in range(N):
    for b in range(N):
        for c in range(N):
            if list2[b][a]+list2[a][c]<list2[b][c]:
                list2[b][c]=list2[b][a]+list2[a][c]
#print(list2)
count=0
for x in range(M):
    if list2[list3[x][0]-1][list3[x][1]-1]!=list3[x][2]:
        count+=1
print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
from __future__ import unicode_literals
from __future__ import print_function
import sys
import string

INF = 32768

def main():
    lines = map(lambda x: [int(i) for i in string.split(x)],
        sys.stdin.readlines())
    N, M = lines[0]

    d = [[INF]*N for x in range(N)]
    for i in range(N):
        for j in range(N):
            if(i == j): d[i][j] = 0

    for line in lines[1:]:
        d[line[0]-1][line[1]-1] = line[2]
        d[line[1]-1][line[0]-1] = line[2]

    # Warshall–Floyd Algorithm
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if(d[i][k] != INF and d[k][j] != INF):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    count = 0
    for line in lines[1:]:
        i, j, c = line
        #print("%s %s org:%s calc:%s" % (i,j,c,d[i-1][j-1]))
        if(d[i-1][j-1] != c):
            count += 1
            

    sys.stdout.write("%s" % count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
INF = 10**10
n,m = map(int, input().split())
d = [[INF for _ in range(n)] for _ in range(n)]
el = []

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i==j:
                d[i][j] = 0

            d[i][j] = min(d[i][j], d[i][k]+d[k][j])

ret = 0
for ei in range(m):
    a = el[ei][0]
    b = el[ei][1]
    c = el[ei][2]
    flag = False
    for s in range(n):
        if d[s][a]+c==d[s][b]:
            flag = True
            break
    if not flag:
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
M,N=map(int,input().split())
list1=[]
for i in range(M):
    list2=[]
    for j in range(M):
        list2.append(10000000000)
    list1.append(list2)
#print(list1)
listN=[]
for k in range(N):
    a,b,c=map(int,input().split())
    list1[a-1][b-1]=c
    list1[b-1][a-1]=c
    listN.append([a-1,b-1,c])
for x in range(M):
    list1[x][x]=0
#print(list1)
for c in range(M):
    for a in range(M):
        for b in range(M):
            if list1[a][b]>list1[a][c]+list1[c][b]:
                list1[a][b]=list1[a][c]+list1[c][b]
#print(list1)
ans=0
for d in range(N):
    if list1[listN[d][0]][listN[d][1]]!=listN[d][2]:
        ans+=1
print(ans)

Submission status: Accepted

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

r=lambda n:range(n)
l=[[inf if i!=j else 0 for j in r(n)] for i in r(n)]
a,b,c=[None]*m,[None]*m,[None]*m

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

for k in r(n):
  for i in r(n):
    for j in r(n):
      l[i][j]=min(l[i][j],l[i][k]+l[k][j])

ans=m
for i in r(m):
  f=False
  for j in r(n):
    if l[j][a[i]]+c[i]==l[j][b[i]]:
      f=True
  if f:ans-=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall as fw
import sys
sdin = sys.stdin.readline


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

INF = float("inf")
adj_mat = INF * np.ones((n, n))


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

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

    
shortest = fw(adj_mat)


ans = 0
for i in range(n):
    for j in range(i+1,n):
        if adj_mat[i][j] != INF and adj_mat[i][j] > shortest[i][j]:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
INF = float('inf')
wf = [[INF]*N for i in range(N)]
for a,b,c in src:
    a,b = a-1,b-1
    wf[a][b] = wf[b][a] = c
for i in range(N):
    wf[i][i] = 0

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])

ans = 0
for a,b,c in src:
    a,b = a-1,b-1
    if c != wf[a][b]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
sdin = sys.stdin.readline

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        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
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist


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

    
shortest = []
for st in range(n):
    shortest.append(dijkstra(adj_list, n, st))

    
# チェック
ans = 0
for st in range(n):
    for cost, ds in adj_list[st]:
        if cost > shortest[st][ds]:
            ans += 1

print(ans//2)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import defaultdict, deque
n, m = map(int, input().split())
G = defaultdict(list)
E = []
for i in range(m):
    a, b, c = map(int, input().split())
    G[a - 1].append((b - 1, c))
    G[b - 1].append((a - 1, c))
    E.append((a - 1, b - 1, c))

INF = float("inf")
d = [[INF] * n for i in range(n)]
for i in range(n):
    d[i][i] = 0
    que = [(0, i)]
    while que:
        cost, v = heappop(que)
        if d[i][v] < cost:
            continue
        for w, c in G[v]:
            if cost + c < d[i][w]:
                d[i][w] = cost + c
                heappush(que, (cost + c, w))

num = m
for x, y, c in E:
    flag = False
    for i in range(n):
        if d[i][x] + c == d[i][y]:
            flag = True
    if flag:
        num -= 1

print(num)

Submission status: Accepted

Solution code:
import numpy as np
N, M = [int(i) for i in input().split()]

INF = int(1e18)
G = np.full((N, N), INF)
for i in range(N):
    G[i][i] = 0

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


rng = range(N)
for k in rng:
    for i in rng:
        for j in range(i + 1, N):
            x = G[i][k] + G[k][j]
            if G[i][j] > x:
                G[i][j] = G[j][i] = x;
                
ans = 0
for (a, b, c) in edge:
    ans = ans + (G[a][b] != c)
print(ans)

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 add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))
 
 
class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """
 
    def __init__(self, graph, start):
        self.g = graph.graph
 
        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
 
        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)
 
        # startノードをキューに入れる
        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):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]
 
def main():
    n, m= map(int,input().split())
    g = Graph()
 
    inputs = [0]*m
 
    for i in range(m):
        lst = [int(i) for i in input().split()]
        inputs[i]=lst
        g.add_edge(lst[0], lst[1],lst[2])
        g.add_edge(lst[1], lst[0],lst[2])
 
    lst = [[0 for i in range(n+1)] for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i != j and lst[j][i] == 0:
                d = Dijkstra(g,i)
                lst[i][j] = d.shortest_distance(j)
 
    #print(lst)
    #print(inputs)
 
    ans = 0
    for i in range(m):
        if lst[min(inputs[i][0],inputs[i][1])][max(inputs[i][0],inputs[i][1])] < inputs[i][2]:
            ans+=1
 
    print(ans)
 
if __name__ == "__main__":
        main()

Submission status: Accepted

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

import heapq
def dijkstra_with_path(adj, n, st=1):
    inf = float('inf')
    dj = [inf] * (n + 1)
    paths = dict((x, [x]) for x in range(n + 1))
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                paths[tn] = paths[fn] + [tn]
                heapq.heappush(q, (dj[tn], tn))
    return dj, paths

links = set()
adj = dict((x, []) for x in range(N + 1))
for _ in range(M):
    a, b, c = map(int, input().split())
    adj[a].append((b, c))
    adj[b].append((a, c))
    links.add((a, b) if a < b else (b, a))

for x in range(1, N):
    _, paths = dijkstra_with_path(adj, N, x)
    for p in paths.values():
        t = (0, p[0])
        for v in p[1:]:
            t = (t[1], v)
            links -= set([t if t[0] < t[1] else (t[1], t[0])])
print(len(links))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[10000 for j in range(N)] for i in range(N)]
E = [(0, 0, 0)] * M
for i in range(N):
  G[i][i] = 0
for i in range(M):
  a, b, c = map(int, input().split())
  E[i] = (a - 1, b - 1, c)
  G[a - 1][b - 1] = c
  G[b - 1][a - 1] = c
def warshall_floyd(G):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        G[i][j] = min(G[i][k] + G[k][j], G[i][j])
  return G
G = warshall_floyd(G)
cnt = 0
for e in E:
  for s in range(N):
    if G[s][e[1]] == G[s][e[0]] + e[2]:
      break
  else:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product

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

dist = [[float('inf') for _ in range(N)] for _ in range(N)]
for a, b, c in abc:
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

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

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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
fn = lambda: [int(x) for x in input().split()]
N, M = fn()
data, row_idx, col_idx = [0]*M, [0]*M, [0]*M
for i in range(M):
    ai, bi, ci = fn()
    row_idx[i] = ai - 1
    col_idx[i] = bi - 1
    data[i] = ci

G = csr_matrix((data, (row_idx, col_idx)), shape=(N, N), dtype=int)
D, P = floyd_warshall(G, directed=False, return_predecessors=True)
edges = []
for i in range(N):
    for j in range(N):
        Pji = P[j][i]
        if Pji < 0 or i == Pji:
            continue
        edges.append((min(i, Pji), max(i, Pji)))
edges = set(edges)
print(M - len(edges))

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
D = []
for i in range(N):
  D.append([1000000]*N)
  D[i][i] = 0
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
  a, b, C[i] = map(int, raw_input().split())
  A[i] = a-1
  B[i] = b-1
  D[A[i]][B[i]] = C[i]
  D[B[i]][A[i]] = C[i]
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])
r = 0
for i in range(M):
  if D[A[i]][B[i]] < C[i]:
    r += 1
print r

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
A = [0]*M
B = [0]*M
C = [0]*M
d = []
for i in range(N):
  d.append([1000000]*N)
  d[i][i]=0
for i in range(M):
  a, b, c = map(int, raw_input().split())
  A[i] = a-1
  B[i] = b-1
  C[i] = c
  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])
      d[j][i] = d[i][j]
r = 0
for i in range(M):
  if d[A[i]][B[i]] < C[i]:
    r += 1
print r

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def warshall_floyd(g):
    d = defaultdict(dict)
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    for i in V:
        for j in V:
            if i in g and j in g[i]:
                d[i][j] = g[i][j]
            else:
                d[i][j] = sys.maxsize
    for k in g:
        for i in g:
            for j in g:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    return d


@mt
def slv(N, M, ABC):
    g = defaultdict(dict)
    for a, b, c in ABC:
        g[a][b] = c
        g[b][a] = c
    d = warshall_floyd(g)

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


def main():
    N, M = read_int_n()
    ABC = [read_int_n() for _ in range(M)]

    print(slv(N, M, ABC))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
    ai, bi, ci = map(int, input().split())
    a.append(ai-1)
    b.append(bi-1)
    c.append(ci)

G = csr_matrix((c, (a, b)), shape=(N, N), dtype=int)
D, P = floyd_warshall(G, directed=False, return_predecessors=True)
edges = []
for i in range(N):
    for j in range(N):
        if P[j][i] < 0 or i == P[j][i]:
            continue
        edges.append((min(i, P[j][i]), max(i, P[j][i])))
edges = list(set(edges))
print(M - len(edges))

Submission status: Accepted

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

N, M = map(int, input().split(" "))
graph = np.zeros((N, N))
edges = []
ans = 0
for l in range(M):
    a, b, c = map(int, input().split(" "))
    a = a - 1
    b = b - 1
    graph[a][b] = c
    graph[b][a] = c
    edges.append((a, b, c))
d = floyd_warshall(graph)
for e in edges:
    if e[2] > d[e[0], e[1]]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product


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


class WarshallFloyd(object):
    def __init__(self, graph):
        n = len(graph)
        dist = graph
        for k, i, j in product(range(n), repeat=3):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        self.dist = dist

    def shortest_distance(self, start, goal):
        return self.dist[start][goal]


graph = [[float('inf') for _ in range(N)] for _ in range(N)]
edge = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c
    edge[i] = (a - 1, b - 1, c)

wf = WarshallFloyd(graph)
ans = 0
for e in edge:
    if wf.shortest_distance(e[0], e[1]) != e[2]:
        ans += 1
print(ans)

Submission status: Accepted

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

import heapq
def dijkstra(adj, n, st=1):
    dj = [2**64] * (n + 1)
    einp = [set() for _ in range(n + 1)]
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc, eid in adj.get(fn, []):
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                einp[tn] = einp[fn] | set([eid])
                heapq.heappush(q, (dj[tn], tn))
    return einp

adj = {}
for i in range(M):
    a, b, c = map(int, input().split())
    e = adj.setdefault(a, [])
    e.append((b, c, i))
    e = adj.setdefault(b, [])
    e.append((a, c, i))

from functools import reduce
inc = set()
for i in range(N):
    einp = dijkstra(adj, N, i + 1)
    inc = reduce(lambda a, x: a | x, einp, inc)
print(M - len(inc))