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(graph):
    n_nodes = len(graph)

    froms = []
    for i in range(len(graph)):
        froms.append([])
        for j in range(len(graph[i])):
            if i == j:
                froms[i].append(0)
            elif graph[i][j] < float("inf"):
                froms[i].append(i)
            else:
                froms[i].append(None)

    for k in range(n_nodes):
        for i in range(n_nodes):
            for j in range(n_nodes):
                adj_cost = graph[i][k] + graph[k][j]
                if adj_cost < graph[i][j]:
                    graph[i][j] = adj_cost
                    froms[i][j] = froms[k][j]
    
    has_negative_loop = False
    for i in range(n_nodes):
        if graph[i][i] < 0:
            has_negative_loop = True
            break

    return graph, froms, has_negative_loop

def restore_path(froms, start, goal):
    path = []
    cur = goal
    path.append(goal)
    while cur != start:
        prev = froms[start][cur]
        path.append(prev)
        cur = prev
    path.reverse()
    return path

def resolve():
    N, M = list(map(int, input().split()))
    graph = [[float("inf") for _ in range(N)] for __ in range(N)]
    import copy
    exists = [[False for _ in range(N)] for __ in range(N)]
    for i in range(M):
        a, b, c = list(map(int, input().split()))
        graph[a-1][b-1] = c
        graph[b-1][a-1] = c
        exists[a-1][b-1] = True
        exists[b-1][a-1] = True
    costs, froms, _ = warshall_floyd(graph)
    # print(froms)

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            path = restore_path(froms, i, j)
            # print("{} to {}".format(i, j))
            # print(path)
            src = 0
            for dst in range(1, len(path)):
                exists[path[src]][path[dst]] = False
                exists[path[dst]][path[src]] = False
                src = dst
    
    print(sum(sum(exists, []))//2)



if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
INF = 10**18
d = [[INF]*n for _ in range(n)]
for i in range(n): d[i][i] = 0
A = [0]*m
B = [0]*m
C = [0]*m
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    A[i] = a
    B[i] = b
    C[i] = c
    d[a][b] = c
    d[b][a] = 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 i in range(m):
    if d[A[i]][B[i]] < C[i]: ans += 1
print(ans)

Submission status: Accepted

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

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

cnt = 0
for i in range(n):
    for j in range(n):
        if d[i][j] == INF: continue
        if nd[i][j] < d[i][j]: cnt += 1
print(cnt//2)

Submission status: Accepted

Solution code:
import networkx as nx
import itertools

N, M = map(int, input().split())
G = nx.Graph()
G.add_nodes_from(range(1, N + 1))
G.add_weighted_edges_from([map(int, input().split()) for _ in range(M)])
S = nx.floyd_warshall(G)

ans = M
for i, j, d in G.edges(data=True):
    for s, t in itertools.combinations(G.nodes(), 2):
        if S[s][i] + d['weight'] + S[j][t] == S[s][t]:
            ans -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from copy import deepcopy
def main():
    N, M = map(int, input().split())
    INF = 10**9
    to = [[INF]*N for _ in range(N)]
    edges = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        to[a][b] = c
        to[b][a] = c
        edges.append((a, b, c))
    
    for i in range(N): to[i][i] = 0

    def floyd_warshall():
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    to[i][j] = min(to[i][j], to[i][k]+to[k][j])
    
    floyd_warshall()
    ans = 0
    for a, b, c in edges:
        if to[a][b] != c:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[[]for _ in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  a,b=a-1,b-1
  g[a].append((c,b,i))
  g[b].append((c,a,i))
no_used=[1]*m
from heapq import heapify,heappop,heappush
def dks(t0):
  todo=[[0,t0,-1]]
  heapify(todo)
  seen=[0]*n
  while todo:
    d,t,i=heappop(todo)
    if seen[t] and seen[t]<d:continue
    seen[t]=d
    if i>-1:no_used[i]=0
    l=g[t]
    for d_,t_,i_ in l:
      heappush(todo,[d+d_,t_,i_])
for i in range(n):
  dks(i)
print(sum(no_used))

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
#import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n,m=map(int,input().split())
edge=[list(map(int,input().split())) for _ in range(m)]
           
inf=10**9
nextm=[[inf]*n for _ in range(n)]

for i in range(n):
    nextm[i][i]=0
for i in range(m):
    to,f,weight=edge[i]
    nextm[to-1][f-1]=weight
    nextm[f-1][to-1]=weight

for k in range(n):
    for i in range(n):
        for j in range(n):
            if nextm[i][j]>nextm[i][k]+nextm[k][j]:
                nextm[i][j]=nextm[i][k]+nextm[k][j]
res=0               
for i in range(m):
  a,b,c=edge[i]
  if c>nextm[a-1][b-1]:
    res+=1
print(res)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    cos = []
    row = []
    col = []
    for _ in range(m):
        a,b,c = map(int,ipt().split())
        row.append(a-1)
        col.append(b-1)
        cos.append(c)
    csr = csr_matrix((cos,(row,col)),shape=(n,n))
    d = dijkstra(csr,directed=False)
    ans = 0
    for i in range(m):
        rwi = row[i]
        cli = col[i]
        csi = cos[i]
        dri = d[rwi]
        dci = d[cli]
        for j in range(n):
            if dri[j] + csi == dci[j]:
                break
            if j == n-1:
                ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os,io
import heapq
INF=10**9
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline  
n,m=map(int,input().split())
edges=[]
d=[]
for i in range(n+1):
  d.append([])
  for j in range(n+1):
    d[-1].append(INF)
  d[i][i]==0
for i in range(m):
  a,b,c=list(map(int,input().split()))
  edges.append([a,b,c])
  d[a][b]=c
  d[b][a]=c
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(m):
  a=edges[i][0]
  b=edges[i][1]
  c=edges[i][2]
  if d[a][b]<c:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
path = [[float("inf")]*N for i in range(N)]
ans = [[[float("inf")]]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    path[a-1][b-1] = c
    path[b-1][a-1] = c
    ans[a-1][b-1] = [i]
    ans[b-1][a-1] = [i]
for i in range(N):
    path[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if path[i][k]+path[k][j] < path[i][j]:
                path[i][j] = path[i][k]+path[k][j]
                ans[i][j] = ans[i][k]+ans[k][j]
total = set()
for i in range(N):
    for j in range(N):
        p = set(ans[i][j])
        total = total|p
print(M-len(set(total))+1)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
l=[np.array([0]*N) for i in range(N)]
for i in range(M):
   tmp=(list(map(int,input().split())))
   l[tmp[0]-1][tmp[1]-1]=tmp[2]
   l[tmp[1]-1][tmp[0]-1]=tmp[2]
l2=csr_matrix(l)
l2=floyd_warshall(l2)
ans=0
for i in range(N):
   for j in range(i):
      if l[i][j] != l2[i][j] and l[i][j] != 0:
         ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq


INF = 10 ** 6


def check(N, adj_nodes, costs, from_node, to_node):
    # calculate shortest distances on a graph without a edge (from_node, to_node)
    dists = [INF for _ in range(N)]
    dists[from_node] = 0
    frontier = [(0, from_node)]
    while len(frontier) > 0:
        d, node = heapq.heappop(frontier)
        for next_node in adj_nodes[node]:
            if (from_node, to_node) == (node, next_node):
                continue
            next_d = costs[node][next_node] + dists[node]
            if dists[next_node] > next_d:
                dists[next_node] = next_d
                heapq.heappush(frontier, (next_d, next_node))
    return costs[from_node][to_node] > dists[to_node]


def main():
    N, M = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    costs = [[INF for _ in range(N)] for _ in range(N)]
    edges = list()
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
        costs[a][b] = c
        costs[b][a] = c
        edges.append((a, b))
    ans = 0
    for edge in edges:
        from_node, to_node = edge
        if check(N, adj_nodes, costs, from_node, to_node):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
INF = 10**10
edge_idx = {}
graph = [[] for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  a -= 1; b -= 1
  graph[a].append((b, c))
  graph[b].append((a, c))
  edge_idx[(a, b)] = edge_idx[(b, a)] = i

used = set()
def dijkstra(node):
  global used
  dist = [INF] * N
  dist[node] = 0
  e = []
  for child, cost in graph[node]:
    heappush(e, (cost, child, node))
  while e:
    cost, node, par = heappop(e)
    if dist[node] < INF:
      if dist[node] == cost:
        used.add(edge_idx[(node, par)])
      continue
    dist[node] = cost
    used.add(edge_idx[(node, par)])
    for child, c in graph[node]:
      if dist[child] < INF:
        continue
      heappush(e, (cost+c, child, node))

for i in range(N):
  dijkstra(i)

print(M - len(used))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a, b, c = zip(*[list(map(int, input().split())) for i in range(m)])

dist = [[1e18]*n for i in range(n)]
for i in range(m):
    dist[a[i]-1][b[i]-1] = dist[b[i]-1][a[i]-1] = min(dist[a[i]-1][b[i]-1], c[i])

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
ans = 0
for i in range(m):
    if dist[a[i]-1][b[i]-1]<c[i]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc051/submissions/1055446

def main():
    import sys
    input = sys.stdin.readline

    inf = 1000 * 100 + 10

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

    dist = [[inf for _ in range(N)] for _ in range(N)]
    for j in range(N):
        dist[j][j] = 0

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

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

    ans = 0
    for a, b, c in es:
        if dist[a][b] == c: continue
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc051/submissions/1055446

def main():
    import sys
    input = sys.stdin.readline

    inf = 1000 * 100 + 10

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

    dist = [[inf for _ in range(N)] for _ in range(N)]
    for j in range(N):
        dist[j][j] = 0

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

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

    ans = 0
    for a, b, c in es:
        if dist[a][b] == c: continue
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations
    import sys
    input = sys.stdin.readline

    inf = 1000 * 100 + 10

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

    dist = [[[inf, 0] for _ in range(N)] for _ in range(N)]
    for j in range(N):
        dist[j][j] = [0, 0]

    for idx in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        dist[a][b][0] = dist[b][a][0] = c
        dist[a][b][1] = dist[b][a][1] = 1 << idx  # weight,edge_idx

    for k in range(N):
        for i in range(N):
            for j in range(N):
                nd = dist[i][k][0] + dist[k][j][0]
                if dist[i][j][0] > nd:
                    dist[i][j][0] = nd
                    dist[i][j][1] = dist[i][k][1] | dist[k][j][1]
                elif dist[i][j][0] == nd:
                    dist[i][j][1] |= dist[i][k][1] | dist[k][j][1]

    used_edge = 0
    for frm, to in combinations(range(N), r=2):
        used_edge |= dist[frm][to][1]

    print(M - bin(used_edge).count('1'))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000001)

def main():
    n, m = map(int, input().rstrip().split())
    dist = [[500000 for i in range(n)]for j in range(n)]

    for i in range(n):
        for j in range(n):
            if (i==j):
                dist[i][j]=0

    a = [None] * m
    b = [None] * m
    c = [None] * m

    for i in range(m):
        x, y, z = map(int, input().rstrip().split())
        dist[x-1][y-1] =  min(dist[x-1][y-1], z)
        dist[y-1][x-1] =  min(dist[x-1][y-1], z)
        a[i] = x - 1
        b[i] = y - 1
        c[i] = z
        
    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(dist)
    result = m

    for i in range(m):
        for j in range(n):
            if dist[j][a[i]] + c[i] == dist[j][b[i]]:
                result -= 1
                break

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000001)

def main():
    n, m = map(int, input().rstrip().split())
    dist = [[500000 for i in range(n)]for j in range(n)]

    for i in range(n):
        for j in range(n):
            if (i==j):
                dist[i][j]=0

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

    for i in range(m):
        x, y, z = map(int, input().rstrip().split())
        dist[x-1][y-1] =  min(dist[x-1][y-1], z)
        dist[y-1][x-1] =  min(dist[x-1][y-1], z)
        a.append(x-1)
        b.append(y-1)
        c.append(z)
        
    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(dist)
    result = m

    for i in range(m):
        for j in range(n):
            if dist[j][a[i]] + c[i] == dist[j][b[i]]:
                result -= 1
                break

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000001)

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

for i in range(n):
    for j in range(n):
        if (i==j):
            dist[i][j]=0

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

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
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(dist)
result = m

for i in range(m):
    for j in range(n):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1
            break

print(result)

Submission status: Accepted

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

INF = 10**7
dist = [[INF for j in range(N)] for i in range(N)]
d = [[INF for j in range(N)] for i in range(N)]
prev = [[i for j in range(N)] for i in range(N)]
t = [[0 for j in range(N)] for i in range(N)]

# 初期化
for i in range(N):
    d[i][i] = 0
    dist[i][i] = 0

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

#　d[a][b]:aとbの距離
def warshall_floyd(n):
    for k in range(n):
        for i in range(n):#始点
            for j in range(n):#終点
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])

warshall_floyd(N)
ans = 0
for i in range(N):
    for j in range(N):
        if dist[i][j] != INF and d[i][j] != dist[i][j]:
            ans += 1
print(ans//2)

Submission status: Accepted

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

INF = 10**7
dist = [[INF for j in range(N)] for i in range(N)]
d = [[INF for j in range(N)] for i in range(N)]
prev = [[i for j in range(N)] for i in range(N)]
t = [[0 for j in range(N)] for i in range(N)]

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



#　d[a][b]:aとbの距離
def warshall_floyd(n):
    for k in range(n):
        for i in range(n):#始点
            for j in range(n):#終点
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])

