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:


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


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

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

    return n, m, edges

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

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

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

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

    d = warshall_floyd(d, n)

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

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

            if edge_inuse[e] == 1:
                break

    print(m - sum(edge_inuse))
    return


if __name__ == '__main__':
    submit()

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

D = np.full((N, N), IINF)
for a, b, c in ABC:
    D[a - 1][b - 1] = c
    D[b - 1][a - 1] = c

# warshall floyd
for via in range(N):
    D = np.minimum(D, sum(np.meshgrid(D[via], D[via], sparse=True)))

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

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

D = np.zeros((N, N))
for a, b, c in ABC:
    D[a - 1][b - 1] = c

min_dist = dijkstra(csgraph_from_dense(D), directed=False)
print((min_dist < D).sum())

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

D = np.full((N, N), IINF)
for a, b, c in ABC:
    D[a - 1][b - 1] = c
    D[b - 1][a - 1] = c

# warshall floyd
for via in range(N):
    D = np.minimum(D, sum(np.meshgrid(D[via], D[via])))

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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
INF = float('inf')
N,M = map(int,input().split())
g = [[INF]*N for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    g[a-1][b-1] = c
    g[b-1][a-1] = c
d = dijkstra(g)
ans = 0
for i in range(N):
    for j in range(N):
        if g[i][j] != INF and g[i][j] > d[i][j]:
            ans += 1
ans //= 2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product, combinations

def floyd_warshall(V, E):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
    Output:
        If there exists a negative cycle, return None
        Otherwise return dist: the table of the minimum cost between arbitrary vertex u, v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = {u: {v: INF for v in V} for u in V}
    path = {u: {v: None for v in V} for u in V}
    for v in V:
        dist[v][v] = 0; path[v][v] = -1
        for u, c in E[v].items(): dist[v][u] = c; path[v][u] = v;
    for k, i, j in product(V, repeat=3):
        if dist[i][j] > dist[i][k] + dist[k][j]:
            dist[i][j] = dist[i][k] + dist[k][j]
            path[i][j] = path[k][j]
    for v in V:
        if dist[v][v] < 0: return None, None
    return dist, path


N, M = map(int, input().split())
E = defaultdict(dict)
cand = set()
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c
    cand |= {(min(a-1, b-1), max(a-1, b-1))}
V = list(range(N))
_, path = floyd_warshall(V, E)
for i, j in combinations(V, 2):
    temp = set()
    while path[i][j] != -1:
        temp |= {(path[i][j], j)} if path[i][j] < j else {(j, path[i][j])}
        j = path[i][j]
    cand -= temp
print(len(cand))

Submission status: Accepted

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

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

edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0] * N for _ in range(N)]
for a,b,c in edge:
  graph[a-1][b-1] = c
  
graph = csgraph_from_dense(graph)

dist = floyd_warshall(graph,directed=False)
answer = (graph > dist).sum()
print(answer)

Submission status: Accepted

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

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

edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0] * N for _ in range(N)]
for a,b,c in edge:
  graph[a-1][b-1] = c
  
graph = csgraph_from_dense(graph)

dist = floyd_warshall(graph,directed=False,overwrite=True).astype(int)

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

Submission status: Accepted

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

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

edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0] * N for _ in range(N)]
for a,b,c in edge:
  graph[a-1][b-1] = c
  
graph = csgraph_from_dense(graph)

dist = floyd_warshall(graph,directed=False).astype(int)

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

Submission status: Accepted

Solution code:
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
n,m=map(int,input().split())
table=[[0]*n for i in range(n)]
Edge=[None]*m
for i in range(m):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
    Edge[i]=[a,b,c]
d=floyd_warshall(csgraph=table, directed=False, return_predecessors=False)
ans=0
for i in range(m):
  a,b,c=Edge[i]
  if d[a-1][b-1]<c:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = [[] for _ in range(N)]
    used_edge = set()

    # ダイクストラ
    def dijkstra(start, edge):
        costs=[inf]*N
        costs[start]=0
        queue = [(0, start, (-1,-1))]  # 第一要素が優先的に評価されるので 第３要素にpre(前の頂点)が入る
        hash = {}
        while queue:
            c, from_, e = heappop(queue)
            hash[from_]=1
            if costs[from_] >= c:
                costs[from_] = c
                used_edge.add(e)
            for cost,node in edge[from_]:
                if node in hash:
                    continue
                e = tuple(sorted([from_,node]))
                heappush(queue, (c + cost, node,e))



    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge[a].append((c, b))
        edge[b].append((c, a))
        
    for start in range(N):
        dijkstra(start, edge)
    
    num_used_edge = len(used_edge)-1
    print(M-num_used_edge)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

