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=[int(i) for i in input().split()]
edges=[[2**60 for i in range(N)] for j in range(N)]
for i in range(M):
    a,b,c=[int(i) for i in input().split()]
    a-=1
    b-=1
    edges[a][b]=edges[b][a]=c

mini=[[edges[i][j] for i in range(N)] for j in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            mini[i][j]=min(mini[i][j],mini[i][k]+mini[k][j])
res=0
for r in range(N):
    for l in range(r):
        #print(l,".",r,"->",edges[l][r],mini[l][r])
        if edges[l][r] != 2**60 and mini[l][r]<edges[l][r]:
            res+=1
print(res)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall


n, m = map(int, input().split())
d = [[0 if i == j else float('inf') for i in range(n)]
     for j in range(n)]
g = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    g[a].append((b, c))
    g[b].append((a, c))

gf = floyd_warshall(csgraph=d)
# print(gf)

cnt = 0
for i in range(n):
    for j, cost in g[i]:
        used = False
        if i > j:
            continue
        for k in range(n):
            if gf[i][k] == cost + gf[k][j]:
                used = True
                break
        if used is False:
            cnt += 1
print(cnt)

Submission status: Accepted

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

A = []
B = []
C = []

inf = 1*10**7
max_n = 110
G = [[inf] * max_n for i in range(max_n)]
for i in range(N):
    G[i][i] = 0


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

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

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

# print(G)


print(ans)

Submission status: Accepted

Solution code:
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

N, M = map(int, input().split())
d = [[float('inf') for i in range(N)] for i in range(N)]
edges = []

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

warshall_floyd(d)

# 与えられた頂点間の辺の距離が求めた最短距離より大きければ
# その辺は使われない
cnt = 0
for edge in edges:
    if d[edge[0]][edge[1]] != edge[2]:
        cnt += 1

print(cnt)

Submission status: Accepted

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

INF = float('inf')

def sol():
    N, M = map(int, input().split())

    edges = []

    for _ in range(M):
        fr, to, cost = map(int, input().split())
        fr -= 1
        to -= 1
        edges.append((fr, to, cost))

    graph = [[INF] * N for _ in range(N)]
    for fr, to, cost in edges:
        graph[fr][to] = cost

    graph = csgraph_from_dense(graph, null_value=INF)

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

sol()

Submission status: Accepted

Solution code:
##SPEED TEST##

import heapq,sys
input=sys.stdin.readline
INF=float('inf')
heappush=heapq.heappush
heappop=heapq.heappop

n,m=map(int,input().split())
graph=[[] for _ in range(n)]
minway=[]
bridges=[]
ans=0
for _ in range(m):
    a,b,c=map(int,input().split())
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))
    bridges.append((a-1,b-1,c))

def dijkstra(graph,n,start):
    Q=[]
    distance=[]
    dappend=distance.append
    for i in range(n):
        dappend([INF,i])
    distance[start][0]=0
    for j in distance:
        heappush(Q,j)
    while Q!=[]:
        q=heappop(Q)
        for v,vl in graph[q[1]]:
            alt=vl+q[0]
            if alt<distance[v][0]:
                distance[v][0]=alt
                heappush(Q,[alt,v])
    return distance

for k in range(n):
    minway.append(dijkstra(graph,n,k))

for l in bridges:
    x,y,z=l[0],l[1],l[2]
    flag=True
    for p in range(n):
        if minway[x][p][0]+z==minway[y][p][0] or minway[y][p][0]+z==minway[x][p][0]:
            flag=False
            break
    if flag:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import heapq,sys
input=sys.stdin.readline
INF=float('inf')
heappush=heapq.heappush
heappop=heapq.heappop

n,m=map(int,input().split())
graph=[[] for _ in range(n)]
minway=[]
bridges=[]
ans=0
for _ in range(m):
    a,b,c=map(int,input().split())
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))
    bridges.append((a-1,b-1,c))

def dijkstra(graph,n,start):
    Q=[]
    distance=[]
    dappend=distance.append
    for i in range(n):
        dappend([INF,i])
    distance[start][0]=0
    for j in distance:
        heappush(Q,j)
    while Q!=[]:
        q=heappop(Q)
        for v,vl in graph[q[1]]:
            alt=vl+q[0]
            if alt<distance[v][0]:
                distance[v][0]=alt
                heappush(Q,[alt,v])
    return distance

for k in range(n):
    minway.append(dijkstra(graph,n,k))

