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: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
li = [[0 for i in range(n)]for j in range(n)]
lis = []

def all_pairs_shortest_paths(W):
    inf = 10**18
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

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

lin = all_pairs_shortest_paths(li)
point = 0

for path in lis:
    a,b,c = path
    flag = False
    for i in range(n):
        for j in range(n):
            if lin[i][a]+c+lin[b][j] == lin[i][j]:
                flag = True
    if not flag:
        point += 1

print(point)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    from itertools import combinations
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for idx in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, c, idx))  # to,weight,idx
        g[b].add((a, c, idx))  # to,weight,idx

    used_edge = 0

    dq = deque()
    for frm, to in combinations(range(N), r=2):
        dq.append((frm, 0))

        dist = [1000 * 100 + 10] * N
        dist[frm] = 0
        while dq:
            v, c = dq.popleft()
            if dist[v] < c: continue
            for u, dc, idx in g[v]:
                nc = c + dc
                if dist[u] > nc:
                    dist[u] = nc
                    dq.append((u, nc))

        dq.append((to, 0))
        while dq:
            v, b = dq.popleft()
            if v == frm:
                used_edge |= b
                continue

            for u, dc, idx in g[v]:
                if dist[u] == dist[v] - dc:
                    dq.append((u, b | 1 << idx))

    print(M - bin(used_edge).count('1'))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    from itertools import combinations
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for idx in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, c, idx))  # to,weight,idx
        g[b].add((a, c, idx))  # to,weight,idx

    used_edge = 0

    dq = deque()
    for frm, to in combinations(range(N), r=2):
        dq.append((frm, 0))

        dist = [1000 * 100 + 10] * N
        dist[frm] = 0
        while dq:
            v, c = dq.popleft()
            if dist[v] < c: continue
            for u, dc, idx in g[v]:
                if dist[u] > c + dc:
                    dist[u] = c + dc
                    dq.append((u, dist[u]))

        dq.append((to, 0))
        while dq:
            v, b = dq.popleft()
            if v == frm:
                used_edge |= b
                continue

            for u, dc, idx in g[v]:
                if dist[u] == dist[v] - dc:
                    dq.append((u, b | 1 << idx))

    print(M - bin(used_edge).count('1'))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    from itertools import combinations

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

    g = tuple(set() for _ in range(N))
    for idx in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, c, idx))  # to,weight,idx
        g[b].add((a, c, idx))  # to,weight,idx

    not_used_edge = [True] * M

    for frm, to in combinations(range(N), r=2):
        dq = deque()
        dq.append((frm, 0))

        dist = [1000 * 100 + 10] * N
        dist[frm] = 0
        while dq:
            v, c = dq.popleft()
            if dist[v] < c: continue
            for u, dc, idx in g[v]:
                if dist[u] > c + dc:
                    dist[u] = c + dc
                    dq.append((u, dist[u]))

        dq = deque()
        dq.append((to, 0))
        while dq:
            v, b = dq.popleft()
            if v == frm:
                for j in range(M):
                    if (b >> j) & 1:
                        not_used_edge[j] = False
                continue

            for u, dc, idx in g[v]:
                if dist[u] == dist[v] - dc:
                    dq.append((u, b | 1 << idx))

    print(sum(not_used_edge))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall

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

s=[[float('inf')]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    s[i][j]=0

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

wf,p=floyd_warshall(s,return_predecessors=True)

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

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


for i in range(n-1):
  for j in range(i+1,n):
    min_l=get_path(i,j,p)
    for k in range(len(min_l)-1):
      hen1=[min_l[k+1],min_l[k]]
      hen2=[min_l[k],min_l[k+1]]
      if hen1 in l:
        l.remove(hen1)
      elif hen2 in l:
        l.remove(hen2)

print(len(l))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())

import heapq

def dijkstra(graph, start, goal):
    path = [start]
    score = 0
    searching_heap = []
    checked = {start: score}
    heapq.heappush(searching_heap, (score, path))
    while(len(searching_heap) > 0):
        score, path = heapq.heappop(searching_heap)
        latest_pos = path[-1]
        if(latest_pos == goal):
            return path, score
        for next_pos, weight in graph[latest_pos].items():
            new_path = path + [next_pos]
            new_score = score + weight
            if(next_pos in checked and checked[next_pos] <= new_score):
                continue
            else:
                checked[next_pos] = new_score
                heapq.heappush(searching_heap, (new_score, new_path)) 
import copy

