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 sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[0]*n
b=[0]*n
c=[0]*n
for i in range(m):
  a[i],b[i],c[i]=map(int,input().split())
  a[i]-=1
  b[i]-=1
INF=float('inf')
dist=[ [INF]*n for _ in range(n)]
for i in range(n):
  dist[i][i]=0
for i in range(m):
  dist[a[i]][b[i]]=c[i]
  dist[b[i]][a[i]]=c[i]
#floyd warshall
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):
  shortest=False
  for j in range(n):
    if dist[j][a[i]]+c[i]==dist[j][b[i]]:
      shortest=True
      break
  if shortest:
    ans-=1
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[0]*n
b=[0]*n
c=[0]*n
for i in range(m):
  a[i],b[i],c[i]=map(int,input().split())
  a[i]-=1
  b[i]-=1
INF=float('inf')
dist=[ [INF]*n for _ in range(n)]
for i in range(n):
  dist[i][i]=0
for i in range(m):
  dist[a[i]][b[i]]=c[i]
  dist[b[i]][a[i]]=c[i]
#floyd warshall
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):
  shortest=False
  for j in range(n):
    if dist[j][a[i]]+c[i]==dist[j][b[i]]:
      shortest=True
      break
  if shortest:
    ans-=1
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
g=[[] for i in range(n)]
p=[]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    p.append([a,b,c])
    g[a].append([c,b])
    g[b].append([c,a])
ans=0
for i in range(m):
    s=p[i][0]
    goal=p[i][1]
    c=p[i][2]
    q=[]
    heapq.heappush(q,[0,s])
    v=[-1]*n
    v[s]=0
    while q:
        p=heapq.heappop(q)
        if p[1]==goal:
            break
        for i in g[p[1]]:
            if v[i[1]]==-1:
                v[i[1]]=i[0]+v[p[1]]
                heapq.heappush(q,[v[i[1]],i[1]])
    if p[0]<c:
        ans+=1
print(ans)

Submission status: Runtime Error

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

from collections import deque
import copy
n,m = map(int,input().split())
r = [[] for i in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    r[a-1].append((b-1,c,i+1))
    r[b-1].append((a-1,c,i+1))

def bfs(x,y):
    q = deque([])
    l = [-1]*n
    l[x] = 0
    check =[[] for i in range(n)]
    q.append((x,0,[]))
    while q:
        bef,pas,rec = q.popleft()
        if bef == y:
            break
            

        for nex,c,num in r[bef]:
            rec2 = copy.deepcopy(rec)
            rec2.append(num)
            
            if l[nex] == -1:
                l[nex] = pas+c
                check[nex] = rec2
                q.append((nex,pas+c,rec2))
            else:
                
                if pas+c < l[nex]:  
                    l[nex] = pas+c
                    check[nex] = rec2
                elif pas+c == l[nex]:
                    check[nex].append(rec2)
                else:
                    continue
    return check[y]

ans = set()
for i in range(n):
    for j in range(n):
        for k in bfs(i,j):
            ans.add(k)
        if len(ans) == m:
            print(0)
            exit()
print(m-len(ans))

Submission status: Runtime Error

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 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 = [100]*(matrix.shape[0])
    d[i] = 0
    Q = []
    for j in range(matrix.shape[0]):
        Q.append([j,100])
    Q[i][1]=0
    Q.sort()
    return d,Q

def relax(matrix,u,v,d,Q):
    if d[v] > d[u[0]]+matrix[u[0]][v]:
        d[v] = d[u[0]]+matrix[u[0]][v]
        for i,tmp in enumerate(Q):
            if Q[i][0]==v:
                Q[i][1] = d[u[0]]+matrix[u[0]][v]


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    S = []
    while Q:
        Q.sort(key=lambda x: x[1])
        u = Q.pop(0)
        S.append(u)
        for v in range(matrix.shape[0]):
            if matrix[u[0]][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]):
        short = dijkstra(i,matrix)
        shortest.append(short)
    ans=0
    for i in range(N):
        for j in range(N):
            cost = matrix[i][j]
            if cost>shortest[i][j]:
                ans+=1

    print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