for l in bridges:
    x,y,z=l[0],l[1],l[2]
    flag=True
    for p in range(n):
        if minway[x][p][0]+z==minway[y][p][0] or minway[y][p][0]+z==minway[x][p][0]:
            flag=False
            break
    if flag:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def solve(G):
    N = len(G)
    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])
    return G

def main():
    N, M = l_inpl()
    G = create_grid(N, N, INF)

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

    a, b, c = [], [], []
    for _ in range(M):
        ai, bi, ci = l_inpl()
        ai, bi = ai-1, bi-1
        a.append(ai)
        b.append(bi)
        c.append(ci)
        G[ai][bi] = ci
        G[bi][ai] = ci
    
    G = solve(G)

    ans = M
    for i in range(M):
        flag = False
        for j in range(N):
            # dist(j, a[i]) + edge(a[i], b[i]) == dist(j, b[i])のとき
            # j~b[i]の最短経路にedge(a[i], b[i])が含まれる
            if G[j][a[i]]+c[i] == G[j][b[i]]:
                flag = True
        if flag:
            ans -= 1
    
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def solve(G):
    N = len(G)
    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])
    return G

def main():
    N, M = l_inpl()
    G = create_grid(N, N, INF)

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

    a, b, c = [], [], []
    for _ in range(M):
        ai, bi, ci = l_inpl()
        ai, bi = ai-1, bi-1
        a.append(ai)
        b.append(bi)
        c.append(ci)
        G[ai][bi] = ci
        G[bi][ai] = ci
    
    G = solve(G)

    ans = M
    for i in range(M):
        flag = False
        for j in range(N):
            if G[j][a[i]]+c[i] == G[b[i]][j]:
                flag = True
        if flag:
            ans -= 1
    
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def WarshallFloyd(V: int, cost: "List[List[int]]"):
    """
    全ての頂点対の間の最短距離を求めます。
    ==============
    V: 頂点数
    cost: 隣接行列(辺が存在しない部分はINF)
    --------------
    cost: 最短距離の行列
    """
    INF = 1e18
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    INF = 1e18
    cost = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(M):
        cost[a[i] - 1][b[i] - 1] = c[i]
        cost[b[i] - 1][a[i] - 1] = c[i]
    for i in range(N):
        cost[i][i] = 0
    cost = WarshallFloyd(N, cost)
    # print(cost)
    counter = 0
    for i in range(M):
        flag = False
        for j in range(N):
            if cost[j][a[i]-1] + c[i] == cost[j][b[i]-1]:
                flag = True
        if not flag:
            counter += 1
    print(counter)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = [ int(v) for v in input().split() ]
shortest_distance = [ [ 10**8 for i in range(n) ] for j in range(n) ]
distance_path = [ [ [] for i in range(n) ] for j in range(n) ]

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


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


path_used = [ False for i in range(m) ]
for i in distance_path:
    for j in i:
        for k in j:
            path_used[k] = True
print(path_used.count(False))

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

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

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

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

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


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

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

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

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

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

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

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

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

def solve():
  n,m = (int(i) for i in input().split())
  route = [[float("INF")]*n for _ in range(n)]
  for i in range(n):
    route[i][i] = 0
    
  A = []
  B = []
  cost = []
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    route[a-1][b-1] = c
    route[b-1][a-1] = c
    A.append(a-1)
    B.append(b-1)
    cost.append(c)

  
  for k in range(n):
    for i in range(n):
      for j in range(n):
        route[i][j] = min(route[i][j],route[i][k]+route[k][j])
        
  ans = 0
  for i in range(m):
    if cost[i] > route[A[i]][B[i]]:
      ans += 1
  print(ans)
        
solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

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

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

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

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


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

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

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

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

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

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

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

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  route = Graph()
  tmp = [[0]*n for _ in range(n)]
  
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    route.add_edge(a-1,b-1,c)
    route.add_edge(b-1,a-1,c)
    tmp[a-1][b-1] = 1

  
  for i in range(n):
    #iを始点としてjに着く経路
    ds = Dijkstra(route,i)
    for j in range(n):
      if not i== j:
        query = ds.shortest_path(j)
        for k in range(len(query)-1):
            tmp[query[k]][query[k+1]] = 0
  ans = 0
  for i in range(n):
    ans += sum(tmp[i])
  print(ans)
        
solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

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

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

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

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


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

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

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

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

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

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

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

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