def Main(N, M, A, B, C):
    g = {}
    for i in range(M):
        if A[i] not in g:
            g[A[i]] = {}
        if B[i] not in g:
            g[B[i]] = {}
        g[A[i]].update({B[i]:C[i]})
        g[B[i]].update({A[i]:C[i]})
    ans = 0
    for i in range(1, N):
        for j in range(i+1, N+1):
            path, score = dijkstra(g, i, j)
            if len(path) > 2:
                if i in g and j in g[i] and score < g[i][j]:
                    ans += 1
    return ans
                
          
                    
print(Main(N, M, A, B, C))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())

import heapq

def dijkstra(graph, start, goal):
    path = [start]
    score = 0
    searching_heap = []
    checked = {start: score}
    heapq.heappush(searching_heap, (score, path))
    while(len(searching_heap) > 0):
        score, path = heapq.heappop(searching_heap)
        latest_pos = path[-1]
        if(latest_pos == goal):
            return path
        for next_pos, weight in graph[latest_pos].items():
            new_path = path + [next_pos]
            new_score = score + weight
            if(next_pos in checked and checked[next_pos] <= new_score):
                continue
            else:
                checked[next_pos] = new_score
                heapq.heappush(searching_heap, (new_score, new_path)) 
import copy

def Main(N, M, A, B, C):
    g = {}
    for i in range(M):
        if A[i] not in g:
            g[A[i]] = {}
        if B[i] not in g:
            g[B[i]] = {}
        g[A[i]].update({B[i]:C[i]})
        g[B[i]].update({A[i]:C[i]})
    gg = copy.deepcopy(g)
    for i in range(1, N):
        for j in range(i+1, N+1):
            path = dijkstra(g, i, j)
            len_path = len(path)
            for k in range(1, len_path):
                a = path[k-1]
                b = path[k]
                if b in gg[a]:
                    del gg[a][b]
                if a in gg[b]:
                    del gg[b][a]
    ans = 0
    for v in gg.values():
        ans += len(v)
    return ans//2
                
          
                    
print(Main(N, M, A, B, C))

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

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

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y,z = map(int,input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z

check = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(i+1,n):
        tmp = dijkstra_back(i,j,n,w,cost)
        #print(tmp)
        for k in range(len(tmp)-1):
            #print(tmp[k],tmp[k+1])
            check[min(tmp[k],tmp[k+1])][max(tmp[k],tmp[k+1])] = 1

#print(check)

#exit()

print(w - sum(map(sum, check)))

#print(dijkstra_back(0,1,n,w,cost))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

INF = 1 << 28
ds = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    ds[i][i] = 0

for abc in ABC:

    ds[abc[0]][abc[1]] = ds[abc[1]][abc[0]] = min(ds[abc[0]][abc[1]], abc[2])

for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            ds[i][j] = ds[j][i] = min(ds[i][j], ds[i][k] + ds[k][j])
cnt = 0
for abc in ABC:
    used = False
    for i in range(N + 1):
        for j in range(N + 1):
            if ds[i][j] == ds[i][abc[0]] + abc[2] + ds[abc[1]][j]:
                used = True
    if not used:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

class WarshallFloyd:
    def __init__(self,n):
        self.dist = {}
        for i in range(n-1):
            for j in range(i,n):
                self.dist[(i,j)] = 1e100

    def unite(self,x,y,c):
        if x == y:
            return False
        elif x > y:
            x,y = y,x
        if self.dist[(x,y)] <= c:
            return False
        else:
            for i in range(n-1):
                for j in range(i+1,n):
                    self.dist[(i,j)] = min(self.d(i,j), self.d(i,x) + c + self.d(y,j), self.d(i,y) + c + self.d(x,j))

    def d(self,x,y):
        if x == y:
            return 0
        if x > y:
            x,y = y,x
        return self.dist[(x,y)]

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

Submission status: Time Limit Exceeded

Solution code:
class WarshallFloyd:
    def __init__(self,n):
        self.dist = {}
        for i in range(n-1):
            for j in range(i,n):
                self.dist[(i,j)] = 1e100

    def unite(self,x,y,c):
        if x == y:
            return False
        elif x > y:
            x,y = y,x
        if self.dist[(x,y)] <= c:
            return False
        else:
            for i in range(n-1):
                for j in range(i+1,n):
                    self.dist[(i,j)] = min(self.d(i,j), self.d(i,x) + c + self.d(y,j), self.d(i,y) + c + self.d(x,j))

    def d(self,x,y):
        if x == y:
            return 0
        if x > y:
            x,y = y,x
        return self.dist[(x,y)]

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

Submission status: Time Limit Exceeded

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

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

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


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


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

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

# 最短経路じゃない辺全探索
edge_not_use = set()
# for s, t in combinations(range(N), 2):
#     d = D[s, t]
#     for (i, j), e in edges.items():
#         if d != D[s, i] + e + D[j, t] and d != D[s, j] + e + D[i, t]:  # 最短経路辺になれない
#             print(s, i, j, t)
#             print(d, '|', D[s, i], e, D[j, t], '|',
#                   D[s, j], e, D[i, t])  # 最短経路辺になれない
#             edge_not_use.add((i, j) if i < j else (j, i))
#     print()

# 辺を固定してs,tを全探索したほうが良さそう
for (i, j), e in edges.items():
    for s, t in combinations(range(N), 2):
        d = D[s, t]
        if d == D[s, i] + e + D[j, t] or d == D[t, i] + e + D[j, s]:
            break
    else:
        edge_not_use.add((i, j))


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

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 10**10
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)
from functools import lru_cache
from itertools import permutations