d = np.ones((n, n)) * 1001

es = []
for i in range(m):
    es.append(list(map(int, input().split())))

for (i, j, w) in es:
    d[i - 1][j - 1] = w
    d[j - 1][i - 1] = w


for k in range(n):
    for i in range(n):
        for j in range(n):
            l = d[i][k] + d[k][j]
            if d[i][j] > l:
                d[i][j] = l

c = 0
for (i, j, w) in es:
    if d[i - 1][j - 1] < w:
        c += 1

print(c)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
N, M = map(int, input().split())
dic = defaultdict(list)
Els = []
for i in range(M):
  a, b, c = map(int, input().split())
  dic[a-1] += [(b-1,c)]
  dic[b-1] += [(a-1, c)]
  Els += [(a,b,c)]

def dijkstra(s,e):
  dist = [float('inf')]*N
  dist[s] = 0
  q = [(0,s)]
  z = -1
  while q:
    c, v = heappop(q)
    if dist[v]<c:
      continue
    dist[v] = c
    for u, m in dic[v]:
      if dist[u]>dist[v]+m:
        dist[u] = dist[v]+m
        heappush(q,(dist[v],v))
        if u==e:
          z = v
  return z

ans = 0
for a, b, c in Els:
  if dijkstra(a,b)==a:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra

INF = 10 ** 18
N, M = map(int, input().split())
d = [[INF for _ in range(N)] for _ in range(N)]
abc = []

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

dtra = dijkstra(d)
minlst = [INF] * N
for i in range(N):
    for j in range(N):
        if dtra[i][j] != 0:
            minlst[i] = min(minlst[i], dtra[i][j])

cnt = 0
for i in range(M):
    if int(minlst[abc[i][1]]) < abc[i][2]:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]

for i in range(N):
    dp[i][i] = 0

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

g = copy.deepcopy(dp)

# ワーシャルフロイド
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]])


# 経路復元
p = {}
for i in range(N):
    for j in range(i+1, N):
        c = i
        while c != j:
            for k in range(N):
                if k != c and (g[c][k]+dp[k][j]) == dp[c][j]:
                    p[(c, k) if c < k else (k, c)] = 1
                    c = k
                    break
print(max([0, M-len(p)))

Submission status: Runtime Error

Solution code:
import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]

for i in range(N):
    dp[i][i] = 0

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

g = copy.deepcopy(dp)

# ワーシャルフロイド
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]])


# 経路復元
p = {}
for i in range(N):
    for j in range(N):
        c = i
        while c != j:
            for k in range(N):
                if k != c and (g[c][k]+dp[k][j]) == dp[c][j]:
                    p[(c, k) if c < k else (k, c)] = 1
                    c = k
                    break