def solve():
  n,m = (int(i) for i in input().split())
  route = Graph()
  tmp = [[0]*n for _ in range(n)]
  
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    route.add_edge(a-1,b-1,c)
    route.add_edge(b-1,a-1,c)
    tmp[a-1][b-1] = 1

  
  for i in range(n):
    #iを始点としてjに着く経路
    ds = Dijkstra(route,i)
    for j in range(n):
      if not i== j:
        query = ds.shortest_path(j)
        for k in range(len(query)-1):
            tmp[query[k]][query[k+1]] = 0
  ans = 0
  for i in range(n):
    ans += sum(tmp[i])
  print(ans)
        
solve()

Submission status: Accepted

Solution code:
import heapq

def dijkstra(m, s, t):
    INF = 1e10
    D = [INF] * N
    D[s] = 0
    Q = [(0 if s == v else INF, v) for v in range(N)]
    heapq.heapify(Q)

    while Q:
        c, u = heapq.heappop(Q)
        if D[u] < c:
            continue
        for v, w in m[u]:
            if D[v] > D[u] + w:
                D[v] = D[u] + w
                heapq.heappush(Q, (D[u]+w, v))
    return D[t] 

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

# N < 100
m = [[] for i in range(N)]
E = [0] * M
for i in range(M):
    a, b, w = map(int, input().split())
    E[i] = a-1, b-1, w
    m[a-1].append((b-1,w))
    m[b-1].append((a-1,w))

count = 0
for a, b, w in E:
    d = dijkstra(m, a, b)
    #print((a+1, b+1), d, "w=%d"%w)
    if d < w:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

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

F = deepcopy(D)
for k in range(N):
    for i in range(N):
        for j in range(N):
            F[i][j] = min(F[i][j], F[i][k]+F[k][j])
a = 0
for i in range(N):
    for j in range(N):
        if D[i][j] == F[i][j]:
            a += 1
a //= 2
print(M-a)

Submission status: Accepted