warshall_floyd(N)
ans = 0
for i in range(N):
    for j in range(N):
        if dist[i][j] != INF and d[i][j] != dist[i][j]:
            ans += 1
print(ans//2)

Submission status: Accepted

Solution code:
class WarshallFloyd:
    def __init__(self,V,inf):
        self.V=V
        self.inf=inf
        self.G=[[inf]*V for _ in range(V)]
        for i in range(V):
            self.G[i][i]=0

    def add(self,u,v,cost):
        self.G[u][v]=min(self.G[u][v],cost)

    def shortest_path(self):
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    self.G[i][j]=min(self.G[i][j],self.G[i][k]+self.G[k][j])
        return self.G

    def exist_negative_loop(self):
        for i in range(self.V):
            if self.G[i][i]<0:
                return True
        return False

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    inf=10**9
    n,m=map(int,readline().split())
    wf=WarshallFloyd(n,inf)
    a=[0]*m
    b=[0]*m
    c=[0]*m
    for i in range(m):
        a[i],b[i],c[i]=map(int,readline().split())
        a[i]-=1
        b[i]-=1
        wf.add(a[i],b[i],c[i])
        wf.add(b[i],a[i],c[i])

    li=wf.shortest_path()

    flags=[False]*m
    for i in range(m):
        v=a[i]
        u=b[i]
        w=c[i]
        for j in range(n):
            for k in range(n):
                if li[j][v]+w+li[u][k]==li[j][k]:
                    flags[i]=True

    print(len([i for i in range(m) if flags[i]==False]))

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n,w = map(int,input().split()) #n:頂点数　w:辺の数
from collections import defaultdict
D=defaultdict(list)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j]>d[i][k]+d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    D[(i,j)]=D[(i,k)]+D[(k,j)][1:]
    return d
