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())
road = [[10**6]*N for i in range(N)]
tmp = []
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
    tmp.append([a-1,b-1,c])

for k in range(N):
   for i in range(N):
       for j in range(N):
           road[i][j] = min(road[i][j],road[i][k] + road[k][j]) 
ans = 0
for a,b,c in tmp:
    if road[a][b] != c:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
inf = 1000 * 1000 + 10

n, m = map(int, input().split())

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))
    e.add((b, a, c))

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

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

res = 0
for a, b, c in e:
    for s in range(n):
        if g[s][b] == g[s][a] + c:
            res += 1
            break

print(m - res // 2)

Submission status: Accepted

Solution code:

N,M = map(int,input().split())
lis = [[float("inf")] * N for i in range(N)]
flis = [[False] * N for i in range(N)]
ans = 0

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

for i in range(M):

    a,b,c = map(int,input().split())

    a -= 1
    b -= 1

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

    flis[a][b] = True
    flis[b][a] = True

for k in range(N):

    for i in range(N):

        for j in range(N):

            if lis[i][j] > lis[i][k] + lis[k][j]:
                lis[i][j] = lis[i][k] + lis[k][j]

                if flis[i][j]:
                    flis[i][j] = False
                    flis[j][i] = False
                    ans += 1

print (ans)

Submission status: Accepted

Solution code:
inf = 1000 * 1000 + 10

n, m = map(int, input().split())

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))

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

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

# print(g)

need = set()
for a, b, c in e:
    for s in range(n):
        for t in range(n):
            if g[s][t] == g[s][a] + c + g[b][t]:
                need.add((a, b))
                break
        else:
            continue
        break
# print(need)
print(m - len(need))

Submission status: Accepted

Solution code:
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, M = IL()
abc = [IL() for _ in range(M)]

dp = [[MAX_INT]*N for _ in range(N)]
for a, b, c in abc:
  dp[a - 1][b - 1] = c
  dp[b - 1][a - 1] = c
for i in range(N):
  dp[i][i] = 0

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

used = [False]*M
cnt = 0
for edge in range(M):
  a, b, c = abc[edge]
  for i in range(N):
    for j in range(N):
      if dp[i][a - 1] + c + dp[b - 1][j] == dp[i][j]:
        used[edge] = True
        cnt += 1
        break
    else:
      continue
    break

#print(used)
print(M - cnt)

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline
N, M = map(int, input().split())

graph = [[0 if i == j else float("inf") for i in range(N)] for j in range(N)]
for i in range(M):
    ai, bi, ci = map(int, input().split())
    graph[ai - 1][bi - 1] = ci
    graph[bi - 1][ai - 1] = ci

dist = dijkstra(graph, directed=False)

cnt = 0
for i in range(N):
    for j in range(N):
        used = False
        if i > j:
            continue
        for k in range(N):
            if graph[i][j] + dist[k][i] == dist[i][j]:
                used = True
                break
        if not used and graph[i][j] != float("inf"):
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import heapq
INFTY = 10**6
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b,c = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append((b,c))
    if b not in G:
        G[b] = []
    G[b].append((a,c))
F = {}
for s in range(1,N+1):
    F[s] = {}
    d = [INFTY for _ in range(N+1)]
    d[s] = 0
    hist = [0 for _ in range(N+1)]
    heap = [(0,s)]
    while heap:
        cur = heapq.heappop(heap)
        hist[cur[1]] = 1
        for x in G[cur[1]]:
            if hist[x[0]]==0:
                if d[x[0]]>cur[0]+x[1]:
                    d[x[0]] = cur[0]+x[1]
                    F[s][x[0]] = cur[1]
                    heapq.heappush(heap,(d[x[0]],x[0]))
E = []
for s in range(1,N+1):
    for i in range(1,N+1):
        if i!=s:
            cur = i
            while cur!=s:
                j = F[s][cur]
                if (cur,j) in E or (j,cur) in E:
                    break
                else:
                    E.append((cur,j))
                cur = j
print(M-len(E))

Submission status: Accepted

Solution code:
def warshall_floyd(d, next_node):
    # d: nxn adjacent matrix
    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]
                    next_node[i][j] = next_node[i][k]


INF = float("inf")

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

warshall_floyd(d, next_node)

used_path = set()
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        used_path.add((i, next_node[i][j]))
        used_path.add((next_node[i][j], i))