Solution code:
import collections
dic=collections.defaultdict(int)
n,m=map(int,input().split())
INF=float("inf")
d=[[INF for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    d[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    a,b=sorted([a,b])
    dic[(a,b)]=1
    d[a][b]=c
    d[b][a]=c
ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            t=min(d[j][k],d[j][i]+d[i][k])
            if d[j][k]>t:
                d[j][k]=t
                t=tuple(sorted([j,k]))
                if dic[t]:
                    ans+=1
                    dic[t]=0
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
D = [[float("inf")]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
abcs = []
for i in range(M):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  abcs.append((a, b, c))
  D[a][b] = c
  D[b][a] = c
for k in range(N):
  for a in range(N):
    for b in range(N):
      D[a][b] = min(D[a][b], D[a][k]+D[k][b])
#print(D)
r = 0
for m in range(M):
  a, b, c = abcs[m]
  if c > D[a][b]:
    r += 1
print(r)

Submission status: Accepted

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

    minDist = [[float('inf') for _ in range(N)] for _ in range(N)]
    edges = set([])

    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        minDist[a][b] = c
        minDist[b][a] = c
        edges.add((min(a, b), max(a, b)))

    noEdge = set([])

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if minDist[i][j] > minDist[i][k] + minDist[k][j]:
                    minDist[i][j] = minDist[i][k] + minDist[k][j]
                    noEdge.add((min(i, j), max(i, j)))

    nessEdge = edges - noEdge
    print(M - len(nessEdge))

sol()

Submission status: Accepted

Solution code:
import scipy.sparse.csgraph
L=lambda:list(map(int,input().split()))
n,m=L()
s=[n*[float("inf")]for _ in range(n)]
d=[L()for _ in range(m)]
for a,b,c in d:s[a-1][b-1]=s[b-1][a-1]=c
x=scipy.sparse.csgraph.floyd_warshall(s)
print(sum(c!=x[a-1][b-1]for a,b,c in d))

Submission status: Accepted

Solution code:
import scipy.sparse.csgraph;L=lambda:list(map(int,input().split()));n,m=L();s=[n*[float("inf")]for _ in range(n)];d=[L()for _ in range(m)]
for a,b,c in d:s[a-1][b-1]=s[b-1][a-1]=c
x=scipy.sparse.csgraph.floyd_warshall(s);print(sum(c!=x[a-1][b-1]for a,b,c in d))

Submission status: Accepted

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

from heapq import heappop, heappush

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

# 隣接リスト
g = [[] for i in range(N)]
e = []
for i in range(M):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))
    e.append((a-1, b-1, c))

def dijkstra(nodeCnt, start, edges):

    # 始点からのコスト
    costs = [-1 for i in range(nodeCnt)]

    # 確定フラグ
    done = [False for i in range(nodeCnt)]

    # priority queue
    q = []

    costs[start] = 0
    heappush(q, (0, start))

    while len(q) > 0:
        # 確定ノードを取り出す
        doneNode = heappop(q)[1]

        # 確定フラグを立てる
        done[doneNode] = True

        # 接続先ノードの情報を更新
        for to,edge_cost in edges[doneNode]:
            cost = costs[doneNode] + edge_cost
            if costs[to] < 0 or cost < costs[to]:
                costs[to] = cost
                if to not in q:
                    heappush(q, (cost, to))

    return costs

dist = [dijkstra(N, i, g) for i in range(N)]
# print(dist)

# edge(i,j)が最短経路に含まれているとき、
# dist(s,i) + edge(i,j) = dist(s,j)を満たす
ans = 0
for i, j, cost in e:
    isUsed = False
    for s in range(N):
        if dist[s][i] + cost == dist[s][j]:
            isUsed = True
            break
    if not isUsed:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M = map( int, input().split())
    d = dict()
    for i in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = c
    V = [[1000000]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for (s,t), c in d.items():
        V[s][t] = V[t][s] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if V[i][k] + V[k][j] < V[i][j]:
                    V[i][j] = V[i][k] + V[k][j]
    ans = 0
    for (s,t), c in d.items():
        check = False
        for k in range(N**2):
            i = k//N
            j = k%N
            if V[i][s] + c + V[t][j] == V[i][j]:
                check = True
                break
        if check == False:
            ans += 1

    print(ans)
                
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a = input()
    print(" ".join(a.split(",")))
    return

#B
def B():
    k, s = LI()
    ans = 0
    for i in range(k + 1):
        for j in range(k + 1):
            if 0 <= s - (i + j) <= k:
                ans += 1
    print(ans)
    return

#C
def C():
    sx, sy, tx, ty = LI()
    UD = ("U", "D")
    LR = ("R", "L")
    ans = UD[sy > ty] * (abs(sy - ty)) + LR[sx > tx] * (abs(sx - tx))
    ans += UD[ty > sy] * (abs(sy - ty)) + LR[tx > sx] * (abs(sx - tx))
    ans += LR[tx > sx] + UD[sy > ty] * (abs(sy - ty) + 1) + LR[sx > tx] * (abs(sx - tx) + 1) + UD[ty > sy]
    ans += LR[sx > tx] + UD[ty > sy] * (abs(sy - ty) + 1) + LR[tx > sx] * (abs(sx - tx) + 1) + UD[sy > ty]
    print(ans)
    return

#D
def D():
    def dij(s):
        dist = [inf for i in range(n)]
        dist[s] = 0
        q = [[0, s]]
        while q:
            d, f = heappop(q)
            for t, cost in edg[f]:
                if d + cost < dist[t]:
                    dist[t] = d + cost
                    heappush(q, [dist[t], t])
        return dist
    n, m = LI()
    ans = defaultdict(int)
    edg = defaultdict(list)
    for _ in range(m):
        a, b, c = LI_()
        c += 1
        edg[a].append((b, c))
        edg[b].append((a, c))
        ans[(a, b)] = False
        ans[(b, a)] = False
    for i in range(n):
        dis = dij(i)
        q = deque()
        q.append(i)
        while q:
            f = q.popleft()
            for t, cost in edg[f]:
                if dis[t] - dis[f] == cost:
                    ans[(t, f)] = True
                    q.append(t)
    ans = list(ans.values())
    print(ans.count(False) // 2)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
INF = 10 ** 10
costs = [[INF] * 101 for _ in range(101)]

for i in range(N + 1):
    costs[i][i] = 0
paths = []
for i in range(M):
    a, b, c = [int(_) for _ in input().split()]
    costs[a][b] = c
    costs[b][a] = c
    paths.append((a, b, c))

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

for i in range(1, N + 1):
    paths2 = paths.copy()
    for p in paths:
        # 点i から 経路p をつかってp[1]への経路をもつかチェック
        if costs[i][p[0]] >= INF or costs[i][p[1]] >= INF: continue
        if costs[i][p[0]] + p[2] == costs[i][p[1]]:
            paths2.remove(p)
    paths = paths2
print(len(paths))