# dijkstra（経路復元できるパターン）
from collections import defaultdict
import heapq
# sからすべての頂点への最小距離を求める O(|E| log |V|)
# 戻り値は min_dist_list, routelist。
# m_d_l : [0への最小距離, 1への最小距離, 2への最小距離, ...]
#  辿り着けないノードの場合、関数内で定義した定数INFを返す
# rl : [0の直前ノード, 1の直前ノード, ...] ただしlist[始点]は-1が入る
#  （注）本来到着不可能なノードでも、INF距離で辿り着けく設定なので経路が返る
# s: startノード
# n: 頂点数
# グラフデータは辞書を使っている。{ノードID:[(to,cost)を格納したリスト],...}
#  graph[nodeID] = [(to1, cost1), (to2, cost2), ...]
# 存在しないキーがエラーになってしまうと困るので、
# graph = defaultdict(list)として、要素を空リストで初期化して生成する
def dijkstra(s: int, n: int, graph: dict) -> list:
  INF = 10 ** 10 #INF以上の経路が存在する可能性がある場合は注意か？？
  que = []    # [(最短距離, node番号)]
  routelist = [-1] * n # routelist[node番号] = 最短経路における1つ前のノード
  heapq.heappush(que, (0, s))
  min_dist_list = [INF] * n
  min_dist_list[s] = 0
  while que:
    now_dist, node = heapq.heappop(que)

    if min_dist_list[node] < now_dist:
      continue

    for to, dist in graph[node]:
      new_dist = now_dist + dist
      if min_dist_list[to] > new_dist:
        min_dist_list[to] = new_dist
        routelist[to] = node
        heapq.heappush(que, (new_dist, to))

  return min_dist_list, routelist

N, M = mi()
SGDs = [tuple(mi()) for _ in range(M)] #start, goal, distance

#dijkstra()に渡すためのグラフデータを生成する
Graph = defaultdict(list) #辞書をlist()で初期化
for s, g, d in SGDs: #start, goal, distance
  s, g = s-1, g-1 #入力が1スタートなので0スタートに訂正
  Graph[s].append((g, d)) #nodeIDがkeyになっているdict-->dict[key]（list）に(行き先番号, 距離を入れていく)
  Graph[g].append((s, d)) #無向グラフなので逆向きも入れる

#最短経路に含まれる辺をこの集合に格納していく
#格納するのはタプル(s, g)。無向グラフなので両面を入れるように注意
Contained_Edge = set()
for eachstart in range(N): #各ノードをスタート地点にする全探索
  routelist = dijkstra(eachstart, N, Graph)[1] #経路復元リストを得る
  for i, prev in enumerate(routelist):
    #prev->iというルートだと分かるので、それをContained_Edgeに入れる
    if prev+1: #prev=-1の場合は実行されない（スタート地点なので無視）
      Contained_Edge.add((i,prev))
      Contained_Edge.add((prev,i))

#全ての辺の集合
All_Edges = {(s-1,g-1) for s, g, d in SGDs}

#print(All_Edges)
#print(Contained_Edge)
#print(All_Edges - Contained_Edge)
print(len(All_Edges - Contained_Edge))

Submission status: Accepted

Solution code:
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]for i in range(N)] 
        self.next = [[ j for j in range(N)]for i in range(N)]  
        self.e = {}
        for i in range(N):
            self.e[i] = []

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

    def printPath(self,start,goal):
        cur = start
        l = []
        while cur != goal:
            t = self.next[cur][goal]
            self.e[cur].append(t)
            #self.e[t].append(cur)
            cur = t
        return l

    def dumpPath(self):
        for i in range(self.N):
            for j in range(self.N):
                if i != j:
                    self.printPath(i,j)

    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    if self.d[i][j] > self.d[i][k] + self.d[k][j]:
                        self.d[i][j] = self.d[i][k] + self.d[k][j]
                        self.next[i][j] = self.next[i][k]


        self.dumpPath() 
        for i in range(self.N):
            self.d[i][i] = 0
        return self.e
        return self.d


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

l = W.WarshallFloyd_search()
ans = M*2
for i in range(N):
    ans -= len(set(l[i]))