def main():
    n,m = map(int,input().split())
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0

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

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

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

graph = [[0] * n for _ in range(n)]
for a, b, c in abc:
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

dist, pre = floyd_warshall(csr_matrix(graph), return_predecessors=True)

edges = set()
for s in range(n):
    for g in range(s + 1, n):
        while g != s:
            par_g = pre[s][g]
            edge = sorted([par_g, g])
            edge = tuple(edge)
            edges.add(edge)
            g = par_g

ans = m - len(edges)
print(ans)

Submission status: Time Limit Exceeded

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

DP = [[10**5 for _ in range(n)] for _ in range(n)]
for i in range(n):
    DP[i][i] = 0

Edge = []
for _ in range(m):
    a, b, c = map(int, input().split())
    DP[a-1][b-1] = c
    DP[b-1][a-1] = c
    Edge.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])

Edge_check = [0 for _ in range(len(Edge))]
for e in range(len(Edge)):
    for s in range(n):
        for t in range(n):
            if s == t:
                continue
            i = Edge[e][0] -1
            j = Edge[e][1] -1
            cost = Edge[e][2]
            if DP[s][i] + cost + DP[j][t] == DP[s][t]:
                Edge_check[e] = 1

ans = len(Edge_check) - sum(Edge_check)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import numpy as np
import heapq
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c

def initial_signal(i,matrix):
    d = [float("inf")]*(matrix.shape[0])
    d[i] = 0
    Q = []
    heapq.heappush(Q,(0,i))
    return d,Q

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


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    while Q:
        cost,u = heapq.heappop(Q)
        if d[u]<cost:
            continue
        for v in range(matrix.shape[0]):
            if matrix[u][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        shortest.append(dijkstra(i,matrix))
    ans=0
    for i in range(N):
        for j in range(N):
            if matrix[i][j]>shortest[i][j]:
                ans+=1
    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import os
import sys
import numpy as np
import heapq
#import pandas as pd
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c

def initial_signal(i,matrix):
    d = [float("inf")]*(matrix.shape[0])
    d[i] = 0
    Q = []
    heapq.heappush(Q,(0,i))
    return d,Q

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


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    while Q:
        cost,u = heapq.heappop(Q)
        if d[u]<cost:
            continue
        for v in range(matrix.shape[0]):
            if matrix[u][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        shortest.append(dijkstra(i,matrix))
    ans=0
    for i in range(N):
        for j in range(N):
            if matrix[i][j]>shortest[i][j]:
                ans+=1
    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import os
import sys
import numpy as np
import heapq
#import pandas as pd
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c

def initial_signal(i,matrix):
    d = [float("inf")]*(matrix.shape[0])
    d[i] = 0
    Q = []
    heapq.heappush(Q,(0,i))
    return d,Q

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


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    while Q:
        cost,u = heapq.heappop(Q)
        if d[u]<cost:
            continue
        for v in range(matrix.shape[0]):
            if matrix[u][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        shortest.append(dijkstra(i,matrix))
    ans=0
    for i in range(N):
        for j in range(N):
            if matrix[i][j]!=0 and matrix[i][j]>shortest[i][j]:
                ans+=1
    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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





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

print(sum(ans))

Submission status: Time Limit Exceeded

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

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





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

print(sum(ans))