ans = m - len(used_path) // 2

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
d = [[float("inf")] * (N + 1) for _ in range(N + 1)]
e = [[0] * (N + 1) for _ in range(N + 1)]
prev = [[-1] * (N + 1) for _ in range(N + 1)]
res = 2 * M
for _ in range(M):
  a, b, c = map(int, input().split())
  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]
        if prev[k][j] == -1:
          prev[i][j] = k
        else:
          prev[i][j] = prev[k][j]
for i in range(1, N):
  for j in range(i + 1, N + 1):
    s = i
    t = j
    while prev[s][t] != -1:
      p = prev[s][t]
      e[p][t] = 1
      e[t][p] = 1
      t = p
    e[s][t] = 1
    e[t][s] = 1
for i in range(1, N + 1):
  res -= sum(e[i])
print(res // 2)

Submission status: Accepted

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

def dijkstra(graph, start):
    cost = [1000*100 for _ in range(n+1)]
    fixed = [False for _ in range(n+1)]
    cost[start] = 0
    fixed[start] = True
    tmp_sta = start
    while True:
        tmp_min = 1000*100
        for i in graph[tmp_sta]:
            cost[i[0]] = min(cost[i[0]], cost[tmp_sta]+i[1])
        for i in range(1, n+1):
            if tmp_min > cost[i] and fixed[i] == False:
                tmp_min = cost[i]
                tmp_sta = i
        if tmp_min == 1000*100:
            return cost
        else:
            fixed[tmp_sta] = True
    
graph = {}
for i in range(1, n+1):
    graph[i] = []
for i in range(m):
    graph[a[i]].append((b[i], c[i]))
    graph[b[i]].append((a[i], c[i]))

cost2d = [[]]
for i in range(1, n+1):
    cost2d.append(dijkstra(graph, i))

ans = 0
for i in range(m):
    if c[i] > cost2d[a[i]][b[i]]:
        ans += 1
print(ans)

Submission status: Accepted

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

def dijkstra(graph, start, end):
    cost = [1000*100 for _ in range(n+1)]
    fixed = [False for _ in range(n+1)]
    cost[start] = 0
    fixed[start] = True
    tmp_sta = start
    while True:
        tmp_min = 1000*100
        for i in graph[tmp_sta]:
            cost[i[0]] = min(cost[i[0]], cost[tmp_sta]+i[1])
        for i in range(1, n+1):
            if tmp_min > cost[i] and fixed[i] == False:
                tmp_min = cost[i]
                tmp_sta = i
        if tmp_sta == end:
            return tmp_min
        else:
            fixed[tmp_sta] = True
    
graph = {}
for i in range(1, n+1):
    graph[i] = []
for i in range(m):
    graph[a[i]].append((b[i], c[i]))
    graph[b[i]].append((a[i], c[i]))
    
ans = 0
for i in range(m):
    if c[i] > dijkstra(graph, a[i], b[i]):
        ans += 1
print(ans)

Submission status: Accepted

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

inf = 100 * 1000
dist = [[inf for i in range(n+1)] for j in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    dist[a[i]][b[i]] = c[i]
    dist[b[i]][a[i]] = c[i]

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

count = 0
for i in range(m):
    if dist[a[i]][b[i]] < c[i]:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy
input = sys.stdin.readline
n,m=map(int,input().split())
d=[[100000]*n for _ in range(n)]
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
  a0,b0,c0=map(int,input().split())
  a[i]=a0-1
  b[i]=b0-1
  c[i]=c0
  d[a0-1][b0-1]=c0
  d[b0-1][a0-1]=c0
for i in range(n):
  d[i][i]=0
d2=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])
count=0
for i in range(n):
  for j in range(i):
    if d2[i][j] != 100000 and d[i][j]!=d2[i][j]:
      count+=1
print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
INF = 10**5
D=[[INF]*N for _ in range(N)]
for i in range(N):
  D[i][i]=0
path=[]
for i in range(M):
  a,b,c = map(int,input().split())
  D[a-1][b-1]=c
  D[b-1][a-1]=c
  path.append([a-1,b-1,c])
for k in range(N):
  for i in range(N-1):
    for j in range(i+1,N):
      D[i][j]=min(D[i][j],D[i][k]+D[j][k])
      D[j][i]=D[i][j]
ans=0
for a,b,c in path:
  if D[a][b]<c:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
edge = [tuple(map(int,input().split())) for _ in range(m)]
g = [[10**8]*(n) for i in range(n)]
for i in range(n):
  g[i][i] = 0
for a,b,c in edge:
  g[a-1][b-1] = c
  g[b-1][a-1] = c

