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:
# https://atcoder.jp/contests/abc051/tasks/abc051_d
# 考えたこと
# 1.経路復元
# 2.ダイクストラ時に使った辺記録(こっちで解いてみる)


# あとで必要なのでクラスを準備しておく
from heapq import heapify, heappop, heappush, heappushpop

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


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


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

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


INF = 10**9 + 1


def dijkstra(adj: list, s: int, N: int):
    Color = [0] * N  # 0:未訪問 1:訪問経験あり 2:訪問済み(そこまでの最短経路は確定済み)
    D = [INF] * N  # 本のdと同じ 始点からの距離を記録する
    P = [None] * N  # 本のpと同じ 最短経路木における親を記録する

    # スタートとするノードについて初期化
    D[s] = 0  # スタートまでの距離は必ず0
    P[s] = None  # 親がない(ROOTである)ことを示す
    PQ = PriorityQueue([(0, s)])  # (コスト, ノード番号)で格納 こうするとPQでソートするときに扱いやすい

    # while True:
    while PQ:  # PQに候補がある限り続ける
        # min_cost = INF
        # for i in range(N):
        #     if Color[i] != 2 and D[i] < min_cost:
        #         min_cost = D[i]
        #         u = i
        min_cost, u = PQ.pop()  # 上記の処理はこのように簡略化できる

        Color[u] = 2  # uは訪問済み これから最短経路木に突っ込む作業をする

        if D[u] < min_cost:
            # もし今扱っているmin_costがメモしているやつよりも大きいなら何もしないで次へ(メモしている方を扱えばいいので)
            continue

        # 以下のforではsからの最短経路木にuを追加したときの更新、uまわりで次の最短経路になる候補の更新をしている
        for idx_adj_u, w_adj_u in adj[u]:
            if Color[idx_adj_u] != 2:
                # 訪問済みでなく、u→vへの経路が存在するならば
                if D[u] + w_adj_u < D[idx_adj_u]:
                    D[idx_adj_u] = D[u] + w_adj_u  # u周りにおける最短経路の候補の更新
                    P[idx_adj_u] = u
                    PQ.push((D[idx_adj_u], idx_adj_u))  # ここで候補に追加していっている
                    Color[idx_adj_u] = 1

    return D, P


# load datas
N, M = read_ints()
adj = [[] for _ in range(N)]  # (node_id, 隣接要素, 隣接nodeidとコスト)の順で格納する
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj[a].append((b, c))
    adj[b].append((a, c))

used_edges = set()
for s in range(N):
    _, P = dijkstra(adj, s, N)
    for i, p in enu(P):
        if p == None:
            continue
        if p > i:
            i, p = p, i
        used_edges.add((i, p))

print(M - len(used_edges))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

    N, W = map(int, input().split())
    #初期化
    dp = [[inf]*N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0
    abc = [list(map(int, input().split())) for _ in range(W)]
    for a,b,c in abc:
        dp[a-1][b-1] = c
        dp[b-1][a-1] = c

    #kを経由してiからjに行く行き方を考える
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dp[i][k]==inf or dp[k][j]==inf:
                    continue
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
    
    res = 0
    for a,b,c in abc:
        for k in range(N):
            if dp[a-1][k] == c + dp[b-1][k]:
                res += 1
                break
    print(W - res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[[10**9]*n for i in range(n)]
edges=[]
for i in range(m):
  u,v,c=map(int,input().split())
  g[u-1][v-1]=g[v-1][u-1]=c
  edges.append((u-1,v-1,c))
for k in range(n):
  for i in range(n):
    for j in range(n):
      g[i][j]=min(g[i][j],g[i][k]+g[k][j])
cnt=0
flag=False
for u,v,c in edges:
  if g[u][v]==c:
    cnt+=1
print(m-cnt)

Submission status: Accepted

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

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

ans = m
for u, v, c in edges:
    flg = False
    for i in range(n):
        if d[i][v] + c == d[i][u]:
            flg = True
    
    if flg:
        ans -= 1

print(ans)

Submission status: Accepted

Solution code:
def 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])

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

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

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

warshall_floyd()
ans = 0

for a, b, c in edges:
    flag = True
    
    for i in range(N):
        for j in range(N):
            if d[i][a]+c+d[b][j]==d[i][j]:
                flag = False
    
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

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,w = map(int,input().split()) #n:頂点数　w:辺の数
dic=defaultdict(int)
d = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    x,y,z = abc[i]
    x,y=x-1,y-1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
tmp=warshall_floyd(d)

for i in range(m):
    a,b,c=abc[i]
    if tmp[a-1][b-1]==c:
        dic[(a,b)]+=1

print(m-len(dic))

Submission status: Accepted

