Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

Constraints

2≤N≤100 

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

1≤a_i,b_i≤N 

1≤c_i≤1000

c_i is an integer.

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

The given graph is connected.

Input

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

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

Output

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

Sample Input 1

3 3
1 2 1
1 3 1
2 3 3

Sample Output 1

1

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

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

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

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

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

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

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

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

Sample Input 2

3 2
1 2 1
2 3 1

Sample Output 2

0

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



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


Sample output:
1

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def WF(E,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                E[i][j]=min(E[i][j],E[i][k]+E[k][j])
    return E

N,M = II()
a,b,c = Line(M,3)

E = [[10**30]*N for _ in range(N)]
for i in range(N):
    E[i][i] = 0         #自分との距離は0にしておく
for i in range(M):
    E[a[i]-1][b[i]-1] = c[i]
    E[b[i]-1][a[i]-1] = c[i]     #無向枝の場合両方格納

E2 = WF(E,N)

ans = 0
for i in range(M):
    if E2[a[i]-1][b[i]-1]<c[i]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
Glaph=[[0 for i in range(N)] for j in range(N)]
flag_ans=[[0 for i in range(N)] for j in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  Glaph[a-1][b-1]=c
  Glaph[b-1][a-1]=c
  
def djikstra(s):
  flag=[0 for i in range(N)]
  cost=[float("Inf") for i in range(N)]
  rout=[-1 for i in range(N)]
  
  cost[s]=0
  flag[s]=1
  
  for i in range(N):  
    minc=float("Inf")
    for j in range(N):
      if  flag[j]==0:
        if Glaph[s][j]!=0:
          if cost[j]>cost[s]+Glaph[s][j]:
            cost[j]=cost[s]+Glaph[s][j]
            rout[j]=s
            if minc>cost[j]:
              k=j
              minc=cost[j]
          elif minc>cost[j]:
            k=j
            minc=cost[j]
        elif minc>cost[j]:
          k=j
          minc=cost[j]

    s=k
    flag[s]=1
  
    flag_ans[ rout[s] ][ s ]=1
    flag_ans[s][ rout[s] ]=1

for i in range(N):
  djikstra(i)
  
ans=0
for i in range(N):
  for j in range(i+1,N):
    if flag_ans[i][j]==0 and Glaph[i][j]!=0:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
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 = dijkstra(graph, directed=False).astype(int)

answer = 0

for i, j, k in zip(a, b, c):
    if k != distance[i][j]:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
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 = dijkstra(graph, directed=False)

answer = 0

for i, j, k in zip(a, b, c):
    k = float(k)
    if k != distance[i][j]:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
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 = dijkstra(graph, directed=False)

answer = 0

for i, j, k in zip(a, b, c):
    k = float(k)
    if k == distance[i][j]:
        continue

    for s in range(1, N + 1):
        if i == s or j == s:
            continue

        if k + distance[j][s] == distance[i][s]:
            break

        if k + distance[i][s] == distance[j][s]:
            break

    else:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:

def dijkstra(graph,weight,s,N):
    distance=[1e10 for i in range(N)]
    distance[s]=0
    unvisited=[i for i in range(N)]
    while len(unvisited)>0:
        unvisited.sort(key=lambda x:distance[x])
        v=unvisited.pop(0)
        for w in graph[v]:
            if distance[w]>distance[v]+weight[(v,w)]:
                distance[w] = distance[v] + weight[(v, w)]
    return distance

def e_check(e,d_list,weight,N):
    for i in range(N):
        for j in range(N):
            if e[0]!=i and e[1]!=j and d_list[e[0]][i]+weight[(i,j)]==d_list[j][e[1]]:
                return True
    return False

def e_check_2(E,d_list,weight):
    count=0
    for e in E:
        if d_list[e[0]][e[1]]!=weight[e]:
            count+=1
    return count


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    graph={i:[] for i in range(N)}
    weight={(i,j):1e10 for i in range(N) for j in range(N)}
    E=[]

    for i in range(M):
        a,b,c = list(map(int, input().split()))
        E.append((a-1,b-1))
        E.append((b-1,a-1))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        weight[(a-1,b-1)]=c
        weight[(b-1,a-1)]=c
    d_list={i:dijkstra(graph,weight,i,N) for i in range(N)}

    ans=e_check_2(E,d_list,weight)

    print(ans//2)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
D = [[0 if i == j else 1<<100 for j in range(N)] for i in range(N)]
X = []
for _ in range(M):
    a, b, c = map(int, input().split())
    X.append([a-1, b-1, c])
    D[a-1][b-1] = c
    D[b-1][a-1] = c

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

print(sum([1 if D[a][b] < c else 0 for a, b, c in X]))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def warshall_floyd(): # 全点対最短路問題O(N^3)
    n,w = inpm() #n:頂点数　w:辺の数
    d = [[10**10 for i in range(n)] for i in range(n)] 
    #d[u][v] : 辺uvのコスト(存在しないときはinf)
    xyz=[]
    for i in range(w):
        x,y,z = inpm()
        x -= 1
        y -= 1
        xyz.append((x,y,z))
        d[x][y] = z
        d[y][x] = z
    for i in range(n):
        d[i][i] = 0 #自身のところに行くコストは0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return n,w,d,xyz

def main():
    n,w,d,edge=warshall_floyd()
    cnt=0
    for i in range(w):
        flag = False
        x=edge[i][0]
        y=edge[i][1]
        z=edge[i][2]
        for j in range(n):
            if d[j][x] + z == d[j][y]:
                flag = True
                break
            if d[j][y] + z == d[j][x]:
                flag = True
                break
        if not flag:
            cnt+=1
    print(cnt)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

import heapq

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

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

INF = float("inf")
# dp[i][j]:点iからjまでの最短距離
dp = [[INF for _ in range(N)] for _ in range(N)]

# 全点を開始点として探索
for i in range(N):
    # 同じ地点は距離0
    dp[i][i] = 0
    q = []
    # iまで0で行ける、を追加
    heapq.heappush(q,(0,i))
    while q:
        # 最短の候補を取り出す
        c,a = heapq.heappop(q)
        # 候補が最短でなければ捨てる
        if dp[i][a] < c:
            continue
        # 候補が最短になりうるならその点に繋がる辺を調べる
        for nc,b in es[a]:
            # i->b の経路について、i->a->bで行く方が今わかっているコストより小さい時
            if dp[i][b] > dp[i][a] + nc:
                dp[i][b] = dp[i][a] + nc
                # iからbまでdp[i][b]で行けるよ、を追加
                heapq.heappush(q, (dp[i][b],b))


        

ans = 0
for a in range(N):
    for c,b in es[a]:
        if dp[a][b] != c:
            ans += 1

print(ans//2)

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
new_graph = csgraph_from_dense(graph)
res = floyd_warshall(new_graph)
cnt = 0
for i in range(n):
    for j in range(i, n):
        if graph[i][j] > 0 and graph[i][j] != res[i][j]:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf,i) for i in range(n)]
    prev=[0]*n
    q=[i for i in d]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur][0]+dist
            if alt<d[dst][0]:
                d[dst]=(alt,dst)
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev
    
show_flg=False
show_flg=True

ans=0
n,m=LI()
g,ip=GI(n,m)
mins=[]
for i in range(n):
    d,p=dijkstra(g,i)
    mins.append([i for i,j in d])

for a,b,c in ip:
    k=1
    for y in range(n):
        if y==b:
            continue
        if mins[y][a]+c==mins[y][b]:
            k=0
    ans+=k

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
INF = 10 ** 7
A = list()
B = list()
C = list()
d = [[INF] * N for i in range(N)]
for m in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
    C.append(c)
    d[a][b] = c
    d[b][a] = c
for k in range(N):
    d[k][k] = 0

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

ans = 0
for m in range(M):
    if d[A[m]][B[m]] < C[m]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
INF = 10**6
Edge = [[INF]*N for _ in range(N)]
for _ in range(M):
    a,b,c = map(int, input().split())
    Edge[a-1][b-1] = c
    Edge[b-1][a-1] = c
    
dp = [[INF]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0
        else:
            dp[i][j] = Edge[i][j]
    
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])

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if Edge[i][j] == INF:
            continue
        if Edge[i][j] > dp[i][j]:
            ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for i in range(n):
        A[i][i]=0
    ABC=[None]*m
    for i in range(m):
        a,b,c=map(int,input().split())
        a-=1; b-=1
        A[a][b]=c; A[b][a]=c
        ABC[i]=(a,b,c)

    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])

    ans=0
    for a,b,c in ABC:
        ans+=all(A[u][v]<A[u][a]+c+A[b][v] for u,v in product(range(n),repeat=2))
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import heapq

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

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