done=[[-1]*n for _ in range(n)]
d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
    D[(x-1,y-1)]=[x-1,y-1]
    D[(y-1,x-1)]=[y-1,x-1]
    done[x-1][y-1]=0
    done[y-1][x-1]=0
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)
for l in D.values():
    for i in range(1,len(l)):
        a=l[i-1]
        b=l[i]
        done[a][b]=1
        done[b][a]=1
import numpy as np
done=np.array(done)
ans=(done==0).sum()
#print(D)
#print(done)
print(ans//2)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
INF = float("inf")
edge = [[] for _ in range(N)]
#print(load)
#dis = [[] for _ in range(N)]
List = [] #0は未使用、1は使用
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  edge[a].append([c,b,i])
  edge[b].append([c,a,i])
  List.append([c,a,b,i])

def dijkstra_heap(s):
  d = [INF for _ in range(N)]
  used = [True for _ in range(N)]
  d[s] = 0
  used[s] = False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while len(edgelist):
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]: #すでに探索済みの場合にはスキップ
      continue
    v = minedge[1]
    d[v] = minedge[0]
    #L.add(minedge[2]) #この道を使用したと記録
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1],e[2]])
  return d

L = set([])
for i in range(N):
  dist = dijkstra_heap(i)
  for c, s, g, ID in List: #道のリストの一つ一つの点を見て、それが最短距離で使われているか確認
    if dist[s] + c == dist[g]:
      L.add(ID)