Solution code:
INF=100000000
N,M=map(int,input().split())
a=[0]*1000
b=[0]*1000
c=[0]*1000
dist=[[INF for _ in range(100)] for _ in range(100)]
for i in range(M):
  a[i],b[i],c[i]=map(int,input().split())
  a[i]-=1
  b[i]-=1
for i in range(N):
  for j in range(N):
    if i==j:
      dist[i][j]=0
for i in range(M):
  dist[a[i]][b[i]]=min(dist[a[i]][b[i]],c[i])
  dist[b[i]][a[i]]=min(dist[b[i]][a[i]],c[i])
for k in range(N):
  for i in range(N):
    for j in range(N):
      dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
ans=M
for i in range(M):
  flag=False
  for j in range(N):
    if dist[j][a[i]]+c[i]==dist[j][b[i]]: flag=True
  if flag: ans-=1
print(ans)

Submission status: Accepted

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

edges = []
for _ in range(M):
    a,b,c = list(map(int,input().split()))
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c
    edges.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(N):
#     print(D[i])
ans = 0
for e in edges:
    used = False
    for s in range(N):
        if D[s][e[0]] + e[2] == D[s][e[1]]:
            used = True
    if not used:
        ans += 1
print(ans)

Submission status: Accepted

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

edges = []
for _ in range(M):
    a,b,c = list(map(int,input().split()))
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c
    edges.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(N):
#     print(D[i])
ans = 0
for e in edges:
    used = False
    for s in range(N):
        for t in range(N):
            if D[s][e[0]] + e[2] + D[e[1]][t] == D[s][t]:
                used = True
    if not used:
        ans += 1
print(ans)

Submission status: Accepted

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

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

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

#####
#print("d",d)
#print("vlist",vlist)
#print("prev",prev)
#####

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]
                prev[i][j] = prev[k][j]

for i in range(N):
    for j in range(N):
        if prev[i][j] == i:
            vlist[i][j] = 0

#####
#print("d",d)
#print("vlist",vlist)
#print("prev",prev)
#####

count = 0
for i in range(N-1):
    for j in range(i,N):
        if vlist[i][j] == 1 and vlist[j][i] == 1:
            count += 1

print(count)

Submission status: Accepted

Solution code:
n,m= map(int,input().split())
rg = [[999999999 for _ in range(n)] for _ in range(n)]
rgflg = [[False for _ in range(n)] for _ in range(n)]
for i in range(m):
    a,b,c= map(int,input().split())
    rg[a-1][b-1] = c
    rgflg[a-1][b-1] = True
    rg[b-1][a-1] = c
    rgflg[b-1][a-1] = True
count=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if rg[i][j] > rg[i][k] + rg[k][j]:
                rg[i][j] = rg[i][k] + rg[k][j]
                if rgflg[i][j]==True or rgflg[j][i]==True:
                    rgflg[i][j]=False
                    rgflg[j][i]=False
                    count+=1
print(count)

Submission status: Accepted

Solution code:

INF = 10**19

def dijkstra_back(s,t,n,w,cost):
    prev = [s] * n 
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

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

cost = [[float("inf") for i in range(N)] for j in range(N)]
edges = set()
for i in range(M):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    cost[a][b] = c
    cost[b][a] = c
    edges.add(min(a,b)*10**5 + max(a,b))

for i in range(N):
    for j in range(i+1,N):
        d = dijkstra_back(i,j,N,M,cost)
        for k in range(len(d)-1):
            a_ = min(d[k],d[k+1])
            b_ = max(d[k],d[k+1])
            X = a_*10**5+b_
            if X in edges:
                edges.remove(X)
print(len(edges))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
h=[list(map(int, input().split())) for i in range(M)]
s=[[10**6]*N for i in range(N)]
for i in h:
    s[i[0]-1][i[1]-1]=i[2]
    s[i[1]-1][i[0]-1]=i[2]
for i in range(N):
    for j in range(N):
        for k in range(N):
            s[j][k] = min(s[j][k],s[j][i] + s[i][k])
a=0
for i in h:
    if s[i[0]-1][i[1]-1]!=i[2]:
        a+=1
print(a)

Submission status: Accepted

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

d = [[10**10]*N for _ in range(N)]

m = {}

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][k] + d[k][j] < d[i][j]:
                d[i][j] = d[i][k] + d[k][j]

ans = 0

for e in m:
    a, b = e
    if d[a][b] < m[e]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    n,m=MI()
    dist=[[inf]*n for _ in range(n)]
    abc=[]
    for _ in range(m):
        a,b,c=MI()
        a,b=a-1,b-1
        abc.append((a,b,c))
        dist[a][b]=dist[b][a]=c
    for i in range(n):dist[i][i]=0
    for j in range(n):
        for i in range(n):
            for k in range(n):
                dist[i][k]=dist[k][i]=min(dist[i][k],dist[i][j]+dist[j][k])
    ans=0
    for a,b,c in abc:
        if dist[a][b]<c:ans+=1
    print(ans)