"""
・ノード数が少ないので、全ノード間の最短距離を求めても間に合う
・ある辺eがいずれかの最短距離に含まれる　→　その辺eが結ぶ２ノードの最短距離はeの距離（それぞれの最短距離を束ねてある２ノードの最短距離を作るから）
"""

INF = float("inf")
# 全ノード間の最短距離を求める
d = [[INF for _ in range(N)] for _ in range(N)]

for i in range(N):
    q = []
    d[i][i] = 0
    heapq.heappush(q, (0, i))
    while q:
        cost, a = heapq.heappop(q)
        if d[i][a] < cost:
            continue
        for c,b in es[a]:
            if d[i][a] + c < d[i][b]:
                d[i][b] = d[i][a] + c
                heapq.heappush(q, (d[i][b], b))


# 全ての辺について、その辺の間の距離cがa->bまでの最短距離か確かめる
# ある辺がいずれかのノード間の最短経路に含まれるなら、その辺（が結ぶノード）も最短距離になるから。
cnt = 0
for i in range(N):
    for c, b in es[i]:
        if d[i][b] != c:
            cnt += 1

# 無向グラフなので２方向分カウントされてるから２で割る
print(cnt//2)

Submission status: Accepted

Solution code:
import heapq

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

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

INF = float("inf")
# 全ノード間の最短距離を求める
d = [[INF for _ in range(N)] for _ in range(N)]

for i in range(N):
    q = []
    d[i][i] = 0
    heapq.heappush(q, (0, i))
    while q:
        cost, a = heapq.heappop(q)
        if d[i][a] < cost:
            continue
        for c,b in es[a]:
            if d[i][a] + c < d[i][b]:
                d[i][b] = d[i][a] + c
                heapq.heappush(q, (d[i][b], b))


# 全ての辺について、その辺の間の距離cがa->bまでの最短距離か確かめる
# ある辺がいずれかのノード間の最短経路に含まれるなら、その辺（が結ぶノード）も最短距離になるから。
cnt = 0
for i in range(N):
    for c, b in es[i]:
        if d[i][b] != c:
            cnt += 1

# 無向グラフなので２方向分カウントされてるから２で割る
print(cnt//2)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d=[[10**18]*n for i in range(n)]
e=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c
    e.append([a-1,b-1,c])
for i in range(n):
    d[i][i]=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])