ans = M -len(L)
print(ans)

Submission status: Accepted

Solution code:
#2020-05-28 22:26:38
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

def modify(x,y):
    if x>y:
        x,y = y,x
    return (x,y)


edge = [[] for _ in range(N)]
edgeid = dict()
for k in range(M):
    u,v,r = map(int,input().split())
    edge[u-1].append((v-1, r))
    edge[v-1].append((u-1, r))
    edgeid[modify(u-1,v-1)] = k

from heapq import heappop,heappush, heapify
INF = 10**20
def dijkstra2(S, N, Edge):
    # S: start vertex
    # N: number of vertices
    # Edge: adjacent list [node, cost]
    

    dist = [INF]*N
    dist[S] = 0
    root = [-1]*N
    que = [(0, S)]
    heapify(que)
    
    while que:
        c, v = heappop(que)
        if dist[v] < c: continue

        for nv, nc in Edge[v]:
            if c+nc < dist[nv]:
                dist[nv] = c+nc
                root[nv] = v
                heappush(que, (c+nc, nv))
    
    return [dist, root]

def find_path(S,T,root):
    # SからTへのパスを逆順で返す
    path = []
    cur = T
    while cur!=S:
        past = root[cur]
        path.append((past, cur))
        cur = past
    return path

unused_flag = [True] * M
for start in range(N):
    dist, root = dijkstra2(start, N, edge)
    for goal in range(N):
        if start==goal:continue
        for p in find_path(start, goal, root):
            unused_flag[edgeid[modify(p[0],p[1])]] = False

