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:
N, M = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]
wf = [[[2000 for _ in range(N + 10)] for _ in range(N + 10)] for _ in range(N + 10)]
for i in range(N):
    for j in range(N):
        wf[i][j][j] = 0
for item in edge:
    a, b, c = item
    wf[0][a - 1][b - 1] = c
    wf[0][b - 1][a - 1] = c

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

ans = 0
for item in edge:
    a, b, c = item
    if c > wf[N][a - 1][b - 1]:
        ans += 1

print(ans)

Submission status: Accepted

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

for a,b,c in l:
  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]=0 if i==j else min(d[i][j],d[i][k]+d[k][j])

ans=m
for a,b,c in l:
  f=False
  for s in range(n):
    if d[s][a-1]+c==d[s][b-1]:
      f=True
  if f:ans-=1

print(ans)

Submission status: Accepted

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

for a,b,c in l:
  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]=0 if i==j else min(d[i][j],d[i][k]+d[k][j])

ans=m
for i,(a,b,c) in enumerate(l):
  f=False
  for s in range(n):
    if d[s][a-1]+c==d[s][b-1]:
      f=True
  if f:ans-=1

print(ans)

Submission status: Accepted

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

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

for a,b,c in l:
  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):
      if i==j:d[i][j]=0
      d[i][j]=min(d[i][j],d[i][k]+d[k][j])

ans=m
for i,(a,b,c) in enumerate(l):
  f=False
  for s in range(n):
    if d[s][a-1]+c==d[s][b-1]:
      f=True
  if f:ans-=1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
