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:
#単一始点最短経路問題
#Bellman-Ford法よりも高速
#ただし、負の辺がある場合は使えない

#隣接リストとpriority queueを用いたDijkstra法
#O(M log N)
#負の辺が含まれるときうまくいかない-->負の辺が含まれるときはBellman-Ford法を使う必要がある
INF = 10 ** 9
#入力
N, M = map(int, input().split())
#辺を管理する隣接リスト

G = [[] for _ in range(N)]
for i in range(M):
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    #0-indexに変換して処理
    G[l-1] += [[s, r-1, i]]
    G[r-1] += [[s, l-1, i]]
# print (G)

#始点sから各頂点への最短距離を求める
def dijksrea(s): #始点s
    import heapq
    s -= 1 #始点を0-indexに変える
    d[s] = 0 #始点の距離を0にする
    pque = []
    heapq.heappush(pque, [0, s]) #要素を[距離、頂点]として管理　最初の位置を入れる

    while len(pque) != 0: #queの中に要素が残っている時
        p = heapq.heappop(pque) #最も距離が短いものを取り出す
        v = p[1] #距離が最も短い頂点
        if d[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ
            continue
        for i in range(len(G[v])): #頂点vの隣接リストを走査
            e = G[v][i]
            if d[e[1]] > d[v] + e[0]: #距離が更新できるかを検討
                d[e[1]] = d[v] + e[0]
                prev[e[1]] = [v, e[2]]
                heapq.heappush(pque, [d[e[1]], e[1]]) #更新できた場合、その値をpqueに入れる

# dijksrea(1)
# print (d)
# print (prev)
#最短経路復元
# edge_num = []
def restore(g): #gまでの最短経路を復元
    g -= 1 #0-indexに直す
    path.append(g)
    edge_num.append(prev[g][1])
    g = prev[g][0]
    while g != -1:
        path.append(g)
        # ans_lst[prev[g][1]] = True #辺を使った処理をする
        edge_num.append(prev[g][1])
        g = prev[g][0]
    path.reverse()
    return path

ans_lst = [False] * M #False使われていない

for i in range(1, N):
    d = [INF] * N #頂点sからの距離
    prev = [[-1, -1] for _ in range(N)] #最短経路復元のためのリスト
    dijksrea(i) #スタート地点から最小距離を処理
    for j in range(i + 1, N + 1):
        path = []
        edge_num = []
        restore(j)
        for k in edge_num[:-1]:
            ans_lst[k] = True
        # print ('i, j',  i, j,  restore(j)) #ゴール地点まで
        # print (ans_lst)
        # print (edge_num)
# print (ans_lst)
print (ans_lst.count(False))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
g = [[float('INF')] * (N + 1) for _ in range(N + 1)]
abc = []
for _ in range(M):
    a, b, c = map(int, input().split())
    abc.append((a, b, c))
    g[a][b] = c
    g[b][a] = c
for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = 0
for a, b, c in abc:
    if g[a][b] != c:
        ans += 1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC51 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,m = map(int,input().split())
w = [[float('inf')]*n for _ in range(n)]
x = [list(map(int,input().split())) for _ in range(m)]
for a,b,c in x:
    w[a-1][b-1] = c
    w[b-1][a-1] = c

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

ans = 0
for i in x:
    a,b,c = i
    if w[a-1][b-1] < c:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
es = [[] for _ in range(N)]

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


def djkstra(start, n, es):
    # start：スタート地点のノード
    # n：ノード数
    # es：edges, ある辺のコスト

    # 最初は全部未探索
    costs = [INF] * n
    costs[start] = 0
    checked = [False] * n #調べ終わったノードはTrue
    hq = [(0, start)] # スタートからスタートまでのコスト（＝０）とスタートの番号
    heapq.heapify(hq)
    while hq: # キューに残りがある限り
        cost, v = heapq.heappop(hq) # 取り出す
        if checked[v]:
            continue # 既に調べていたら飛ばす
        checked[v] = True
        costs[v] = cost
        for to, c in es[v]: # ノードvから伸びている辺すべてについて
            if costs[to] <= cost + c:
                continue # 現時点で発覚しているtoまでのコストのほうが、v経由でto行くまでのコストより小さいなら更新せず飛ばす
            heapq.heappush(hq, (cost+c, to)) # toに行くまでの最短距離がcost+cに更新される
        
    return costs


min_cost = [[] for _ in range(N)]
for i in range(N):
    min_cost[i] = djkstra(i,N,es)

ans = 0
for i in range(len(es)):
    for to, c in es[i]:
        if min_cost[i][to] < c:
            #print("--------")
            #print(i,to,c)
            ans += 1

print(ans//2)
#print(min_cost)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC51 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,m = map(int,input().split())
edge = [[] for _ in range(n)]
w = [[float('inf')]*n for _ in range(n)]
x = []
for _ in range(m):
    a,b,c = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    w[a-1][b-1] = c
    w[b-1][a-1] = c
    x.append([a,b,c])

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

ans = 0
for i in x:
    a,b,c = i
    if w[a-1][b-1] < c:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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



"""
以下実行例
"""
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in input().split()]

"""隣接行列の初期化"""
dist = [[float("inf")]*n for _ in [0]*n]
for i in range(n):
    dist[i][i] = 0

e = []
for _ in range(m):
    a,b,t = [int(i) for i in input().split()]
    dist[a-1][b-1] = t
    dist[b-1][a-1] = t
    e.append((a-1,b-1,t))

Floyd_Warshall(dist)

ans = 0
for a,b,t in e:
    if t > dist[a][b]: ans += 1

print(ans)

Submission status: Accepted

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

def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    inf = 10 ** 5 + 1
    length_data = [[inf for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(edge_num):
        a, b, c = data[i]
        length_data[a][b] = c
        length_data[b][a] = c

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

    ans = 0
    for i in range(edge_num):
        a, b, c = data[i]
        if c > length_data[a][b]:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    inf = 10 ** 5 + 1
    length_data = [[inf for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(edge_num):
        a, b, c = data[i]
        length_data[a][b] = c
        length_data[b][a] = c

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

    ans = 0
    for i in range(edge_num):
        a, b, c = data[i]
        if c > length_data[a][b]:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from collections import defaultdict
import heapq


def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    graph_data = defaultdict(set)
    weight_data = defaultdict(int)

    for i in range(edge_num):
        a, b, c = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)
        weight_data[(a, b)] = c
        weight_data[(b, a)] = c

    # used_edge = set()

    inf = 10 ** 5 + 1

    length_data = [[inf for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(1, node_num + 1):
        visit_flg = [0 for i in range(node_num + 1)]
        visit_flg[i] = 1
        length_data[i][i] = 0
        # for j in range(1, i):
        #     visit_flg[j] = 1
        #     length_data[i][j] = length_data[j][i]
        # print(length_data, ',,mm')
        heap_list = []
        for ele in graph_data[i]:
            weight = weight_data[(i, ele)]
            heapq.heappush(heap_list, (weight, ele, i))

        while len(heap_list) > 0:
            now_weight, now_ele, pre_ele = heapq.heappop(heap_list)
            # print(visit_flg, 'vf')
            if visit_flg[now_ele]:
                continue
            visit_flg[now_ele] = 1
            length_data[i][now_ele] = length_data[i][pre_ele] + weight_data[(pre_ele, now_ele)]
            # used_edge.add((min(now_ele, pre_ele), max(now_ele, pre_ele)))
            for next_ele in graph_data[now_ele]:

                if visit_flg[next_ele]:
                    continue
                next_weight = weight_data[(now_ele, next_ele)] + length_data[i][now_ele]
                heapq.heappush(heap_list, (next_weight, next_ele, now_ele))

            # print(used_edge, 'ue')
            # print(heap_list, 'hl')
            # print(visit_flg, 'vf')
            # print(length_data, 'ld')
            # print()
        # print(length_data[i])

    # print(length_data)

    ans = 0
    for i in range(edge_num):
        a, b, c = data[i]
        if c > length_data[a][b]:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*M]
INF = 10**9
d = [[INF]*N for _ in [0]*N]
for i in range(N):
    d[i][i] = 0
for a,b,c in ABC:
    d[a-1][b-1] = c
    d[b-1][a-1] = c
def Warshall_Floyd(d,N=None):
    if N==None : N = len(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,N)
print(sum(d[a-1][b-1]!=c for a,b,c in ABC))

Submission status: Accepted

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

# 15行目ぐらいまでワーシャルフロイドの前処理
INF = 10 ** 10
dist = [[INF] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

a = [0] * M
b = [0] * M
c = [0] * M
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]

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

res = 0
for i in range(M):
    # 最短経路が直接の頂点a-b間の距離でなかった時、（迂回ルートが最短距離の時）
    # 辺a-bはどの最短経路にも含まれないので+1する。
    if c[i] > dist[a[i]-1][b[i]-1]:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import itertools

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

# graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**20
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]
edges = []
for i in range(M):
    a,b,c = list(map(int,input().split(" ")))
    cost[a][b] = c
    cost[b][a] = c
    edges.append((a,b,c))
for i in range(1,N+1):
    cost[i][i] = 0
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):

            cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j])
            cost[j][i] = min(cost[j][i], cost[j][k] + cost[k][i])
ans = 0
for k,edge in enumerate(edges):
            a,b,c = edge
            if  cost[a][b] !=c:
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

# graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**20
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]
edges = []
for i in range(M):
    a,b,c = list(map(int,input().split(" ")))
    cost[a][b] = c
    cost[b][a] = c
    edges.append((a,b,c))