print(sum(unused_flag))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
INF = 10**10
d = [[INF]*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
nxt = [[[i] for i in range(n)] for _ in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            if d[i][k]+d[k][j] < d[i][j]:
                d[i][j] = d[i][k]+d[k][j]
                nxt[i][j] = nxt[i][k][:]
            elif d[i][k]+d[k][j] == d[i][j]:
                nxt[i][j] += nxt[i][k]
s = set()
for start in range(n):
    for goal in range(n):
        if start==goal:
            continue
        def DFS(i):
            for j in nxt[i][goal]:
                s.add((i, j))
                if j!=goal:
                    DFS(j)
        DFS(start)
print(m-len(s)//2)

Submission status: Accepted

Solution code:
import sys
import heapq
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    edge = [[] for _ in range(n)]
    k = []
    for _ in range(m):
        a, b, c = map(int, input().split())
        edge[a - 1].append([c, b - 1])
        edge[b - 1].append([c, a - 1])
        k.append([c, a - 1, b - 1])

    def dijkstra_heap(s):
        d = [f_inf] * n
        used = [True] * n
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist, e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, [e[0] + d[v], e[1]])
        return d

    used = set()
    for i in range(n):
        dist = dijkstra_heap(i)
        for d, to, fr in k:
            if dist[to] + d == dist[fr]:
                used.add((to, fr))

    print(len(k) - len(used))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import heapq
INFTY = 10**6
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
Arc = {}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
    Arc[(a,b)]=0
    Arc[(b,a)]=0
for s in range(1,N+1):
    dist = [INFTY for _ in range(N+1)]
    dist[s] = 0
    hist = [0 for _ in range(N+1)]
    heap = [(0,s)]
    pre = {}
    while heap:
        d,x = heapq.heappop(heap)
        if dist[x]<d:continue
        hist[x] = 1
        for y,e in G[x]:
            if hist[y]==0 and dist[y]>d+e:
                dist[y] = d+e
                pre[y] = x
                heapq.heappush(heap,(d+e,y))
    for j in pre:
        a = j
        while pre[a]!=s:
            b = pre[a]
            Arc[(a,b)] = 1
            Arc[(b,a)] = 1
            a = b
        Arc[(a,s)] = 1
        Arc[(s,a)] = 1
cnt = 0
for x in Arc:
    if Arc[x]==0:
        cnt += 1
print(cnt//2)

Submission status: Accepted

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

minDist = [[INF] * N for _ in range(N)]
for i in range(N):
    minDist[i][i] = 0

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

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

ans = 0
for fr, to, d in edges:
    if minDist[fr][to] < d:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
inf = 10**8
d = [[inf]*N for _ in range(N)]
E = [[] 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
    E[a-1].append((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])

cnt = 0
for i in range(N):
    for e in E[i]:
        j = e[0]
        c = e[1]
        flag = False
        for k in range(N):
            for l in range(k+1, N):
                if d[k][l] == d[k][i]+c+d[j][l] or d[k][l] == d[k][j]+c+d[i][l]:
                    cnt += 1
                    flag = True
                    break
            if flag:
                break
print(M-cnt)

Submission status: Accepted

Solution code:
# まずワーシャルフロイドの表を作る
# 元の表で頂点A-Bを結ぶ距離が、ワーシャルフロイドの表で短縮されていたら、その辺は使わないで良いことになる
# この個数を数える

import sys
readline = sys.stdin.readline

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense

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

INF = 10 ** 9
G = [[INF] * N for i in range(N)]
for i in range(M):
  a,b,c = map(int,readline().split())
  G[a-1][b-1] = c
  G[b-1][a-1] = c

d = csgraph_from_dense(G, null_value=10**9)
d = floyd_warshall(d)

ans = 0
for a in range(N-1):
  for b in range(a + 1,N):
    if G[a][b] == INF:
      continue
    if G[a][b] > d[a][b]:
      ans += 1
      
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
d = [[1000000]*N for _ in range(N)]
d_dict = {}

inf = 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
  d_dict[(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 key in d_dict:
  if d[key[0]][key[1]] < d_dict[key]:
    ans += 1
    
print(ans)