INF = 10 ** 20
edgeList = []
dist = [[INF] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    dist[a][b] = dist[b][a] = c
    edgeList.append((a, b, 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])

print(sum([dist[a][b] < c for a, b, c in edgeList]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

G = [[float('inf')] * N for i in range(N)]
edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = c
    G[b-1][a-1] = c
    edges[i] = (a-1, b-1, c)

# ワーシャルフロイドで全頂点の最短距離
for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j:
                G[i][j] = 0
            else:
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

ans = 0
for a, b, c in edges:
    # 最短距離ではない辺の数を数える
    if G[a][b] < c:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as comb
from collections import deque as dq

def inpl(): return list(map(int, input().split()))


def dijkstra(a):
    node = dq()
    node.append(a)
    ncost = [1<<20 for _ in range(N+1)]
    first = a
    ncost[a] = 0
    path = {}
    while len(node) != N:
        for nb in edge[first]:
            if nb in node:
                continue
            if ncost[nb] > ncost[first] + cost[(first, nb)]:
                # print(nb, ncost[nb])
                path[nb] = first
                ncost[nb] = ncost[first] + cost[(first, nb)]
                # print(nb, ncost[nb])

        nf = 0
        # print(path)
        for t in range(N+1):
            if t in node:
                continue
            # print(nf, t)
            if ncost[nf] > ncost[t]:
                nf = t
        node.append(nf)
        first = nf
        # print(node)
    # print(path)
    # print(ncost)
    ret = set()
    for k, v in path.items():
        ret.add((k, v))
        ret.add((v, k))
    return ret


N, M = inpl()
cost = {}
edge = [dq() for _ in range(N+1)]
for _ in range(M):
    a, b, c = inpl()
    cost[(a, b)] = c
    cost[(b, a)] = c
    edge[a].append(b)
    edge[b].append(a)

ans = set()
for a in range(1, N+1):
    # print(a, b, "check")
    # print(dijkstra(a, b))
    ans = ans | dijkstra(a)
# print(ans)
print(M-len(ans)//2)

Submission status: Accepted

Solution code:
N, M = (list)(map(int, input().split()))
a = []
b = []
c = []

inf = 10**4
for _ in range(M):
    tmp = (list)(map(int, input().split()))
    a.append(tmp[0]-1)
    b.append(tmp[1]-1)
    c.append(tmp[2])

mat = [[inf] * N for _ in range(N)]
for i in range(N):
    mat[i][i] = 0

edges = [False] * M

for i in range(M):
    mat[a[i]][b[i]] = c[i]
    mat[b[i]][a[i]] = c[i]

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

ans = M
for i in range(M):
    s = False
    for j in range(N):
        if mat[j][a[i]] + c[i] == mat[j][b[i]]:
            s = True
    if s:
        ans -= 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
COSTLIST=[list(map(int,input().split())) for i in range(M)]#aからbへのcostがx

#グラフの最短距離を全て求める（ワーシャル–フロイド法）

Distance=[[float("inf") for i in range(N+1)] for j in range(N+1)]

for i,j,t in COSTLIST:
    Distance[i][j]=Distance[j][i]=t#分かっている距離を書き込んでおく.

for k in range(1,N+1):#k個までの町を使ってのDisが知れているときに
    for i in range(1,N+1):#町iと
        for j in range(i,N+1):#町jとの最短距離は、
            length=Distance[i][k]+Distance[j][k]
            if Distance[i][j]>length:
                Distance[i][j]=Distance[j][i]=length
        

ANS=0
for i ,j,t in COSTLIST:
    if Distance[i][j]!=t:
        ANS+=1

print(ANS)

Submission status: Accepted

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

d = [[INF for _ in range(N)] for _ in range(N)]
abc = []

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

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

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

ans = M
for a, b, c in abc:
  shortest = False
  for j in range(N):
    if d[j][a]+c == d[j][b]:
      shortest = True
  if shortest:
    ans -= 1
print(ans)

Submission status: Accepted

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

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

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

need = 0
for a, b, c in Edge:
    for s in range(N):
        if G[s][a] + c == G[s][b]:
            need += 1
            break

print(M - need)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
N, M = map(int, input().split())

inf = float("inf")
graph = [[inf for _ in range(N)] for _ in range(N)]
edge = []
for i in range(M):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
    edge.append([a-1, b-1])
w_graph = floyd_warshall(graph)

count = 0
for e in edge:
    e_s = e[0]
    e_e = e[1]
    used = False
    for i in range(N):
        if w_graph[i][e_e] == w_graph[i][e_s] + graph[e_e][e_s]:
            used = True
    if not used:
        count += 1

print(count)

Submission status: Accepted

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

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

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

ans = 0
for i in range(M):
    a,b,c = B[i]
    for j in range(N):
        if A[j][b] == A[j][a] + c:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(n,w,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") for i in range(n)] for i in range(n)]
edge = [[float("inf") for i in range(n)] for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
S = []
for i in range(w):
    x,y,z = map(int,input().split())
    if x > y:
        x, y = y, x
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z 
    edge[x][y]=z
    edge[y][x]=z
    S.append(str(x)+","+str(y))
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
trash = warshall_floyd(n,w,d)
L=[]
for s in range(n):
    for t in range(n):
        for v in range(n):
            if d[s][t] + edge[t][v] == d[s][v] and t < v:
                L.append(str(t)+","+str(v))
ans = 0
for x in S:
        if x not in L:
            ans += 1
print(ans)

Submission status: Accepted

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

n, m = map(int, input().split())
d = []
for i in range(m):#h:高さ
    d.append([int(m) for m in input().split()])

dist = d
#dist.append([i, j, c[i][j]])

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]
# (src, dst, weight)
inputs = dist

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)
ans = 0
for i in range(m):
    d = Dijkstra(g, dist[i][1])
    sp = format(d.shortest_distance(dist[i][0]))
    if int(sp) != dist[i][2]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
V, E = [int(_) for _ in input().split()]
G = {}
for i in range(V):
    G[i] = {}
    G[i][i] = 0

for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  # 0を始点とする場合
    t -= 1  # 0を始点とする場合
    G[s][t] = c
    G[t][s] = c

INF = 10**10

edges_used = set()
for i in range(V):
    D = [INF] * V
    D[i] = 0  # iを始点とする場合
    used = [False] * V
    used[i] = True
    prev = {}
    while True:
        for j in G[i].keys():
            if D[i] + G[i][j] < D[j]:
                D[j] = D[i] + G[i][j]
                prev[j] = i
        v = -1
        for j in range(V):
            if not used[j] and (v == -1 or D[j] < D[v]):
                v = j
        if v == -1:
            break
        else:
            used[v] = True
            i = v
    for key, value in prev.items():
        if key > value:
            key, value = value, key
        edges_used.add((key + 1, value + 1))

print(E - len(edges_used))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A, B, C = [], [], []
for i in range(M):
    a, b, c = map(int, input().split())
    A.append(a - 1)
    B.append(b - 1)
    C.append(c)

d = [[float('inf') if i != j else 0 for i in range(N)] for j in range(N)]

for i in range(M):
    d[A[i]][B[i]] = min(d[A[i]][B[i]], C[i])
    d[B[i]][A[i]] = min(d[B[i]][A[i]], C[i])

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 = M
for i in range(M):
    flag = False
    for j in range(N):
        if d[j][A[i]] + C[i] == d[j][B[i]]:
            flag = True
    if flag:
        ans -= 1

print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall 

n,m = map(int, input().split())
s = [[float('inf')]*n for i in range(n)]
d = [list(map(int, input().split())) for i in range(m)]
ans = 0

for a,b,c in d:
    s[a-1][b-1] = c
    s[b-1][a-1] = c

cost = floyd_warshall(s)

for a,b,c in d:
    #print(cost[a-1][b-1], c)
    #例えば1(a)→2(b)に行くとき他の経路を使った方がコストが低い場合は1→2は絶対使われず、他の経路が使われる
    if cost[a-1][b-1] != c:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall 

n,m = map(int, input().split())
s = [[float('inf')]*n for i in range(n)]
d = [list(map(int, input().split())) for i in range(m)]
ans = 0

for a,b,c in d:
    s[a-1][b-1] = c
    s[b-1][a-1] = c

cost = floyd_warshall(s)

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

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
s=[[float('inf')]*n for i in range(n)]
d=[list(map(int, input().split())) for i in range(m)]
for a,b,c in d:
    s[a-1][b-1]=c
    s[b-1][a-1]=c
from scipy.sparse.csgraph import floyd_warshall 
cost=floyd_warshall(s)
ans=0
for a,b,c in d:
    if cost[a-1][b-1]!=c:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
INF = float('inf')
d = [[INF for i in range(N)] for _ in range(N)]
edge = []
for i in range(N):
    d[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    edge.append([a-1,b-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][b]!=c:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq
import math

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = {}
    for i in range(N):
        graph[i] = {}
        for j in range(N):
            graph[i][j] = 0
    for edge in edges:
        a, b, c = edge
        graph[a][b] = c
        graph[b][a] = c
    return graph

def Dijkstra(graph, start):
    N = len(graph)
    d = {}
    prev = {}
    for i in range(N):
        prev[i] = None
        if i == start:
            d[i] = 0
        else:
            d[i] = float('inf')
    Q = []
    heapq.heappush(Q, (0, start))
    while Q:
        d_u, u = heapq.heappop(Q)
        if d[u] < d_u:#ダブりを回避
            continue
        for i in range(N):
            if graph[u][i]:
                temp = d_u + graph[u][i]
                if d[i] > temp:
                    d[i] = temp
                    prev[i] = u
                    heapq.heappush(Q, (d[i], i))
    return (d, prev)

def saitan(start, goal, d, prev):
    temp = goal
    res = [goal]
    while True:
        res.append(prev[temp])
        if prev[temp] == start:
            break
        else:
            temp = prev[temp]
    return res

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

graph = make_Graph(N, edges)

res = []
for i in range(N):
    d, prev = Dijkstra(graph, i)
    for j in range(N):
        if i != j:
            sait = saitan(i, j, d, prev)
            for k in range(len(sait) - 1):
                res.append(  (min(sait[k], sait[k + 1]) , max(sait[k], sait[k + 1]) ) )

res = set(res)
print(M - len(res))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from copy import deepcopy
inf = 10**5
n,m = map(int, input().split())

edge = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    edge[i][i] = 0
for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge[a][b] = c
    edge[b][a] = c
edge_tmp = deepcopy(edge)

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

res = 0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if edge[i][j]!=edge_tmp[i][j] and edge_tmp[i][j]<inf:
            res += 1
print(res//2)

Submission status: Accepted

Solution code:
ans = 0
n,m = map(int,input().split())
dis = [[float('inf') for i in range(n)] for j in range(n)] #各点距離を最初∞に設定
abt = []
for i in range(m):
    abt.append(list(map(int,input().split()))) #入力
for a,b,t in abt:
    dis[a-1][b-1] = t #頂点aからbへの距離がt
    dis[b-1][a-1] = t # 逆も同様
for i in range(n):
    for j in range(n):
        for k in range(n):
            dis[k][j] = min(dis[k][j], dis[k][i] + dis[i][j])
for a,b,t in abt:
    if t > dis[a-1][b-1]:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
cnt=0
n,m=map(int,input().split())
dis=[[float('inf') for i in range(n)]for j in range(n)]
tmp=[]
for i in range(m):
    tmp.append(list(map(int,input().split())))
for a,b,t in tmp:
    dis[a-1][b-1]=t
    dis[b-1][a-1]=t
for k in range(n):
    for i in range(n):
        for j in range(n):
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])
for a,b,t in tmp:
    if t>dis[a-1][b-1]:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
Islands=[[10**9]*N for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1][b-1]=c
  Islands[b-1][a-1]=c
  Edge.append([a-1,b-1,c])
for k in range(N):
  for i in range(N):
    for j in range(N):
      Islands[i][j]=min(Islands[i][j],Islands[i][k]+Islands[k][j])

ans=0
for a,b,c in Edge:
  if Islands[a][b]!=c:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
d = {}
p = {}
INF = 9999999
for i in range(1, N + 1):
  for j in range(1, N + 1):
    if i == j:
      continue
    d[i, j] = INF
    p[i, j] = []
e = set([])
for i in range(M):
  a, b, c = map(int, input().split())
  e.add((a, b))
  d[a, b] = c
  d[b, a] = c
  p[a, b] = [a, b]
  p[b, a] = [b, a]
for k in range(1, N + 1):
  for i in range(1, N + 1):
    if i == k:
      continue
    for j in range(1, N + 1):
      if i == j or j == k:
        continue
      if d[i, j] > d[i, k] + d[k, j]:
        d[i, j] = d[i, k] + d[k, j]
        p[i, j] = p[i, k] + p[k, j][1:]
for i in range(1, N + 1):
  for j in range(1, N + 1):
    if i == j:
      continue
    q = p[i, j]
    for k in range(len(q) - 1):
      r = q[k], q[k + 1]
      s = q[k + 1], q[k]
      if r in e:
        e.remove(r)
      if s in e:
        e.remove(s)
print(len(e))

Submission status: Accepted

Solution code:
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d



V, E=map(int,input().strip().split(' '))
inf=10**9
cost=[[inf]*V for i in range(V)]
edge=[]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
    edge.append([fr-1,to-1])
    
d=[]
for i in range(V):
    d.append(dijkstra(i))

cand=E
for i in range(E):
    fl=False
    for s in range(V):
        if d[s][edge[i][0]]+cost[edge[i][0]][edge[i][1]]==d[s][edge[i][1]]:
            cand-=1
            fl=True
            break

print(cand)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
Islands=[[10**9]*N for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1][b-1]=c
  Islands[b-1][a-1]=c
  Edge.append([a-1,b-1,c])
for k in range(N):
  for i in range(N):
    for j in range(N):
      Islands[i][j]=min(Islands[i][j],Islands[i][k]+Islands[k][j])

ans=0
for a,b,c in Edge:
  if Islands[a][b]!=c:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


"""
https://beta.atcoder.jp/contests/abc051/tasks/abc51_d
"""

import sys
import math
import copy
from inspect import currentframe

def debug_print(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args), file=sys.stderr)

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

d = [[0 if i == j else float('inf') for i in range(N)] for j in range(N)]
edges = []

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

graph = copy.deepcopy(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])
    
#debug_print(d)
unused_edge = 0
for edge in edges:
    if edge[2] > d[edge[0] - 1][edge[1] - 1]:
        unused_edge += 1
print(unused_edge)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
Islands=[[10**9]*N for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1][b-1]=c
  Islands[b-1][a-1]=c
  Edge.append([a-1,b-1,c])
for k in range(N):
  for i in range(N):
    for j in range(N):
      Islands[i][j]=min(Islands[i][j],Islands[i][k]+Islands[k][j])

ans=0
for a,b,c in Edge:
  if Islands[a][b]!=c:
    ans+=1
print(ans)

Submission status: Accepted

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

N,M=list(map(int,input().split()))
dist=np.array([[10**9 for _ in range(N)] for _ in range(N)])
for i in range(N):
    dist[i,i]=0

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

wsdist=np.array(ws(dist),dtype='int')
ans=-N
for i in range(N):
    for j in range(N):
        if wsdist[i][j]==dist[i][j]:
            ans+=1
print(M-ans//2)

Submission status: Accepted

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

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

for i in range(n):
    for j in range(n):
        if i!=j:
            d[i][j]=float('inf')
            e[i][j]=float('inf')

for i in range(m):
    d[abc[i][0]-1][abc[i][1]-1]=abc[i][2]
    d[abc[i][1]-1][abc[i][0]-1]=abc[i][2]
    e[abc[i][0]-1][abc[i][1]-1]=abc[i][2]
    e[abc[i][1]-1][abc[i][0]-1]=abc[i][2]

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

f = 0

for i in range(n):
    for j in range(n):
        if d[i][j]!=e[i][j] and e[i][j]!=float('inf'):
            f+=1

print(f//2)

Submission status: Accepted

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


d = [[0]*n for i in range(n)]
e = [[[-1]for j in range(n)] for i in range(n)]


for i in range(n):
    for j in range(n):
        if i!=j:
            d[i][j]=float('inf')


for i in range(m):
    d[abc[i][0]-1][abc[i][1]-1]=abc[i][2]
    d[abc[i][1]-1][abc[i][0]-1]=abc[i][2]
    e[abc[i][0]-1][abc[i][1]-1]=[i]
    e[abc[i][1]-1][abc[i][0]-1]=[i]


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


f = []

for i in range(n):
    for j in range(n):
        for k in range(len(e[i][j])):
            if e[i][j][k] not in f:
                f.append(e[i][j][k])

print(m-len(f)+1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
N,M=map(int,input().split())

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

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

dist = dijkstra(graph)

count = 0

for i in range(N):
    for j in range(N):
        if graph[i][j] != inf:
            if graph[i][j] != dist[i][j]:
                count += 1

print(count//2)

Submission status: Accepted

Solution code:
import heapq

n, m = [int(i) for i in input().split()]
inf = 10**10
path = [[0] * n for _ in range(n)]
Q = [[inf] * n for _ in range(n)]
ans = 0
pathnum = []

for i in range(m):
    a, b, c = map(lambda x: int(x)-1 ,input().split())    
    path[a][b] = path[b][a] = c+1
    pathnum.append((a,b))

for i in range(n):
    decided = [False for _ in range(n)]
    H = []
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    for _ in range(n):
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                break
        for j in range(n):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

for i in pathnum:
    if Q[i[0]][i[1]] == inf:
        continue
    elif Q[i[0]][i[1]] != path[i[0]][i[1]]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = [int(i) for i in input().split()]
inf = 10**10
path = [[0] * n for _ in range(n)]
Q = [[inf] * n for _ in range(n)]
ans = 0
pathnum = [0 for _ in range(m)]

for i in range(m):
    a, b, c = map(lambda x: int(x)-1 ,input().split())    
    path[a][b] = path[b][a] = c+1
    pathnum[i] = (a,b)

for i in range(n):
    decided = [False for _ in range(n)]
    H = []
    ctr = 0
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    while ctr != n:
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                ctr += 1
                break
        for j in range(n):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

for i in pathnum:
    if Q[i[0]][i[1]] == inf:
        continue
    elif Q[i[0]][i[1]] != path[i[0]][i[1]]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = [int(i) for i in input().split()]
inf = 10**10
path = [[0] * n for _ in range(n)]
Q = [[inf] * n for _ in range(n)]
ans = 0
pathnum = []

for i in range(m):
    a, b, c = map(lambda x: int(x)-1 ,input().split())    
    path[a][b] = path[b][a] = c+1
    pathnum.append((a,b))

for i in range(n):
    decided = [False for _ in range(n)]
    H = []
    ctr = 0
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    while ctr != n:
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                ctr += 1
                break
        for j in range(n):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

for i in pathnum:
    if Q[i[0]][i[1]] == inf:
        continue
    elif Q[i[0]][i[1]] != path[i[0]][i[1]]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = [int(i) for i in input().split()]
inf = 10**10
path = [[0] * n for _ in range(n)]
Q = [[inf] * n for _ in range(n)]
ans = 0
pathnum = []

for i in range(m):
    a, b, c = map(lambda x: int(x)-1 ,input().split())    
    path[a][b] = path[b][a] = c+1
    pathnum.append((a,b))

for i in range(n):
    decided = [False for _ in range(n)]
    H = []
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    while False in decided:
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                break
        for j in range(n):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

for i in pathnum:
    if Q[i[0]][i[1]] == inf:
        continue
    elif Q[i[0]][i[1]] != path[i[0]][i[1]]:
        ans += 1
print(ans)