for i in range(1,N+1):
    cost[i][i] = 0
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j])

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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

n,m=map(int,input().split())
edge=[list(map(int,input().split())) for _ in range(m)]
g=[[float('inf')]*(n+1) for _ in range(n+1)]
for a,b,c in edge:
  g[a][b]=c
  g[b][a]=c
d=floyd_warshall(g)
ans=0
for a,b,c in edge:
  for i in range(1,n+1):
    if d[i][a]+c==d[a][b]:
      break
  else:
    ans+=1
print(ans)

Submission status: Accepted

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
    dist[b][a] = c
    
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: Accepted

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

inf = 1000000
L = [[0] * N for _ in range(N)]
C = [[inf] * N for _ in range(N)]
for i in range(M):
  a, b, c = abc[i]
  a -= 1
  b -= 1
  C[a][b] = c
  C[b][a] = c

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

for k in range(N):
  for i in range(N):
    for j in range(N):
      if C[i][j] > C[i][k] + C[k][j]:
        C[i][j] = C[i][k] + C[k][j]
        L[i][j] = 1

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

print(M - ((N * (N - 1) // 2) - (n // 2)))

Submission status: Accepted

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

INF = float('inf')

vec1 = [[INF] * N for _ in range(N)]
vec2 = [[INF] * N for _ in range(N)]

for _ in range(M) :
    a, b, c = map(int, input().split())
    vec1[a-1][b-1] = vec1[b-1][a-1] = vec2[a-1][b-1] = vec2[b-1][a-1] = c
    
for i in range(N) :
    vec1[i][i] = vec2[i][i] = 0
    
for k in range(N) :
    for i in range(N) :
        for j in range(N) :
            vec1[i][j] = min(vec1[i][j], vec1[i][k] + vec1[k][j])

ret = 0            
for i in range(N) :
    for j in range(i+1, N) :
        if vec2[i][j] != INF and vec1[i][j] != vec2[i][j] :
            ret += 1

print(ret)

Submission status: Accepted

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

# N:頂点, M:辺
N, M = map(int, input().split())

d = [[float('inf') for i in range(N)] for i in range(N)]

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

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

warshall_floyd(d,N)
cnt = 0
for edge in edges:
    if d[edge[0]][edge[1]] != edge[2]:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import heapq


def dijkstra(adj, start, goal=None):
    num = len(adj)          # グラフのノード数
    dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
    prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

    dist[start] = 0
    # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
    q = []
    heapq.heappush(q, (0, start))  # 始点をpush

    while q:
        prov_cost, src = heapq.heappop(q)  # pop

        # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
        if dist[src] < prov_cost:
            continue

        # 他の頂点の探索
        for dest in range(num):
            cost = adj[src][dest]
            if cost != float('inf') and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost  # distの更新
                # キューに新たな仮の距離の情報をpush
                heapq.heappush(q, (dist[dest], dest))
                prev[dest] = src                      # 前の頂点を記録

    return dist


n, m = map(int, input().split())
mat = [[float('inf')] * n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c
for i in range(n):
    mat[i][i] = 0
mat2 = []
for i in range(n):
    mat2.append(dijkstra(mat, i))
ans = 0
for i in range(n):
    for j in range(i, n):
        if mat[i][j] != float('inf') and mat[i][j] != mat2[i][j]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

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

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]


N, M = map(int, input().split())
graph = Dijkstra()
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c, directed=False)

usedPaths = collections.defaultdict(set)
for i in range(N):
    for j in range(i+1, N):
        path = graph.getDijkstraShortestPath(i, j)
        if len(path) == 2:
            usedPaths[path[0]].add(path[1])
            usedPaths[path[1]].add(path[0])
        else:
            for k, v in enumerate(path[:-1]):
                usedPaths[v].add(path[k + 1])
                usedPaths[path[k + 1]].add(v)

ans = M - sum([len(a) for a in list(usedPaths.values())])//2
print(ans)

Submission status: Accepted

Solution code:
# 頂点の数（N）および辺の数（M）を入力する
N, M = map(int, input().split())

# 辺の長さを格納する辞書（dic_edge_dist）を設定する
dic_edge_dist = {(i, j) : float("inf") for i in range(1, N + 1) for j in range(1, N + 1)}
for i in range(1, N + 1):
    dic_edge_dist[(i, i)] = 0
# 辺を格納するリスト（list_edge）を設定する
list_edge = []

def warshall_floyd(dic_edge_dist):
    dic_shortest_dist = dic_edge_dist.copy()
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                dic_shortest_dist[(j, k)] = min(dic_shortest_dist[(j, k)], dic_shortest_dist[(j, i)] + dic_shortest_dist[(i, k)])
    return dic_shortest_dist

# 各辺について、、
for _ in range(M):
    # 頂点および辺の長さを入力する
    a, b, c = map(int, input().split())
    # dic_edge_distに辺の長さを格納する
    dic_edge_dist[(a, b)] = c
    dic_edge_dist[(b, a)] = c
    # list_edgeに辺を格納する
    list_edge.append((min(a, b), max(a, b)))

dic_shortest_dist = warshall_floyd(dic_edge_dist)
    
edge_count = 0
for i, j in list_edge:
    for k in range(1, N + 1):
        if dic_shortest_dist[(k, i)] + dic_edge_dist[(i, j)] == dic_shortest_dist[(k, j)]:
            edge_count += 1
            break
        if dic_shortest_dist[(k, j)] + dic_edge_dist[(j, i)] == dic_shortest_dist[(k, i)]:
            edge_count += 1
            break

print(len(list_edge) - edge_count)

Submission status: Accepted

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

N,M = [int(x) for x in input().split()]
INF = float('inf')
edges = []
d = [[INF]*N for _ in range(N)]
for _ in range(M):
    a,b,c = [int(x) for x in input().split()]
    a-=1
    b-=1
    d[a][b]=c
    d[b][a]=c
    edges.append([a,b,c])

warshall_floyd(d,N)
cnt = 0
for e in edges:
    if(d[e[0]][e[1]]!=e[2]):
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

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

    def __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(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

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: Accepted

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.concatenate([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: Accepted

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
INF = 10**9
N, M = map(int, input().split())
d = [[INF] * (N+1) for i in range(N+1)]
for i in range(N+1):
    d[i][i] = 0
es = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b], d[b][a] = c, c
    es[i] = (a, b, c)
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])
ans = M
for k in range(M):
    i, j, c = es[k]
    for s in range(1, N+1):
        if d[s][i] + c == d[s][j]:
            ans -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
D = []
ans = 0
for i in range(n):
    t = [float('inf')]*n
    t[i] = 0
    D.append(t)
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
    L.append([a,b,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])
for i in range(m):
    a,b,c = L[i][0],L[i][1],L[i][2]
    if D[a-1][b-1] != c:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#ワ―シャルフロイド法   d=[[0,1],[2,0]]を最短コストに変換する感じ
def warshall_floyd(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

n,m=map(int,input().split())
abc=[]
d=[[10**9+7 for i in range(n)] for j in range(n)]
l=[[10**9+7 for i in range(n)] for j in range(n)]
for i in range(m):
    tmp=[int(j) for j in input().split()]
    abc.append(tmp)
    d[tmp[0]-1][tmp[1]-1]=tmp[2]
    d[tmp[1]-1][tmp[0]-1]=tmp[2]
    l[tmp[0]-1][tmp[1]-1]=tmp[2]
    l[tmp[1]-1][tmp[0]-1]=tmp[2]

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

ans=0
for i in range(n):
    for j in range(n):
        if d[i][j]!=l[i][j] and l[i][j]!=10**9+7:
            ans+=1
print(ans//2)

Submission status: Accepted

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

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

#print(graph,dist)

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

for n in range(N):

  for time in range(N):
    judge = 0
    for m in range(M):
      if dist[n][graph[m][0]-1]-dist[n][graph[m][1]-1] > graph[m][2]:
        dist[n][graph[m][0]-1]=dist[n][graph[m][1]-1]+graph[m][2]
        judge=1
      elif dist[n][graph[m][1]-1]-dist[n][graph[m][0]-1] > graph[m][2]:
        dist[n][graph[m][1]-1]=dist[n][graph[m][0]-1]+graph[m][2]
        judge=1
    if judge == 0:
      break

num = 0

for m in range(M):
  if dist[graph[m][0]-1][graph[m][1]-1] < graph[m][2]:
    num+=1
    
#print(dist)
  
    
print(num)