for k in range(n):
  for i in range(n-1):
    for j in range(i+1,n):
      if g[i][j] > g[i][k] + g[k][j]:
        g[i][j] = g[i][k] + g[k][j]
        g[j][i] = g[i][j]

ans = 0
for a,b,c in edge:
  a -= 1; b -= 1
  if a > b:
    a,b = b,a
  for i in range(n):
    if abs(g[i][a]-g[i][b]) == c:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq


def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        cost, cur_node = heapq.heappop(q)
        if dist[cur_node] < cost:
            continue
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))
    return dist


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

shortest = []
for i in range(n):
    shortest.append(dijkstra(adj, n, i))

ans = 0
for i in range(n):
    for cost, j in adj[i]:
        if cost > shortest[i][j]:
            ans += 1
print(ans // 2)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
G=[[10**18]*n for i in range(n)]
e=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
    e.append([a-1,b-1,c])
for i in range(n):
  G[i][i]=0
for k in range(n):
  for i in range(n):
    for j in range(n):
      if G[i][j]>G[i][k]+G[k][j]:
        G[i][j]=G[i][k]+G[k][j]

print(sum(c>G[a][b] for a,b,c in e))

Submission status: Accepted

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

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

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

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


#nは頂点、mは辺、a、bは頂点、cはaとbの距離


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


res = 0
for i in range(m):
	if c[i] > dist[a[i]-1][b[i]-1]:
		res += 1

print(res)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート

#入力受け取り
def getlist():
	return list(map(int, input().split()))

def warshall_floyd(d, 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])
    return d

#処理内容
def main():
	n,w = map(int,input().split())
	d = [[float("inf") for i in range(n)] for i in range(n)]
	a = []
	b = []
	weight = []
	for i in range(w):
		x,y,z = map(int,input().split())
		a.append(x - 1)
		b.append(y - 1)
		weight.append(z)
		d[x - 1][y - 1] = z
		d[y - 1][x - 1] = z
		for i in range(n):
			d[i][i] = 0
	d = warshall_floyd(d, n)
	ans = 0
	for i in range(w):
		if d[a[i]][b[i]] < weight[i] :
			ans += 1
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import heapq

def dijkstra(graph, node, target):
  INF = float("inf")
  dist = [INF] * node
  dist[target] = 0
  que = [(0, target)]
  while que:
    co, one_node = heapq.heappop(que)
    for next_c, next_n in graph[one_node]:
      dist_candi = dist[one_node] + next_c
      if dist_candi < dist[next_n]:
        dist[next_n] = dist_candi
        heapq.heappush(que, (dist[next_n], next_n))
  return dist


class SetGraph:
  def __init__(self, node_num):
    self.n = node_num
    self.graph = [[] for _ in range(self.n)]

  def add_one_edge(self, start, end, cost):
    self.graph[start].append((cost, end))
    self.graph[end].append((cost, start))

  def get_graph(self):
    return self.graph 
  

n, m = map(int, input().split(" "))
graph_set = SetGraph(n)
for i in range(m):
  a, b, c = map(int, input().split(" "))
  graph_set.add_one_edge(a - 1, b - 1, c)
graph = graph_set.get_graph()

cost = []
for i in range(n):
  temp_cost = dijkstra(graph, n, i)
  cost.append(temp_cost)

result = 0
for i in range(n):
  for c, node in graph[i]:
    if cost[i][node] != c:
      result += 1

print(result // 2)

Submission status: Accepted

Solution code:
def D():
    n, m = map(int, input().split())
    a, b, c = [], [], []
    dist = [[float('inf') if i != j else 0 for j in range(n)] for i in range(n)]

    for _ in range(m):
        in_a, in_b, in_c = map(int, input().split())
        a.append(in_a - 1)
        b.append(in_b - 1)
        c.append(in_c)

    for i in range(m):
        dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i])
        dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i])

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

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

    print(ans)


if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
INF=10**9
w=[[INF]*n for i in range(n)]
for i in range(n):
    w[i][i]=0