main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Map = [[int(1e18) for _ in range(N)] for __ in range(N)]
Path = [[[] for _ in range(N)] for __ in range(N)]
D = {}
for i in range(M):
  a, b, c = map(int, input().split())
  Map[a-1][b-1] = c
  Map[b-1][a-1] = c
  Path[a-1][b-1] = [a-1, b-1]
  Path[b-1][a-1] = [b-1, a-1]
  D[(a-1)*N+b-1] = 0
  D[(b-1)*N+a-1] = 0
for i in range(N):
  Map[i][i] = 0

for k in range(N):
  for i in range(N):
    for j in range(N):
      if Map[i][j] > Map[i][k] + Map[k][j]:
        Map[i][j] = Map[i][k] + Map[k][j]
        Path[i][j] = Path[i][k][:] + Path[k][j][1:]
        
for i in range(N):
  for j in range(N):
    X = Path[i][j][:]
    n = len(X)
    for k in range(n-1):
      l = X[k] * N + X[k+1]
      r = X[k+1] * N + X[k]
      if l in D:
        D[l] = 1
      if r in D:
        D[r] = 1
SUM41 = 0
for i in D:
  if D[i] == 0:
    SUM41 += 1
print(SUM41 // 2)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

N,M=map(int,input().split())
hen=[]
for i in range(0,M):
    a,b,length=map(int,input().split())
    hen.append((a-1,b-1,length))

shortest=[[10**20 for i in range(0,N)] for j in range(0,N)]

for i in range(0,M):
    a,b,length=hen[i]
    shortest[a][b]=length
    shortest[b][a]=length

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

count=0
for i in range(0,M):
    a,b,length=hen[i]
    if length!=shortest[a][b]:
        count+=1

print(count)

Submission status: Accepted

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

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


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

warshall_floyd(d)

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

Submission status: Accepted

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

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


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

warshall_floyd(d)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

n, m = map(int, input().split())
d = [[float("inf")]*n for i in range(n)]

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

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

warshall_floyd(d)

ans = m

for i, (a,b,c) in enumerate(abc):
    a,b = a-1,b-1
    for j in range(n):
        if  d[j][a] + c == d[j][b]:
            ans-=1
            break

print(ans)

Submission status: Accepted

Solution code:
inf = 10 ** 18
n, m = map(int, input().split())
d = [[inf for _ in range(n)] for _ in range(n)]
edge = [tuple(map(int, input().split())) for _ in range(m)]

for i in range(n):
    d[i][i] = 0
for a, b, c in edge:
    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])

ans = 0
for a, b, c in edge:
    if d[a-1][b-1] != c:
        ans += 1
print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import copy

def main():
    N,M=MI()
    inf=10**10
    adj=[[inf]*N for _ in range(N)]
    for i in range(N):
        adj[i][i]=0
        
    
    for i in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        adj[a][b]=c
        adj[b][a]=c
        
    d=copy.deepcopy(adj)
    
    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
    
    ans=0
    d=warshall_floyd(d)
    
    for i in range(N):
        for j in range(N):
            if d[i][j]!=adj[i][j] and adj[i][j]!=inf:
                ans+=1
                
    print(ans//2)
    
        
    
    
        

main()

Submission status: Accepted

Solution code:
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,w = map(int,input().split()) #n:頂点数　w:辺の数

d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
x = [0]*w
y = [0]*w
z = [0]*w
for i in range(w):
    x[i],y[i],z[i] = map(int,input().split())
    d[x[i]-1][y[i]-1] = z[i]
    d[y[i]-1][x[i]-1] = z[i]
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
d = warshall_floyd(d)

res = 0
for i in range(w):
    if z[i] > d[x[i]-1][y[i]-1]:
        res += 1
print(res)

Submission status: Accepted

Solution code:
from copy import deepcopy
N, M = map(int, input().split())
INF = 10**9+7
graph = [[INF for _ in range(N)] for l in range(N)]

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

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

newGraph = deepcopy(graph)

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]
tmp = []

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

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

ans = 0
for a, b, c in tmp:
    if c > graph[a][b]:
        ans += 1

print(ans)

Submission status: Accepted

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

# dは隣接頂点間のコスト、Nは頂点の個数
def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

# input
N, W = [int(x) for x in input().split()] # N:頂点数、W:辺の数
inf = float("inf")

# d[i][v]:辺(i, v)間のコスト、存在しなければinf
d = [[inf] * N for _ in range(N)]
abc = []

for _ in range(W):
    a, b, c = [int(x) for x in input().split()]
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c
    abc.append([a, b, c])

# 自身の頂点へのコストは0
for i in range(N):
    d[i][i] = 0

d = warshall_floyd(d)
cnt = 0