print(max([0, M-len(p)))

Submission status: Runtime Error

Solution code:
from itertools import combinations
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
abc = [list(map(int,input().split())) for i in range(m)]
abc = [[abc[i][0]-1,abc[i][1]-1,abc[i][2]] for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b,c in abc:
  graph[a].append((b,c))
  graph[b].append((a,c))
v1,v2,edge = zip(*abc)
csr = csr_matrix((edge,(v1,v2)),shape = (n,n))
dist = floyd_warshall(csr, directed = False)
ans = 0
for i,j in combinations(range(n),2):
  fs1,fs2 = zip(*graph[i])
  if j in fs1:
    x = fs1.index(j)
    if fs2[x] > dist[i][j]:
      ans += 1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

graph = [[float('infinity') for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][c] = c
ans = 0
# 頂点g -> 頂点vへのコストを計算する。直接のpathが最小なら、カウントしない。
# そうでなければ、他の経路があるので、カウントする。
for g in range(1, len(graph)):
    for v in range(1, N + 1):
        if g == v:
            continue
        paths = graph[g]
        direct = paths[v]
        if direct == float('infinity'):
            continue
        min_path = float('infinity')
        for i in range(len(paths)):
            p = paths[i]
            cost = p + graph[i][v]
            if min_path > cost:
                min_path = cost
        if direct > min_path:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
from itertools import combinations
read = sys.stdin.read

N, M, *abc = map(int, read().split())
a, b, c = zip(*zip(*[iter(abc)] * 3))

graph = csr_matrix((c, (a, b)), shape=(N + 1, N + 1))
distance = shortest_path(graph, directed=False)

answer = 0

for i, j in zip(a, b):
    for s in range(1, N + 1):
        if distance[i][j] + distance[j][s] == distance[i][s]:
            continue

        if distance[j][i] + distance[i][s] == distance[j][s]:
            continue

        answer += 1

print(answer)

Submission status: Runtime Error

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

A=[]
B=[]
C=[]
dist=[[1000]*N for i in range(N)]

for i in range(M):
    A.append(abc[i][0])
    B.append(abc[i][1])
    C.append(abc[i][2])
    
for i in range(N):
    dist[A[i]-1][B[i]-1] = C[i]
    dist[B[i]-1][A[i]-1] = C[i]

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])
            
count = 0
for i in range(N):
    if dist[abc[i][0]-1][abc[i][1]-1] != abc[i][2]:
        count+=1
        
print(count)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

n,m = map(int,input().split())
A = [0]*n
B = [0]*n
C = [0]*n
for i in range(m) :
    a, b, c = map(int,input().split())
    A[i] = a-1
    B[i] = b-1
    C[i] = c

graph = [[0]*n for i in range(n)]

for i in range(m) :
    graph[A[i]][B[i]] = C[i]
    graph[B[i]][A[i]] = C[i]

graph = csgraph_from_dense(graph)
dist = dijkstra(graph)

ans = 0
for i in range(m) :
    if dist[A[i]][B[i]] != C[i] :
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

n,m = map(int,input().split())
A = [0]*n
B = [0]*n
C = [0]*n
for i in range(m) :
    a, b, c = map(int,input().split())
    A[i] = a-1
    B[i] = b-1
    C[i] = c

graph = [[0]*n for i in range(n)]

for i in range(m) :
    graph[A[i]][B[i]] = C[i]
    graph[B[i]][A[i]] = C[i]

graph = csgraph_from_dense(graph)
dist = dijkstra(graph)

ans = 0
for i in range(m) :
    if dist[A[i]][B[i]] != C[i] :
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra

n,m = map(int,input().split())
edges = [[int(x) for x in input().split()] for i in range(m)]
graph = [[None]*n for i in range(n)]
for a, b, c in edges :
    graph[a-1][b-1] = c

#graph = csgraph_from_dense(graph)
dist = dijkstra(graph, directed=True).astype(int)

used = [0]*m
for s in range(n-1) :
    for t in range(s+1, n) :
        for i in range(len(edges)) :
            a, b, c = edges[i]
            a -= 1
            b -= 1
            if dist[s][a] + c + dist[b][t] == dist[s][t] :
                used[i] = 1
ans = m - sum(used)
print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import *

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

graph = csgraph_from_dense(graph)
dist = dijkstra(graph, directed=False).astype(int)

used = [0]*m
for s in range(n-1) :
    for t in range(s+1, n) :
        for i in range(len(edges)) :
            a, b, c = edges[i]
            a -= 1
            b -= 1
            if dist[s][a] + c + dist[b][t] == dist[s][t] :
                used[i] = 1
ans = m - sum(used)
print(ans)

Submission status: Runtime Error

Solution code:
def examD():
    N, M = LI()
    D = [[float("inf") for i in range(N)] for i in range(N)]
    # d[u][v] : 辺uvのコスト(存在しないときはinf)
    XY = [[0,0]]*M
    for i in range(M):
        x, y, z = map(int, input().split())
        XY[i] = [x-1,y-1]
        D[x - 1][y - 1] = z
        D[y - 1][x - 1] = z
    for i in range(N):
        D[i][i] = 0  # 自身のところに行くコストは０
    d = copy.deepcopy(D)
#    print(warshall_floyd(N, d))
    W = warshall_floyd(N, d)
    cur = int(0)
    for i in range(M):
        if D[XY[i][0]][XY[i][1]]>W[XY[i][0]][XY[i][1]]:
            cur += 1
    print(cur)

import sys
import copy
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
from math import inf


def dijkstra_need_edge(s):
    used = [False] * n
    used[s] = True

    dist = [inf] * n
    dist[s] = 0

    hq = []
    for e in g[s]:
        heappush(hq, e)

    need_edge = set()
    while hq:
        w, t, ind = heappop(hq)
        if used[t]: continue
        need_edge.add(ind)
        used[t] = True
        dist[t] = w
        add_es = map(lambda x: (dist[t] + x[0], x[1], x[2]), g[t])
        for e in add_es:
            heappush(hq, e)
    return need_edge


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

g = tuple(set() for _ in range(n))
for ind in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a].add((c, b, ind))
    g[b].add((c, a, ind))