V=[]
for i in range(m):
    a,b,c=map(int,input().split())
    V.append((a-1,b-1,c))
    w[a-1][b-1]=c
    w[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            w[i][j]=min(w[i][j],w[i][k]+w[k][j])
count=0
for v in V:
    short=False
    for i in range(n):
        for j in range(i+1,n):
            if w[i][j]==w[i][v[0]]+v[2]+w[v[1]][j] or w[i][j]==w[i][v[1]]+v[2]+w[v[0]][j]:
                short=True
    if not short:
        count+=1
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
cs = [[float('inf')] * n for _ in range(n)]
ns = [[0] * n for _ in range(n)]
for i in range(n):
    cs[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    cs[a][b] = cs[b][a] = c
    ns[a][b] = b
    ns[b][a] = a
for k in range(n):
    for i in range(n):
        for j in range(n):
            s = cs[i][k] + cs[k][j]
            if s < cs[i][j]:
                cs[i][j] = s
                ns[i][j] = ns[i][k]
used = set()
for i in range(n):
    for j in range(i + 1, n):
        path = [i]
        while path[-1] != j:
            s = path[-1]
            t = ns[s][j]
            path.append(t)
            used.add(tuple(sorted([s, t])))
print(m - len(used))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
cs = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    cs[i][i] = 0
es = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    es.append((a, b, c))
    cs[a][b] = cs[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            cs[i][j] = min(cs[i][j], cs[i][k] + cs[k][j])
print(sum([1 for a, b, c in es if cs[a][b] != c]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
cs = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    cs[i][i] = 0
es = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    es.append((a, b, c))
    cs[a][b] = cs[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            cs[i][j] = min(cs[i][j], cs[i][k] + cs[k][j])
res = 0
for a, b, c in es:
    if cs[a][b] != c:
        res += 1
print(res)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
cs = [[float('inf')] * n for _ in range(n)]
ns = [[0] * n for _ in range(n)]
for i in range(n):
    cs[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    cs[a - 1][b - 1] = cs[b - 1][a - 1] = c
    ns[a - 1][b - 1] = b - 1
    ns[b - 1][a - 1] = a - 1
for k in range(n):
    for i in range(n):
        for j in range(n):
            s = cs[i][k] + cs[k][j]
            if s < cs[i][j]:
                cs[i][j] = s
                ns[i][j] = ns[i][k]
used = set()
for i in range(n):
    for j in range(i + 1, n):
        path = [i]
        while path[-1] != j:
            s = path[-1]
            t = ns[s][j]
            path.append(t)
            used.add(tuple(sorted([s, t])))
print(m - len(used))

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in range(M)]

path = defaultdict(int)
for i in range(N):
    path[i] = defaultdict(int)

for i in range(N):
    path[i][i] = []

for i in range(M):
    ABC[i][0] -= 1
    ABC[i][1] -= 1


edges = [list() for _ in range(N)]
for a,b,c in ABC:
    edges[a].append((b,c)) 
    edges[b].append((a,c)) 
inf = 100000000

for i in range(N):
    D = [inf for _ in range(N)]
    D[i] = 0
    stack = [i]
    while stack:
        vertex = stack.pop(-1)
        for b,c in edges[vertex]:
            cost = D[vertex] + c
            if cost < D[b]:
                if vertex > b:
                    path[i][b] = path[i][vertex] + [(vertex,b)]
                else:
                    path[i][b] = path[i][vertex] + [(b,vertex)]
                D[b] = cost
                stack.append(b)

counter = set()

for i in range(N):
    for j in range(N):
        for e in path[i][j]:
            counter.add(e)

print(M-len(counter))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from copy import deepcopy

def main():
    N,M = map(int,input().split())
    INF = 10**10
    l = [[INF for _ in range(N)] for _ in range(N)]
    X = [list(map(int,input().split())) for _ in range(M)]
    for i in range(M):
        l[X[i][0]-1][X[i][1]-1] = X[i][2]
        l[X[i][1]-1][X[i][0]-1] = X[i][2]
    d = deepcopy(l)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                d[j][k] = min(d[j][k],d[j][i]+d[i][k])

    count = 0
    for i in range(N):
        for j in range(N):
            if l[i][j] == d[i][j]:
                count += 1

    print(M-count//2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import copy
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    D = [[float("inf")]*(N+1) for i in range(N+1)]
    ID = [[float("inf")]*(N+1) for i in range(N+1)]
    NEX = [[set() for j in range(N+1)] for i in range(N+1)]
    
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = c
        D[b][a] = c
        ID[a][b] = i
        ID[b][a] = i
        NEX[a][b].add(b)
        NEX[b][a].add(a)
        
    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]
                    NEX[i][j].clear()
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
                elif D[i][j] == D[i][k]+D[k][j] and i!=j and j!=k and k!=i and D[i][j]<float("inf"):
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
    S = set()
    for i in range(1,N+1):
        for j in range(1,N+1):
            if i != j:
                for l in NEX[i][j]:
                    S.add(ID[i][l])
                #print(i,j,D[i][j],NEX[i][j])
    #print(S)            
    print(M-len(S))
            
    
    
main()

Submission status: Accepted

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

n += 1

M = [[float("inf")] * n for i in range(n)]

for i in range(n):
    M[i][i] = 0
for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

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

ans = 0
for i in range(m):
    if M[A[i][0]][A[i][1]] != A[i][2]:
        ans += 1
print(ans)

Submission status: Accepted

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

class Edge:
    def __init__(self, id, node1=-1, node2=-1, cost=-1):
        self.id = id
        self.node1 = node1
        self.node2 = node2
        self.cost = cost
    
    def next(self, num):
        if num == self.node1:
            return self.node2
        elif num == self.node2:
            return self.node1
        else:
            return False

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

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

    ans = set([i for i in range(M)])
    for start in range(N):
        q = []
        check = [False] * N
        costs = [-1] * N
        heapq.heappush(q, (0, start, None))
        used_edge = set()
        while len(q) > 0:
            cost, node, pre_edge = heapq.heappop(q)
            if check[node]:
                if costs[node] == cost:
                    used_edge.add(pre_edge)
                continue
            costs[node] = cost
            check[node] = True
            if pre_edge != None:
                used_edge.add(pre_edge)
            for edge in edges[node]:
                next_node = edge.next(node)
                if not check[next_node]:
                    heapq.heappush(q, (cost + edge.cost, next_node, edge.id))
        ans -= used_edge
    print(len(ans))




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
inf = 10**10
N, M = map(int, input().split())
E = []
edge = [[inf]*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())
    E.append((a-1, b-1))
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c
flag = [[False]*N for _ in range(N)]
def warshall_floyd(d):
    next_v = [[set([i]) for i in range(N)] for j in range(N)]
    for i in range(N):
        for a in range(N):
            for b in range(N):
                if d[a][b] > d[a][i]+ d[i][b]:
                    d[a][b] = d[a][i]+ d[i][b]
                    next_v[a][b] = next_v[a][i].copy()
                elif d[a][b] == d[a][i]+ d[i][b]:
                    next_v[a][b]|=next_v[a][i]
    return (next_v, d)
next_v, d = warshall_floyd(edge)    
ans = M
for a, b in E:
    if any(b in next_v[a][i] or a in next_v[b][i] for i in range(N)):
        ans -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
graph = [[INF] * n for _ in range(n)]
for i in range(n):
    graph[i][i] = 0


for a, b, c in LIR(m):
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c


dist = [[graph[i][j] for j in range(n)] for i in range(n)]




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



cnt = 0
for i in range(n):
    for j in range(i, n):
        if graph[i][j] != INF and graph[i][j] > dist[i][j]:
            cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for i in range(n): A[i][i]=0
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        A[a][b]=c
        A[b][a]=c
    from copy import deepcopy
    C=deepcopy(A)
    # Warshall-Floyd
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])
    # count
    B=set()
    for s,i,j in product(range(n),repeat=3):
        if (C[i][j]!=INF) and (i!=j) and (A[s][i]+C[i][j]==A[s][j]):
            B.add((min(i,j),max(i,j)))
    print(m-len(B))

resolve()

Submission status: Accepted

Solution code:
N,M=map(int,input().split());e=[[9e9]*N for _ in range(N)];g=[[0]*N for _ in range(N)]
for _ in range(M):a,b,c=map(int,input().split());e[a-1][b-1]=e[b-1][a-1]=c
for i in range(N):
 for j in range(N):
  for k in range(N):
   if e[j][k]>e[j][i]+e[i][k]:
    e[j][k]=e[j][i]+e[i][k];g[j][k]=1
print((sum(sum(l)for l in g)+2*M-N*N)//2)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
d = [[float('inf') for _ in range(N + 1)] for _ in range(N + 1)]
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c
    edges.append((a, b, c))

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

ans = 0
for edge in edges:
    if edge[2] != d[edge[0]][edge[1]]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    inf =1000000000
    N,M = map(int,input().split())
    a,b,c = [],[],[]
    dist = [[0 if i ==j else inf for j in range(N)] for i in range(N)]
    for _ in range(M):
        x,y,z = map(int,input().split())
        a.append(x-1)
        b.append(y-1)
        c.append(z)

    for i in range(M):
        dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i])
        dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i])

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

    ans = M
    for i in range(M):
        if dist[a[i]][b[i]] == c[i]:
            ans -=1
    print(ans)

if __name__ == '__main__':
    main()