print(sum(c>d[a][b] for a,b,c in e))

Submission status: Accepted

Solution code:
def warshall_floyd(d, next_node):
    # d: nxn adjacent matrix
    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]
                    next_node[i][j] = next_node[i][k]
 
 
INF = float("inf")
 
n, m = map(int, input().split())
d = [[INF] * n for _ in range(n)]
next_node = [list(range(n)) for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for j in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c
 
warshall_floyd(d, next_node)
 
used_path = set()
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        used_path.add((i, next_node[i][j]))
        used_path.add((next_node[i][j], i))
 
ans = m - len(used_path) // 2
 
print(ans)

Submission status: Accepted

Solution code:
def warshal(N, 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])
    return d

def main():
    N, M = map(int, input().split())
    d = [[float('inf')] * N for _ in range(N)]
    edges = []

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

    warshal(N, d)

    cnt = 0
    for edge in edges:
        if d[edge[0]][edge[1]] != edge[2]:
            cnt += 1

    print(cnt)

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
d =[[float('inf') for _ in range(n)] for _ in range(n)]
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,b,c))
for i in range(n):
    d[i][i] = 0
# warshall_floyd
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])
s = set()
for i in range(n):
    for j in range(m):
        if d[i][edges[j][0]-1] + edges[j][2] == d[i][edges[j][1]-1]:
            s.add(j)