st = set()
for v in range(n):
    st |= dijkstra_need_edge(v)
print(m - len(st))

Submission status: Runtime Error

Solution code:
sx, sy, tx, ty = map(int, input().split())
X, Y = tx-sx, ty-sy
ans = 'R'*X + 'U'*Y + 'L'*X + 'D'*Y + 'D' + 'R'*(X+1) + 'U'*(Y+1) + 'LU' + 'L'*(X+1) + 'D'*(Y+1) + 'R'
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
INF = 10**5
D=[[INF]*N for _ in range(N)]
for i in range(N):
  D[i][i]=0
path=[]
for i in range(M):
  a,b,c = map(int,input().split())
  D[a][b]=c
  D[b][a]=c
  path.append([a,b,c])
for k in range(N):
  for i in range(N-1):
    for j in range(i+1,N):
      D[i][j]=min(D[i][j],D[i][k]+D[j][k])
      D[j][i]=D[i][j]
ans=0
for a,b,c in path:
  if D[a][b]>c:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
dist = []
a = []
b = []
c = []

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



#nは頂点、mは辺、a、bは頂点、cはaとbの距離


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

res = 0
for i in range(m):
	if c[i] > dist[a[i]-1][b[i]-1]:
		res += 1

print (res)

Submission status: Runtime Error

Solution code:
import heapq

def dijkstra(graph, node, start):
  INF = float("inf")
  dist = [INF] * node
  dist[start] = 0
  que = [(0, start)]
  while que:
    cost, one_node = heapq.heappop(heap)
    for next_c, next_n in graph[one_node]:
      dist_candi = dist[one_node] + next_c
      if dist_candi < dist[next_n]:
        dist[next_node] = dist_candi
        heapq.heappush(heap, (dist[next_n], next_n))
  return dist

class SetGraph:
  def __init__(self, node_num):
    self.graph = [[] for _ in range(node_num)]

  def add_one_edge(self, start, end, cost):
    self.graph[start].append((cost, end))
    self.graph[end].append((cost, start))

  def get_graph(self):
    return self.graph 
  

n, m = map(int, input().split(" "))
graph = SetGraph(n)
add_process = SetGraph.add_one_edge
for i in range(m):
  a, b, c = map(int, input().split(" "))
  add_process(a - 1, b - 1, c)
graph = Graph.get_graph()

cost = []
for i in range(n):
  temp_cost = dijkstra(graph, n, i)
  cost.append(temp_cost)

result = 0
for i in range(n):
  for c, node in graph[i]:
    if cost[i][node] != c:
      result += 1

print(result // 2)

Submission status: Runtime Error

Solution code:
from queue import Queue

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

G=[[] for i in range(N)]
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])

T=[[1000]*N for i in range(N)]
U=[[[]for i in range(N)] for i in range(N)]

