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: Runtime Error

Solution code:
import heapq


def dijkstra(n, s, g):
    h = [(0, s)]
    heapq.heapify(h)
    cost = [float("Inf")] * (n + 1)  # cost: i -> j
    cost[s] = 0

    while h:
        c, v = heapq.heappop(h)
        if c > cost[v]:
            continue
        for d, u in g[v]:
            d_s_u = d + cost[v]
            if d_s_u < cost[u]:
                cost[u] = d_s_u
                heapq.heappush(h, (d_s_u, u))

    return cost


def main():
    n, m, *abc = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for a, b, c in zip(*[iter(abc)] * 3):
        g[a].append([c, b])
        g[b].append([c, a])

    ans = 0
    checkd = [[False] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        cost = dijkstra(n, i, g)
        for j, k in g[i]:
            if checkd[i][j]:
                continue
            if j > cost[k]:
                ans += 1
            checkd[i][j] = True
            checkd[j][i] = True
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
INF = 10**18
d = [[INF]*n for _ in range(n)]
for i in range(n): d[i][i] = 0
a = [0]*m
b = [0]*m
c = [0]*m
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    a[i] = a
    b[i] = b
    c[i] = c
    d[a][b] = c
    d[b][a] = 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])

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

Submission status: Runtime Error

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    cos = []
    row = []
    col = []
    for _ in range(m):
        a,b,c = map(int,ipt().split())
        row.append(a-1)
        col.append(b-1)
        cos.append(c)
        cos.append(c)
    csr = csr_matrix((cos,(row,col)),shape=(n,n))
    d = dijkstra(csr,directed=False)
    ans = 0
    for i in range(m):
        csr = csr_matrix((cos[:i:]+cos[i+1::],(row[:i:]+row[i+1::],col[:i:]+col[i+1::])),shape=(n,n))
        di = dijkstra(csr)
        if (di == d).all():
            ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


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


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


resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000001)

def main():
    n, m = map(int, input().rstrip().split())
    dist = [[500000 for i in range(n)]for j in range(n)]

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

    a = [None] * (m-1)
    b = [None] * (m-1)
    c = [None] * (m-1)

    for i in range(m):
        x, y, z = map(int, input().rstrip().split())
        dist[x-1][y-1] =  min(dist[x-1][y-1], z)
        dist[y-1][x-1] =  min(dist[x-1][y-1], z)
        a[i] = x - 1
        b[i] = y - 1
        c[i] = z
        
    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])
    #print(dist)
    result = m

    for i in range(m):
        for j in range(n):
            if dist[j][a[i]] + c[i] == dist[j][b[i]]:
                result -= 1
                break

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000001)

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

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

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
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])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1
            break

print(result)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000001)

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

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

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
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])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            print(j, a[i],b[i], c[i], i, dist[j][a[i]] ,dist[j][b[i]])
            result -= 1

print(result)

Submission status: Runtime Error

Solution code:
import sys

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

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

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
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])

result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1
            break

print(result)

Submission status: Runtime Error

Solution code:
import sys

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

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

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
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])
print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1
            break

print(result)

Submission status: Runtime Error

Solution code:
import sys

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

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

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
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])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
             result -= 1

print(result)

Submission status: Runtime Error

Solution code:
import sys

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

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

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1

print(result)

Submission status: Runtime Error

Solution code:
import sys

n, m = map(int, input().rstrip().split())
dist = [[float('inf') for i in range(n)]for j in range(n)]

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

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1

print(result)

Submission status: Runtime Error

Solution code:
import sys
import re
import heapq

n, m = map(int, input().rstrip().split())
dist = [[float('inf') for i in range(n)]for j in range(n)]

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

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
#print(dist)
result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1