print(ans//2)

Submission status: Accepted

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

l=[list(map(int,input().split())) for i in range(M)]
inf=10**20
a=[[inf]*N for i in range(N)]
e=[[0]*N for i in range(N)]
for i,j,k in l:
    a[i-1][j-1]=k
    a[j-1][i-1]=k
    e[i-1][j-1]=1
    e[j-1][i-1]=1

ans=0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if a[i][j]>a[i][k]+a[k][j]:
                if e[i][j]==1:
                    ans+=1
                    e[i][j]=e[j][i]=0
                a[i][j]=a[i][k]+a[k][j]

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
edge=[list(map(int,input().split())) for i in range(M)]
inf=10**20
c=[[inf]*N for i in range(N)]
e=[[0]*N for i in range(N)]
for i,j,w in edge:
    c[i-1][j-1]=w
    c[j-1][i-1]=w
    e[i-1][j-1]=1
    e[j-1][i-1]=1
for i in range(N):
    c[i][i]=0
ans=0
def wf(c,N):
    global ans
    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]:
                    if e[i][j]==1:
                        ans+=1
                        e[i][j]=e[j][i]=0
                    c[i][j]=c[i][k]+c[k][j]
wf(c,N)
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
R=[]
G=[[] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    G[a].append((b,c))
    G[b].append((a,c))
    R.append((a,b,c))
Q=[[0]*N for i in range(N)]
INF=10**9
for i in range(N):
    stack=[]
    g=[INF for i in range(N)]
    g[i]=0
    n=1
    for b,c in G[i]:
        heapq.heappush(stack,(g[i]+c,i,b))
    used=[[0]*N for i in range(N)]
    while(stack):
        if n==N:
            break
        c,a,b=heapq.heappop(stack)
        g[b]=min(g[b],c)

        used[a][b]=1
        used[b][a]=1
        for j in G[b]:
            if used[b][j[0]] or g[j[0]]!=INF:
                continue
            if g[j[0]]<=g[b]+j[1]:
                continue
            heapq.heappush(stack,(g[b]+j[1],b,j[0]))
    for j in range(i+1,N):
        Q[i][j]=g[j]
ans=0
for a,b,c in R:
    if b<a:
        a,b=b,a
    if Q[a][b]<c:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
R=[]
G=[[] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    G[a].append((b,c))
    G[b].append((a,c))
    R.append((a,b,c))
Q=[[0]*N for i in range(N)]
INF=10**9
for i in range(N):
    stack=[]
    g=[INF for i in range(N)]
    g[i]=0
    n=1
    for b,c in G[i]:
        heapq.heappush(stack,(g[i]+c,i,b))
    used=[[0]*N for i in range(N)]
    while(stack):
        if n==N:
            break
        c,a,b=heapq.heappop(stack)
        g[b]=min(g[b],c)
        used[a][b]=1
        used[b][a]=1
        for j in G[b]:
            if used[b][j[0]] or g[j[0]]!=INF:
                continue
            heapq.heappush(stack,(g[b]+j[1],b,j[0]))
    for j in range(i+1,N):
        Q[i][j]=g[j]
ans=0
for a,b,c in R:
    if b<a:
        a,b=b,a
    if Q[a][b]<c:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8

N,M=map(int,raw_input().split())
D=[[1145141919]*101 for _ in range(101)]
R=[[1145141919]*101 for _ in range(101)]

A=set()
for i in range(M):
    a,b,c=map(int,raw_input().split())
    D[a][b]=c;D[b][a]=c
    R[a][b]=c;R[b][a]=c
    A.add((min(a,b),max(a,b)))

for i in range(1,N+1):D[i][i]=0


for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if D[i][j]>D[i][k]+D[k][j]:
                D[i][j]=D[i][k]+D[k][j]    
ans=0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if R[i][j]==1145141919:continue
        if D[i][j]!=R[i][j]:ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

class dijkstra(object):
    def __init__(self, start, n, E, INF=1e10):
        self.INF = INF
        self.start = start
        self.n = n
        self.V = [0 for _ in range(n + 1)]
        self.E = E
        self.d = [INF for _ in range(n + 1)]
        self.d[start] = 0

    def run(self):
        Q = [[i, self.d[i]] for i in range(1, self.n + 1)]

        while(len(Q) > 0):
            Q.sort(key=lambda x: x[1], reverse=True)
            u = Q.pop()[0]
            for v, l in self.E[u].items():
                if self.d[v] > self.d[u] + l[0]:
                    self.d[v] = self.d[u] + l[0]
                    self.V[v] = u
            Q = [[x[0], self.d[x[0]]] for x in Q]

    def count_path(self):
        def find_path(i, Qv):
            Qv[i] += 1
            if i != self.start:
                self.E[i][self.V[i]][-1] += 1
                self.E[self.V[i]][i][-1] += 1
                Qv = find_path(self.V[i], Qv)
            return Qv

        Qv = [0 for _ in range(self.n + 1)]
        for i in range(1, self.n + 1):
            if i == self.start or Qv[i] > 0:
                continue
            Qv = find_path(i, Qv)

        return self.E

n, m = map(int, input().split())
E_list = [list(map(int, input().split())) for _ in range(m)]
E = defaultdict(dict)
for j in range(m):
    a, b, c = E_list[j]
    E[a][b] = [c, 0]
    E[b][a] = [c, 0]
for i in range(1, n + 1):
    D = dijkstra(i, n, E)
    D.run()
    E = D.count_path()
ans = 0
for v in E.values():
    for v2 in v.values():
        if v2[-1] == 0:
            ans += 1
print(ans // 2)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d=[[float('inf') for i in range(n)] for i in range(n)]
r=[list(map(int,input().split())) for i in range(m)]

from scipy.sparse.csgraph import floyd_warshall

for u,v,c in r:
    u,v=u-1,v-1
    d[u][v]=d[v][u]=c

d=floyd_warshall(d).tolist()

cnt=0
for u,v,c in r:
    u,v=u-1,v-1
    if d[u][v]!=c:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d=[[float('inf') for i in range(n)] for i in range(n)]
r=[list(map(int,input().split())) for i in range(m)]

def wf(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


for u,v,c in r:
    u,v=u-1,v-1
    d[u][v]=d[v][u]=c

wf(d)

cnt=0
for u,v,c in r:
    u,v=u-1,v-1
    if d[u][v]!=c:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
e_list = [[] for i in range(N)]
e_list2 = []
for i in range(M):
    a,b,d = list(map(int,input().split()))
    a=a-1
    b=b-1
    e_list[a].append([b,d])
    e_list[b].append([a,d])
    e_list2.append([a,b,d])

dist_list = []
import heapq
for i in range(N):
    vi = i
    min_d_list = [10**27 for i in range(N)]
    min_d_list[vi] = 0
    prev_list = [-1 for i in range(N)]
    q = []
    for i in range(N):
        heapq.heappush(q,[min_d_list[i],i])

    while len(q)>0:
        d,v = heapq.heappop(q)
        for e in e_list[v]:
            v1,d1=e
            if min_d_list[v1]>d+d1:
                min_d_list[v1]=d+d1
                prev_list[v1]=v
                heapq.heappush(q,[d+d1,v1])
    dist_list.append(min_d_list)
count=len(e_list2)
for e in e_list2:
    for i in range(N):
        if dist_list[i][e[0]]+e[2]==dist_list[i][e[1]]:
            count-=1
            break

print(count)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000


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

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

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

min_Graph = copy.deepcopy(Graph)
used = [[0 for i in range(N)] for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            min_Graph[i][j] = min(min_Graph[i][j],min_Graph[i][k]+min_Graph[k][j])

ans = 0
for i in range(M):
    a,b,c = routes[i]
    if min_Graph[a][b] == c:
        pass
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
N,M=map(int,input().split())
inf=10**9

class Node():
	def __init__(self, ix):
		self.ix = ix # ノード番号
		self.done = False # 確定ノードかどうか
		self.pay = {} # 頂点番号:コストの一覧を容れる辞書
		self.paid = -1 # ここに到達するための最小コスト(未定義なら-1)
		self.prev = -1 # 最小コストを与える親ノード(未定義なら-1)
	def __str__(self):
		# デバッグ用
		return '{} <- [{}] <- {}, done:{}, pay:{}'.format(self.ix, self.paid, self.prev, self.done, self.pay)

# ノードのリストを生成
nodes = []
for i in range(N):
	nodes.append(Node(i))

# エッジのリストを生成(これはこの問題用)
# edges = np.zeros((N,N), dtype=np.uint8) #NumPy
edges = []
for _ in range(N):
	edges.append([0]*N)

# エッジ情報を取得
# 全エッジを格納
# 注意: 標準入力は1-indexedだがここでは0-indexedに直す
for _ in range(M):
	a,b,c = map(int,input().split())
	nodes[a-1].pay[b-1] = c
	nodes[b-1].pay[a-1] = c
	edges[a-1][b-1] = 1
	edges[b-1][a-1] = 1
		
		
# 出発ノードを0からN-1まで変化させる
for i in range(N):
	nodes[i].prev = i # 出発点の最良親を自分自身に
	nodes[i].paid = 0 # 出発点のコストは0
	nodes[i].done = True # 出発点は確定済み
	n_done = 1 # 確定ノード数を1に
	while n_done < N: # 全部確定するまで続行
		to_conf_ix = -1 # 次に確定されるべきノード番号
		to_conf_paid = 10**9 # そのコスト
		for node in nodes:
			# 確定ノードすべてに対して操作を行う
			if node.done:
				# 接続先を全列挙
				for child in list(node.pay.keys()):
					# その接続先が未確場合のみ進む定なら処理続行
					if not nodes[child].done:
						# その接続先の仮の最小コストと仮の親を更新
						# まだ確定済みにはしない
						newcost = node.paid + node.pay[child]
						# 更新するための条件
						flag = (nodes[child].paid < 0) or (newcost < nodes[child].paid)
						# 条件をみたせば接続先の情報を更新
						# また次に確定されるノード候補の情報も更新
						if flag:
							nodes[child].paid = newcost
							nodes[child].prev = node.ix
						if newcost < to_conf_paid:
							to_conf_paid = newcost
							to_conf_ix = child
		# 操作が完了したら現段階の候補ノードを確定させる
		nodes[to_conf_ix].done = True
		# 確定ノード数を1増やす
		n_done += 1
		
	# 各ノードについてそれを親と連結するパスをedgeから削除
	for j in range(N):
		k = nodes[j].prev
		edges[j][k], edges[k][j] = 0, 0

	# 全ノードのpaid,prevをリセット
	for j in range(N):
		nodes[j].paid, nodes[j].prev = -1, -1
		nodes[j].done = False

# 最後にedgesに残っているエッジの本数を出力
# print(int(np.sum(edges)//2)) # NumPy
ans = 0
for i in range(N):
	ans += sum(edges[i])
print(ans//2)

Submission status: Accepted

Solution code:
#import numpy as np
N,M=map(int,input().split())
inf=10**9

class Node():
	def __init__(self, ix):
		self.ix = ix # ノード番号
		self.done = False # 確定ノードかどうか
		self.pay = {} # 頂点番号:コストの一覧を容れる辞書
		self.paid = -1 # ここに到達するための最小コスト(未定義なら-1)
		self.prev = -1 # 最小コストを与える親ノード(未定義なら-1)
	def __str__(self):
		# デバッグ用
		return '{} <- [{}] <- {}, done:{}, pay:{}'.format(self.ix, self.paid, self.prev, self.done, self.pay)

# ノードのリストを生成
nodes = []
for i in range(N):
	nodes.append(Node(i))

# エッジのリストを生成(これはこの問題用)
# edges = np.zeros((N,N), dtype=np.uint8)
edges = []
for _ in range(N):
	edges.append([0]*N)

# エッジ情報を取得
# 全エッジを格納
# 注意: 標準入力は1-indexedだがここでは0-indexedに直す
for _ in range(M):
	a,b,c = map(int,input().split())
	nodes[a-1].pay[b-1] = c
	nodes[b-1].pay[a-1] = c
	edges[a-1][b-1] = 1
	edges[b-1][a-1] = 1
		
		
# 出発ノードを0からN-1まで変化させる
for i in range(N):
	##### DEBUG
	# print('start node: {}'.format(i))
	nodes[i].prev = i # 出発点の最良親を自分自身に
	nodes[i].paid = 0 # 出発点のコストは0
	nodes[i].done = True # 出発点は確定済み
	n_done = 1 # 確定ノード数を1に
	while n_done < N: # 全部確定するまで続行
		to_conf_ix = -1 # 次に確定されるべきノード番号
		to_conf_paid = 10**9 # そのコスト
		for node in nodes:
			# 確定ノードすべてに対して操作を行う
			if node.done:
				##### DEBUG
				# print('confirmed parent: {}'.format(node.ix))
				# 接続先を全列挙
				for child in list(node.pay.keys()):
					# その接続先が未確場合のみ進む定なら処理続行
					if not nodes[child].done:
						# その接続先の仮の最小コストと仮の親を更新
						# まだ確定済みにはしない
						newcost = node.paid + node.pay[child]
						# 更新するための条件
						flag = (nodes[child].paid < 0) or (newcost < nodes[child].paid)
						##### DEBUG
						# print('p{} -> c{}, prevcost={}, newcost={}'.format(node.ix, child, nodes[child].paid, newcost))
						# 条件をみたせば接続先の情報を更新
						# また次に確定されるノード候補の情報も更新
						if flag:
							nodes[child].paid = newcost
							nodes[child].prev = node.ix
						if newcost < to_conf_paid:
							to_conf_paid = newcost
							to_conf_ix = child
						##### DEBUG
						# print('to_conf: ix:{}, cost:{}'.format(to_conf_ix, to_conf_paid))
		# 操作が完了したら現段階の候補ノードを確定させる
		nodes[to_conf_ix].done = True
		# 確定ノード数を1増やす
		n_done += 1
		##### DEBUG
		# print('--- n_done: {} ---'.format(n_done))
		# for j in range(N):
		# 	print(nodes[j])
		# print('------------------')
		
	# 各ノードについてそれを親と連結するパスをedgeから削除
	for j in range(N):
		k = nodes[j].prev
		edges[j][k], edges[k][j] = 0, 0

	# 全ノードのpaid,prevをリセット
	for j in range(N):
		nodes[j].paid, nodes[j].prev = -1, -1
		nodes[j].done = False

# 最後にedgesに残っているエッジの本数を出力
# print(int(np.sum(edges)//2)) # NumPy
ans = 0
for i in range(N):
	ans += sum(edges[i])
print(ans//2)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
INF = 1000*n+1
#edges = [[] for _ in  range(m)]
edge = [[INF for _ in range(n)] for _ in range(n)]
d = [[INF for _ in range(n)] for _ in range(n)]

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

def dijkstra(i):
    #d = [INF for _ in range(n)] 
    d[i][i] = 0
    used = [False] * n

    while True:
        v = -1
        for j in range(n):
            if used[j] == False and (v == -1 or d[i][j] < d[i][v]):
                v = j
        if v == -1:
            break
        used[v] = True
        for k in range(n):

            d[i][k] = min(d[i][k], d[i][v] + edge[v][k])
            d[k][i] = d[i][k]


for i in range(n):
    dijkstra(i)
#print(edge)
#print(d)
ans = 0
for a, b, c in abc:
    if d[a-1][b-1] < c:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
from collections import defaultdict
B=[tuple(map(int,input().split())) for i in range(M)]
dist=defaultdict(lambda : float('inf'))
for i,x in enumerate(B):
    a,b,c=x[0]-1,x[1]-1,x[2]
    dist[(a,b)]=c
    dist[(b,a)]=c
for i in range(N):
    dist[(i,i)]=0
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[(j,k)])
            dist[(j,i)]=dist[(i,j)]
cnt=0
for x in B:
    a,b,c=x[0]-1,x[1]-1,x[2]
    if dist[(a,b)]!=c:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path

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

edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = np.zeros((N,N)) # 0-indexed
for a,b,c in edge:
  graph[a-1,b-1] = c

dist = shortest_path(graph,directed=False).astype(int)

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

Submission status: Accepted

Solution code:
import copy

def warshall_floyd(V, E):
    INF = 10 ** 9
    d = [[[INF, 0] for j in range(V + 1)] for i in range(V + 1)]
    for i, j, c in E:
        d[i][j] = [c, 0]
        d[j][i] = [c, 0]
    for k in range(1, V + 1):
        for i in range(1, V):
            for j in range(i, V + 1):
                dk = d[i][k][0] + d[k][j][0]
                if d[i][j][0] > dk:
                    d[i][j] = [dk, k]
                    d[j][i] = [dk, k]
    return d

def find_path(i, j, d, E):
    k = d[i][j][1]
    if k == 0:
        E[i][j] += 1
        E[j][i] += 1
        return E
    E = find_path(i, k, d, E)
    E = find_path(k, j, d, E)
    return E

n, m = map(int, input().split())
E = [[None for j in range(n + 1)] for i in range(n + 1)]
E_list = []
for i in range(m):
    a, b, c = map(int, input().split())
    E_list.append([a, b, c])
    E[a][b] = 0
    E[b][a] = 0
d = warshall_floyd(n, E_list)
ans = 0
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        E = find_path(i, j, d, E)
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if E[i][j] == 0:
            ans += 1
print(ans)