for i in range(N):
	q=Queue()
	seen=[False]*N
	q.put([i,0,[i]])
	seen[i]=True
	while not(q.empty()):
		t,d,u=q.get()
		seen[t]=True
		if T[i][t]>d:
			T[i][t]=d
			U[i][t]=u
			T[t][i]=d
			U[t][i]=u
		for x,c in G[t]:
			if seen[x]==False:
				q.put([x,d+c,[*u,x]])

A=[[False]*N for i in range(N)]
for i in range(N-1):
	for j in range(i+1,N):
		u=U[i][j]
		for k in range(len(u)-1):
			a,b=min(u[k],u[k+1]),max(u[k],u[k+1])
			A[a][b]=True

ans=M
for i in range(N-1):
	for j in range(i+1,N):
		ans-=int(A[i][j])

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce
from scipy.sparse.csgraph import floyd_warshall, csgraph_from_dense


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
graph = [[INF] * n for _ in range(n)]
for i in range(n):
    graph[i][i] = 0


for a, b, c in LIR(m):
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c


dist = [[graph[i][j] for j in range(n)] for i in range(n)]




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



cnt = 0
for i in range(n):
    for j in range(i, n):
        if graph[i][j] != INF and graph[i][j] > dist[i][j]:
            cnt += 1


print(cnt)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque

def solve(graph, edges, n, start_idx):
  flg = [False for _ in range(n)] #未検索のノードはFlase
  flg[start_idx] = True
  
  cost = [float('inf') for _ in range(n)]
  cost[start_idx] = 0
  
  prv_edges = [None for _ in range(n)]
  
  prv_node = start_idx  
  while not all(flg):
    for node, dis in graph[prv_node]:
      if cost[node] > dis:
        cost[node] = dis
        
        tmp_edge = sorted([prv_node, node])
        if tmp_edge in edges:
          edges.remove(tmp_edge)
        if prv_edges[node] is not None and prv_edges[node] not in edges:
          edges.append(prv_edges[node])
        prv_edges[node] = tmp_edge
    
    min_cost = float('inf')
    tmp_idx = -1
    for i in range(n):
      if flg[i] is False and min_cost > cost[i]:
        min_cost = cost[i]
        tmp_idx = i
    prv_node = tmp_idx
    flg[prv_node] = True
    #print(start_idx, prv_node, cost, edges, prv_edges)
  return edges

n, m = map(int, input().split())
graph = defaultdict(list)
edges = []

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

for i in range(n):
  edges = solve(graph, edges, n, i)
print(len(edges))

Submission status: Runtime Error

Solution code:
import heapq,math,sys
input=sys.stdin.readline
INF=math.inf
heappush=heapq.heappush
heappop=heapq.heappop

n,m=map(int,input().split())
graph=[[] for _ in range(n)]
minway=[]
bridges=[]
ans=0
for _ in range(m):
    a,b,c=map(int,input().split())
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))
    bridges.append((a-1,b-1))

def dijkstra(graph,n,start):
    Q=[]
    distance=[]
    dappend=distance.append
    for i in range(n):
        dappend([INF,i])
    distance[start][0]=0
    for j in distance:
        heappush(Q,j)
    while Q!=[]:
        q=heappop(Q)
        for v,vl in graph[q[1]]:
            alt=vl+q[0]
            if alt<distance[v][0]:
                distance[v][0]=alt
                heappush(Q,[alt,v])
    return distance

for k in range(n):
    minway.append(dijkstra(graph,n,k))

for l in bridges:
    flag=0
    x,y=l[0],l[1]
    for p in graph[x]:
        if p!=y:
            if minway[x][p[0]][0]+minway[x][y][0]==minway[p[0]][y][0]:
                flag=1
    for q in graph[y]:
        if q!=x:
            if minway[x][y][0]+minway[y][q[0]][0]==minway[x][q[0]][0]:
                flag=1
    if flag==0:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
INF = 10**9

edges = []

for i in range(M):
    edges.append(list(map(int, input().split())))

dist = [[INF for j in range(N)] for i in range(N)]

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

for i in range(M):
    a, b, c = edges[i]
    a, b = a - 1, b - 1
    dist[a][b] = c[i]
    dist[b][a] = c[i]
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])