print(result)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
INF = 10**10
d = [[INF]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
nxt = [[[i] for i in range(n)] for _ in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            if d[i][k]+d[k][j] < d[i][j]:
                d[i][j] = d[i][k]+d[k][j]
                nxt[i][j] = nxt[i][k]
            elif d[i][k]+d[k][j] == d[i][j]:
                nxt[i][j].extend(nxt[i][k])
s = set()
for start in range(n):
    for goal in range(n):
        if start==goal:
            continue
        def DFS(i):
            for j in nxt[i][goal]:
                s.add((i, j))
                if j!=goal:
                    DFS(j)
        DFS(start)
print(m-len(s)//2)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
INF = 10**10
d = [[INF]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
nxt = [[[i] for i in range(n)] for _ in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            if d[i][k]+d[k][j] < d[i][j]:
                d[i][j] = d[i][k]+d[k][j]
                nxt[i][j] = nxt[i][k]
            elif d[i][k]+d[k][j] == d[i][j]:
                nxt[i][j].extend(nxt[i][k])
s = set()
for start in range(n):
    for goal in range(n):
        if start==goal:
            continue
        def DFS(i):
            for j in nxt[i][goal]:
                s.add((i, j))
                if j!=goal:
                    DFS(j)
        DFS(start)
print(m-len(s)//2)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
INF = float("inf")
load = [[[INF, 0] for _ in range(N)] for _ in range(N)]
#print(load)
#dis = [[] for _ in range(N)]
#ID = [0 for _ in range(M)] #、0は未使用、1は使用
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  load[a][b] = [c,0]
  load[b][a] = [c,0]
  #dis[a].append([b,i])
  #dis[b].append([a,i])
#for i in range(N):
for i in range(N):
  load[i][i] = [0,0]
#print(load)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if load[i][j][0] > load[i][k][0]+load[j][k][0]:
        load[i][j][1] = 1
#print(load)
ans = 0
for i in range(N):
  for j in range(i+1,M):
    if load[i][j][1] == 1:
      ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import re
import heapq

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

for i in range(n):
    for j in range(n):
        if (i==j):
            dist[i][j]=0
        else:
            dist[i][j]=float('inf')
        

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x][y] =  min(dist[x][y], z)
    dist[y][x] =  min(dist[x][y], z)
    a.append(x)
    b.append(y)
    c.append(z)
    
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])

result = m

for i in range(m):
    for j in range(m):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1

print(result)

Submission status: Runtime Error

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 ] * ( m+1 ) for i in range( m+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: Runtime Error

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 ] * ( m+1 ) for i in range( m+1 ) ]

used_count = 0
for s in range( 1, n+1 ):
    prev_node = dijkstra( s )
    for i in range( 1, m+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: Runtime Error

Solution code:
import heapq
n, m = map( int, input().split() )
adj_list = [ [] for i in range( 0, 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, m+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: Runtime Error

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

s = deque([])
for i in range(N):
    ls = [[-1,math.inf]]*N
    ls[i] =  [-1,0]
    q = [deque(j for j in i) for i in v]
    l = deque([i])
    while l:
        u = l.popleft()
        while q[u]:
            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])
    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: Runtime Error

Solution code:
N,M = map(int,input().split())
start = []
goal = []
data = []
for _ in range(M):
    a,b,c = map(int,input().split())
    start.append(a)
    goal.append(b)
    data.append(c)
csr = csr_matrix((data,(start,goal)),shape=(N+1,N+1))
p,q = floyd_warshall(csr,directed=False,return_predecessors=True)
d=[[True]*N for _ in range(N)]
for i in range(1,N+1):
    for k,v in enumerate(q[i]):
        if v != -9999:
            d[i-1][v-1]=False
            d[v-1][i-1]=False
print(sum([sum(i) for i in d])//2)

Submission status: Runtime Error

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 and score < g[i][j]:
                ans += 1
    return ans
                
          
                    
print(Main(N, M, A, B, C))

Submission status: Runtime Error

Solution code:
import sys


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


sys.setrecursionlimit(20000000)


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

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

    def warshall_floyd(d):
        # d[i][j]: iからjへの最短距離
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j] = d[i][k] + d[k][j]
                        if i < j:
                            if (i, j) in L:
                                S.append((i, j))
                        else:
                            if (j, i) in L:
                                S.append((j, i))
        return d

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

d = [[0]*N for i in range(N)]

for i in range(M):
    d[a[i]-1][b[i]-1] = c[i]
    d[b[i]-1][a[i]-1] = c[i]
    



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

count = 0
for i in range(M):
    d[i][i] = float("inf")
    if d[a[i]-1][b[i]-1] != c[i]:

        count += 1
print(count)

Submission status: Runtime Error

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

d = [[0]*N for i in range(N)]

for i in range(M):
    d[a[i]-1][b[i]-1] = c[i]
    d[b[i]-1][a[i]-1] = c[i]
    


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

count = 0
for i in range(N):
    d[i][i] = float("inf")
    if d[a[i]-1][b[i]-1] != c[i]:

        count += 1
print(count)

Submission status: Runtime Error

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

d = [[0]*N for i in range(N)]

for i in range(M):
    d[a[i]-1][b[i]-1] = c[i]
    d[b[i]-1][a[i]-1] = c[i]
    


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

count = 0
for i in range(N):
    d[i][i] = float("inf")
    for j in range(N):
        if c[i] > d[i][j]:
            count += 1
print(count//2)

Submission status: Runtime Error

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

d = [[0]*N for i in range(N)]

for i in range(M):
    d[a[i]-1][b[i]-1] = c[i]
    d[b[i]-1][a[i]-1] = c[i]
    


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

count = 0
for i in range(M):
    d[i][i] = float("inf")
    if c[i] > d[a[i]-1][b[i]-1]:
            count += 1
print(count)

Submission status: Runtime Error

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

d = [[0]*N for i in range(N)]

for i in range(M):
    d[a[i]-1][b[i]-1] = c[i]
    d[b[i]-1][a[i]-1] = c[i]
    


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

count = 0
for i in range(M):
    d[i][i] = float("inf")
    if c[i] > d[a[i]-1][b[i]-1]:
            count += 1
print(count)

Submission status: Runtime Error

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

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

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

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

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

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

dp = g.WarshallFloyd_search()

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

print(ans)

Submission status: Runtime Error

Solution code:
N,M = (int(x) for x in input().split())
a= [0]*1000
b = [0]*1000
c = [0]*1000
dist= [[0]*100 for i in range(100)]
for i in range(M):
    a[i],b[i],c[i] = (int(x) for x in input().split())
for i in range(N):
    for j in range(N):
        if(i==j):
            dist[i][j] = 0
        else:dist[i][j] = float('inf')

for i in range(M):
    dist[a[i]][b[i]] = min(dist[a[i]][b[i]],c[i])
    dist[b[i]][a[i]] = min(dist[b[i]][a[i]],c[i])

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 i in range(M):
    flag = 0
    for j in range(N):
        if(dist[j][a[i]]+c[i] == dist[j][b[i]]):
            flag = 1
            if(flag == 1):
                ans -= 1
print(ans)

Submission status: Runtime Error

Solution code:
#051_D
from heapq import heappop, heappush
inf = 10 ** 10
d = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    d[i][i] = 0
n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    edges.append((a-1, b-1))

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

ans = 0
for u, v in edges:
    for i in range(n):
        if i == u or i == v:
            continue
        if d[u][i] + d[i][v] == d[u][v]:
            ans += 1
            break

print(ans)

Submission status: Runtime Error

Solution code:
# cadidates of no shortest paths
n, m = map(int, input().split())

d = [[float("inf") for i in range(n + 1)] for i in range(n + 1)]
edge_data=[]
connect={i:[] for i in range(1,n+1)}
for i in range(m):
    x, y, z = map(int, input().split())
    # 有向グラフか無向グラフかによってここで場合わけが生じる
    d[x][y] = z
    d[y][x] = z
    connect[x].append(y)
    connect[y].append(x)    
    edge_data.append((x,y,z))
for i in range(n + 1):
    d[i][i] = 0  # 自身のところに行くコストは０


def warshall_floyd(d):
    # d[i][j]=i番目の頂点からj番目の頂点までの最短距離
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

warshall_floyd(d)

#最短距離を求めた
cnt=0
for some in edge_data:
    x,y,zsome[0],some[1],some[2]
    if d[x][y]<z:
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
N, M = map(int, input().split())
graph = [[10000 for _ in range(N)] for l in range(N)]

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

  graph[b][a] = c
  graph[a][b] = c

newGraph = deepcopy(graph)

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

res = 0
for (i, row) in enumerate(newGraph):
  for (j, weight) in row:
    if (graph[i][j] != weight):
      res += 1

print(res/2)