print(m-len(s))

Submission status: Accepted

Solution code:

from collections import defaultdict
from heapq import heappop, heappush


class Graph():

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra():

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

        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)

            if self.dist[u] < dist_u:
                continue

            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):

        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal

        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]


g=Graph()
n,m=map(int,input().split())
from collections import defaultdict
e=defaultdict(int)
for _ in range(m):
    a,b,c=map(int,input().split())
    g.add_edge(a,b,c)
    g.add_edge(b,a,c)
    a,b=min(a,b),max(a,b)
    e[(a,b)]+=1



d=[0]*(n+1)
d[0]=1
for i in range(1,n+1):
    dd=Dijkstra(g,i)
    for j in range(i+1,n+1):
        l=dd.shortest_path(j)
        for k in range(1,len(l)):
            a,b=min(l[k-1:k+1]),max(l[k-1:k+1])
            e[(a,b)]=0
ans=0
for v in e.values():
    ans+=v

print(ans)

Submission status: Accepted

Solution code:
INF = 10**18

N,M = map(int,input().split())
edge = [list(map(int,input().split())) for _ in range(M)]
graph = [[INF for j in range(N)] for i in range(N)]

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

for e in edge:
    graph[e[0]-1][e[1]-1] = e[2]
    graph[e[1]-1][e[0]-1] = e[2]
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] != INF and graph[k][j] != INF:
                graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j])

ans = 0

for e in edge:
    if graph[e[0]-1][e[1]-1] != e[2]:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
bri=[[] for _ in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  bri[a-1].append([b,c])
  bri[b-1].append([a,c])

ans=0  
for i in range(N):
  a=i+1
  nseen=list(range(1,N+1))
  dist=[float("inf")]*N
  dist[a-1]=0
  q=[[dist[i],i] for i in range(N)]
  heapq.heapify(q)
  while q:
    d,ind=heapq.heappop(q)
    if d<=dist[ind]:
      for n,c in bri[ind]:
        if dist[n-1]>d+c:
          dist[n-1]=d+c
          heapq.heappush(q,[dist[n-1],n-1])
  for b,c in bri[i]:
    if a<b:
      if dist[b-1]<c:
        ans+=1
        
print(ans)

Submission status: Accepted

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]*m
B = [0]*m
C = [0]*m
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: Accepted

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

n,m = map(int,input().split())
edges = [[int(x) for x in input().split()] for i in range(m)]
graph = [[False]*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)

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

print(ans)

Submission status: Accepted