for i in range(W):
    a, b, c = abc[i]
    if d[a - 1][b - 1] != c:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import *
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for i,(a,b,c) in enumerate(ABC):
    data[a].append([b,c,i])
    data[b].append([a,c,i])


mlst=set()

for sp in range(1,N+1):
    visited={sp}
    dic={}
    stack=[]
    distance=[0 for i in range(N+1)]
    for p,c,i in data[sp]:
        if not c in dic:
            dic[c]=[[p,i]]
            stack.append(c)
        else:
            dic[c].append([p,i])
            stack.append(c)
    heapify(stack)
    while stack:
        m=heappop(stack)
        a,i=dic[m].pop()
        if a in visited:
            if distance[a]==m:
                mlst.add(i)
            continue
        visited.add(a)
        mlst.add(i)
        distance[a]=m
        for p,c,i in data[a]:
            if not p in visited:
                C=m+c
                heappush(stack,C)
                if C in dic:
                    dic[C].append([p,i])
                else:
                    dic[C]=[[p,i]]
print(M-len(mlst))

Submission status: Accepted

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

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

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

dist = floyd_warshall(csr_matrix(graph))

ans = 0
for a, b, c in abc:
    a -= 1
    b -= 1

    if dist[a][b] != c:
        ans += 1

print(ans)

Submission status: Accepted

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

Solution code:
n,m=map(int,input().split())
INF=10**18
edge=[[INF]*n for i in range(n)]
s=[]
for i in range(m):
  u,v,c=map(int,input().split())
  edge[u-1][v-1]=edge[v-1][u-1]=c
  s.append((u-1,v-1,c))
for k in range(n):
  for i in range(n):
    for j in range(n):
      edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
cnt=0
for i,j,cost in s:
  if edge[i][j]==cost:
    cnt+=1
print(m-cnt)

Submission status: Accepted

Solution code:
def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

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

    e[i][0] = a
    e[i][1] = b
    e[i][2] = c

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

d = warshal_floyd(d)
ans = 0
for i in range(m):
    a = e[i][0]
    b = e[i][1]
    c = e[i][2]
    for k in range(n):
        if d[a][k] == c + d[b][k]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

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

    e[i][0] = a
    e[i][1] = b
    e[i][2] = c

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

d = warshal_floyd(d)
ans = 0
for i in range(m):
    a = e[i][0]
    b = e[i][1]
    c = e[i][2]
    for k in range(n):
        if d[a][k] == c + d[b][k]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s,g):
    used = [True] * n #True:未確定
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,[e[0],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        if v==g:
            return minedge[0]
        kai=minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+kai,e[1]])                   
    return -1

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

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
pp=[]
for i in range(m):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])
    pp.append([x-1,y-1,z])
ans=0
for i in range(m):
    if pp[i][2]>dijkstra_heap(pp[i][0],pp[i][1]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = {}
for i in range(m):
    a,b,c = inm()
    if a not in dst:
        dst[a] = {}
    dst[a][b] = c
    if b not in dst:
        dst[b] = {}
    dst[b][a] = c
d = [[BIG]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    d[i][i] = 0
    for j in dst[i]:
        d[i][j] = dst[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])
sm = 0
for i in range(1,n):
    for j in range(i+1,n+1):
        if j in dst[i] and dst[i][j]>d[i][j]:
            sm += 1
print(sm)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
l = []
for i in range(m):
    l.append(list(map(int,input().split())))

wf=[[10**10 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c = l[i]
    wf[a-1][b-1] = c
    wf[b-1][a-1] = c
for i in range(n):
    wf[i][i]=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            wf[i][j] = min(wf[i][j],wf[i][k]+wf[k][j])

ans=0
for edge in l:
    ok=False
    for i in range(n):
        for j in range(n):
            dist = wf[i][j]
            if dist == wf[i][edge[0]-1] + edge[2] + wf[edge[1]-1][j]:
                ok=True
    if not ok:
        ans+=1
print(ans)

Submission status: Accepted

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

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

if __name__ == "__main__":
    n,e = map(int,readline().split()) #n:頂点数　e:辺の数
    matrix = [[float("inf") for i in range(n)] for j in range(n)]
    lst1 = []
    for i in range(e):
        x,y,w = map(int,readline().split())
        x,y = x-1,y-1
        matrix[x][y] = w
        matrix[y][x] = w
        lst1.append([x,y,w])
    for i in range(n):
        matrix[i][i] = 0
    matrix = warshall_floyd(matrix)

    ans = 0

    #全辺mについて全探索
    for i in range(e):
        flag = True
        for j in range(n):
            for k in range(n):
                if matrix[j][k] == matrix[j][lst1[i][0]] + lst1[i][2] + matrix[lst1[i][1]][k]:
                    flag = False
        if flag:
            ans += 1
    print(ans)