res = M
for i in range(M):
    a, b, c = edges[i]
    a, b = a - 1, b - 1
    shortest = False
    for j in range(N):
        if dist[j][a] + c == dist[j][b]:
            shortest = True
            break
    if shortest:
        res -= 1

print(res)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
INF = 10**9

edges = []

for i in range(M):
    edges.append(list(map(int, input().split())))

dist = [[INF for j in range(N)] for i in range(N)]

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

for i in range(M):
    a, b, c = edges[i]
    a, b = a - 1, b - 1
    dist[a][b] = c[i]
    dist[b][a] = c[i]
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])

res = M
for i in range(M):
    a, b, c = edges[i]
    a, b = a - 1, b - 1
    shortest = False
    for j in range(N):
        if dist[j][a] + c == dist[j][b]:
            shortest = True
            break
    res -= 1

print(res)

Submission status: Runtime Error

Solution code:
s=input()
k=int(input())
ans=[]
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        ans.append(s[i:j])
ans.sort()
a=[ans[0]]
for i in range(1,len(ans)):
    if ans[i-1]!=ans[i]:
        a.append(ans[i])
print(a[k-1])

Submission status: Runtime Error

Solution code:
g = Graph()
N,M = list(map(int, input().split()))
INF = 10**9+7
A = [[INF if i!=j else 0 for i in range(N)] for j in range(N)]
S=[]
E=[]
W=[]

for i in range(M):
    s,e,w=list(map(int,input().split()))
    g.add_edge(s-1, e-1, w)
    g.add_edge(e-1, s-1, w)
    S.append(s-1)
    E.append(e-1)
    W.append(w)

for i in range(N):
    d = Dijkstra(g, i)
    for j in range(i+1,N):
        dist = d.shortest_distance(j)
        A[i][j] = dist
        A[j][i] = dist
        
ans=M
for i in range(M):
    shortest = False
    for j in range(N):
        if A[j][S[i]] + W[i] == A[j][E[i]]:
            shortest = True
    if shortest:
        ans-=1

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import copy
from collections import defaultdict
from heapq import heappush, heappop


def djkstra(adj_mat, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = np.argwhere(adj_mat[u] > 0).flatten()
        for v in vs:
            weight = adj_mat[u, v]
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))
    visited_edges = np.zeros_like(adj_mat, dtype=np.int32)

    for v in range(adj_mat.shape[0]):
        u = prev[v]
        if u is not None:
            visited_edges[u, v] = 1
            visited_edges[v, u] = 1

    return visited_edges


def main():
    N, M = map(int, input().split())
    adj_mat = np.zeros((N, N), dtype=np.int32)
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj_mat[a, b] = c
        adj_mat[b, a] = c

    visited_edge_count = np.sum(
        np.stack([djkstra(adj_mat, src)[np.newaxis, :, :] for src in range(N)], axis=0), axis=0)
    out = np.sum(np.logical_and(adj_mat > 0, visited_edge_count == 0)) // 2
    print(out)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:


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


def read_input():
    n, m = map(int, input().split())

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

    return n, m, edges

def submit():
    n, m, edges = read_input()

    # 全ノード間の最短経路を求める
    d = [[float('inf') for _ in range(n)] for _ in range(n)]

    for edge in edges:
        d[edge[0]][edge[1]] = edge[2]
        d[edge[1]][edge[0]] = edge[2]

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

    d = warshall_floyd(d, n)

    # 各edgeについていずれかの2点間の最短経路に含まれうるか確認する
    edge_inuse = [0 for _ in range(n)]
    for e, edge in enumerate(edges):
        for i in range(n):
            for j in range(n):
                dist1 = d[i][j]
                dist2 = d[i][edge[0]] + edge[2] + d[edge[1]][j]

                if dist1 == dist2:
                    edge_inuse[e] = 1
                    break

            if edge_inuse[e] == 1:
                break

    print(m - sum(edge_inuse))
    return


if __name__ == '__main__':
    submit()