Solution code:
import heapq
def dijkstra(n, edge, dist, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u in edge[v]:
            if min_dist[u] > min_dist[v] + dist[v][u]:
                min_dist[u] = min_dist[v] + dist[v][u]
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

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

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

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

e = set()
for i in range(n):
    md, path = dijkstra(n, edge, dist, i)
    for i, p in enumerate(path):
        if p == -1: continue
        if i <= p: e.add((i, p))
        else: e.add((p, i))

print(m - len(e))

Submission status: Accepted

Solution code:
INF = float('inf')

def dijkstra(s,N,M,cost,ans):
  d = [INF] * N
  used = [False] * N
  d[s] = 0
  prvv = [[] for _ in range(N)]
  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 j in range(N):
      if d[j] > d[v]+cost[v][j]:
        d[j] = d[v]+cost[v][j]
        prvv[j] = [v]
      elif d[j] == d[v]+cost[v][j]:
        d[j] = d[v]+cost[v][j]
        prvv[j].append(v)
  
  for i, vs in enumerate(prvv):
    for v in vs:
      ans.add(tuple(sorted([v,i])))

  return prvv

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

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


ans =set([])
for i in range(N):
  dijkstra(i,N,M,cost,ans)
print(M-len(ans))
#print(ans)

Submission status: Accepted

Solution code:
# ワーシャル-フロイド法
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

##############################
n,w = map(int,input().split()) #n:頂点数　w:辺の数
d = [[float('inf') for i in range(n+1)] for i in range(n+1)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
W = []
for i in range(w):
    x,y,z = map(int,input().split())
    W.append((x,y,z))
    d[x][y] = z
    d[y][x] = z
for i in range(n+1):
    d[i][i] = 0 #自身のところに行くコストは０
a = 0
warshall_floyd(d)
for i in range(w):
    x,y,z = W[i][0],W[i][1],W[i][2]
    if d[x][y] < z:
        a += 1
print(a)

Submission status: Accepted

Solution code:
#隣接する点へいく最短経路で使われないことが必要。かつ十分
n,m = map(int, input().split( ))

Ad = [[] for _ in range(n)]
for _ in range(m):
    ai,bi,ci = map(int, input().split( ))
    ai -= 1
    bi -= 1
    Ad[ai].append((bi,ci))
    Ad[bi].append((ai,ci))

dp = [[10**10 for i in range(n)] for j in range(n)]
for i in range(n):
    dp[i][i] = 0
    for b,c in Ad[i]:
        dp[i][b] = c

ans = []

for k in range(n):
    for i in range(n):
        for b,c in Ad[i]:
            if dp[i][b]>dp[i][k]+dp[k][b]:
                ans.append((i,b))
                dp[i][b] = dp[i][k]+dp[k][b]
        for j in range(n):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])
ans = set(ans)
#print(ans)
print(len(ans)//2)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

data=np.zeros((n+1,n+1))
for u in abc:
    a,b,c=u
    data[a,b]=c
    data[b,a]=c
qqq=shortest_path(data,directed=False).astype(int)

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

Submission status: Accepted

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

data=[[inf]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    data[i][i]=0
lst=[]
for u in range(m):
    a,b,c=map(int,input().split())
    data[a][b]=c
    data[b][a]=c
    lst.append([a,b,c])

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

ans=0
for u in lst:
    a,b,c=u
    if data[a][b]!=c:
        ans+=1

print(ans)

Submission status: Accepted

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

# main
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in range(M)]

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

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

csg = csgraph_from_dense(g)
d = floyd_warshall(csg, directed=False)

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

print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(n,d):
    #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 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: Accepted

Solution code:
import sys
import copy


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    wn, wm = list(map(int, readline().split()))
    inf = 10 ** 13
    wl = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl[i][i] = 0

    for i in range(wm):
        wa, wb, wc = list(map(int, input().rstrip('\n').split()))
        wl[wa - 1][wb - 1] = wc
        wl[wb - 1][wa - 1] = wc

    cwl = copy.deepcopy(wl)
    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])
    cnt = 0
    for i in range(wn):
        for j in range(wn):
            if cwl[i][j] != 10 ** 13 and cwl[i][j] != wl[i][j]:
                cnt += 1
    print(cnt // 2)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import copy


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    wn, wm = list(map(int, input().rstrip('\n').split()))

    inf = 10 ** 13
    wl = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl[i][i] = 0

    for i in range(wm):
        wa, wb, wc = list(map(int, input().rstrip('\n').split()))
        wl[wa - 1][wb - 1] = wc
        wl[wb - 1][wa - 1] = wc

    cwl = copy.deepcopy(wl)

    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    cnt = 0
    for i in range(wn):
        for j in range(wn):
            if cwl[i][j] != wl[i][j] and cwl[i][j] != 10 ** 13:
                cnt += 1
    print(cnt // 2)


if __name__ == '__main__':
    solve()