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:
import sys
input = sys.stdin.readline

inf = float('inf')

# dist[i][j]: iからjへのコスト,  n:頂点数
def warshall_floyd(dist,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

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

warshall_floyd(ad,N)
ans = M

for a,b,c in edges:
    if a > b:
        a,b = b,a
    for s in range(N):
        for e in range(s+1,N):
            if ad[s][a] + c + ad[b][e] == ad[s][e]:
                ans -= 1
                break
        else:
            continue
        break

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        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
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

n,m = li()

edges = []
graph = [[] for _ in range(n)]
adj_mat = [[0]*n for _ in range(n)]

for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    edges.append((a,b,c))
    
# 各点からの最短dist
for i in range(n):
    adj_mat[i] = dijkstra(graph, n, i)
    
    
# 最短路とedgeの比較
ans = 0
for ai, bi, ci in edges:
    if adj_mat[ai][bi] < ci:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from operator import itemgetter
n,m = map(int,input().split())
edge = [list(map(int,input().split())) for i in range(m)]

kyori =[[float("inf")]*n for i in range(n)]
for i in range(n):
  kyori[i][i] = 0
  
def dfs(start,goal):
  visited_cost = [float("inf")]*n
  visited_cost[start] = 0
  que = deque()
  que.append(start)
  while que:
    pos = que.pop()
    for [next_pos,cost] in tree[pos]:
      #print(next_pos,cost)
      if visited_cost[next_pos] > visited_cost[pos] + cost:
        visited_cost[next_pos] = visited_cost[pos] + cost
        que.append(next_pos)    
  return visited_cost[goal]

edge = sorted(edge, key=itemgetter(2))
tree = [[] for i in range(n)]

ans = m
for [start,goal,cost] in edge:
  start -= 1
  goal -= 1
  if cost <= dfs(start,goal):
    tree[start].append([goal,cost])
    tree[goal].append([start,cost])
    ans -= 1
    
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
N,M=list(map(int, input().strip().split()))
abc={}
used={}
for _ in range(M):
    a,b,c=(list(map(int, input().strip().split())))
    abc[a,b]=c
    used[a,b]=False
spth=[[float("inf")]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    spth[i][i]=0
for ab,c in abc.items():
    spth[ab[0]][ab[1]]=c
    spth[ab[1]][ab[0]]=c
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            d=spth[i][k]+spth[k][j]
            if spth[i][j] > d:
                spth[i][j]=d

for ab,c in abc.items():
    for s in range(1,N+1):
        if used[ab]:break
        if spth[s][ab[1]]==spth[s][ab[0]]+c:
            used[ab]=True
            break
print(sum(not i for i in used.values()))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[list(map(int,input().split()))for i in range(m)]
s=[[float("inf")]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    s[i][i]=0
for i in range(m):
    s[a[i][0]][a[i][1]]=a[i][2]
    s[a[i][1]][a[i][0]]=a[i][2]
for h in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if s[i][j]>s[i][h]+s[h][j]:
                s[i][j]=s[i][h]+s[h][j]
c=0
for i in range(m):
    for j in range(1,n+1):
        if s[j][a[i][0]]!=float("inf"):
            if s[j][a[i][0]]+a[i][2]==s[j][a[i][1]]:
                break
    else:
        c+=1
print(c)

Submission status: Accepted

Solution code:
n,M =map(int,input().split())
inf = 10**15

dist = [[inf for i in range(n)] for i in range(n)]
route = [[ [] for i in range(n)] for i in range(n)]
import copy

for i in range(M):
    ak,bk,ck = map(int,input().split())
    dist[ak-1][bk-1]  =ck
    dist[bk-1][ak-1]  =ck

for i in range(n):
    for k in range(n):
        route[i][k] = [i,k]
        route[k][i] = [k,i]


for a in range(n):
    for b in range(n):
        for c in range(n):
            #print(a,b,c)
            if dist[b][a]+dist[a][c] < dist[b][c]:
                route[b][c] = copy.deepcopy(route[b][a]) + (copy.deepcopy(route[a][c])[1:])
                dist[b][c] =  dist[b][a]+dist[a][c]


#for i in range(n):
    #print(route[i])

used = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    for k in range(n):
        for m in range(len(route[i][k])-1):
            used[route[i][k][m]][route[i][k][m+1]] = 1
            used[route[i][k][m+1]][route[i][k][m]] = 1
#for i in range(n):
    #print(used[i])

ans = 0
for i in range(n):
    for k in range(n):
        if used[i][k]:
            ans += 1

print(M-(ans//2))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
n, m = map(int, input().split())
edges = [[0]*n for i in range(n)]
query = []
ans = 0
for i in range(m):
    a,b,c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c
    query.append([a-1, b-1, c])
for a,b,c in query:
    edges[a][b] = 0
    edges[b][a] = 0
    dist_ = dijkstra(edges, directed=False, indices=a)[b]
    if dist_ < c:
        ans += 1
    edges[a][b] = c
    edges[b][a] = c
print(ans)

Submission status: Accepted

Solution code:
N, M= map(int, input().split())
ABC = [list(map(int,input().split())) for _ in range(M)]
# 最短距離を求めるのでワーシャルフロイド法(O(N^3))

inf = float("inf")
dist = [[inf] * N for _ in range(N)]

for a,b,c in ABC:
  a,b = a-1, b-1
  dist[a][b] = c
  dist[b][a] = c

for mid in range(N):
  for start in range(N):
    for end in range(N):
      dist[start][end] = min(dist[start][end],
                 dist[start][mid] + dist[mid][end])
# すべての辺を見て、一致しない辺の個数
ans = 0
for a,b,c in ABC:
  a,b = a-1, b-1
  if dist[a][b] != c:
    ans += 1
print(ans)

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[9999999 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	org = copy.deepcopy(maps)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])
				maps[j][i] = min(maps[i][j], maps[i][k] + maps[k][j])
			
	for i in range(N):
		for j in range(N):
			if i <= j:
				continue
			if org[i][j] == 9999999:
				continue
			if org[i][j] != maps[i][j]:
				ans += 1
		
	print(ans)
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[9999999 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	org = copy.deepcopy(maps)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				#if maps[i][j] == 9999999:
					#continue
				if i <= j:
					continue
				maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])
				maps[j][i] = min(maps[i][j], maps[i][k] + maps[k][j])
			
	for i in range(N):
		for j in range(N):
			if i <= j:
				continue
			if org[i][j] == 9999999:
				continue
			if org[i][j] != maps[i][j]:
				ans += 1
		
	print(ans)
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def int_raw():
    return int(raw_input())
 
def ss_raw():
    return raw_input().split()
 
def ints_raw():
    return map(int,ss_raw())
 
INF = 1<<29
 
def make1d_arr(n,val=INF):
    return [val for i in xrange(n)]

def make2d_arr(w,h,val =INF):
    return [[val for i in xrange(w)]for i in xrange(h)]
 
def floyd_warshall(costs):
    N = len(costs)
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                costs[i][j]  = min(costs[i][j],costs[i][k]+costs[k][j])
    return costs
 
N,M = ints_raw()
costs = make2d_arr(N+1,N+1,INF)
E = []
for i in xrange(M):
    a,b,c = ints_raw()
    E.append((a,b,c))
    costs[a][b]=c
    costs[b][a]=c
 
costs = floyd_warshall(costs)
 
ans  = 0
for e in E:
    if costs[e[0]][e[1]] < e[2]:
        ans+=1
print ans

Submission status: Accepted

Solution code:
import heapq
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

N,W=map(int,input().split())
G=[list() for i in range(N)]
for i in range(W):
    a,b,c=map(int,input().split())
    G[a-1].append(edge(b-1,c))
    G[b-1].append(edge(a-1,c)) #無向グラフならこれも

def dijkstra(o):
    d=[float('inf') for i in range(N)]
    d[o]=0
    hq=[]
    prev=[[] for i in range(N)]
    heapq.heappush(hq,(0,o))
    while hq:
        p=heapq.heappop(hq)
        v=p[1]
        if(d[v]<p[0]):
            continue
        for i in G[v]:
            if(d[i.to]>d[v]+i.cost):
                d[i.to]=d[v]+i.cost
                prev[i.to]=prev[v]+[str(sorted([v,i.to]))]
                heapq.heappush(hq,(d[i.to],i.to))
    return d,prev


ans=set()
for i in range(N):
    tmp=dijkstra(i)[1]
    for j in tmp:
        if(j):
            ans.add(str(j[0]))
print(W-len(ans))

Submission status: Accepted

Solution code:
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int,ss_raw())

INF = 1<<29

def make2d_arr(w,h,val =INF):
    return [[val]*w for i in xrange(h)]

def floyd_warshall(costs):
    N = len(costs)
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                costs[i][j]  = min(costs[i][j],costs[i][k]+costs[k][j])
    return costs

N,M = ints_raw()
costs = make2d_arr(N+1,N+1,INF)
E = []
for i in xrange(M):
    a,b,c = ints_raw()
    E.append((a,b,c))
    costs[a][b]=c
    costs[b][a]=c

costs = floyd_warshall(costs)

ans  = 0
for e in E:
    if costs[e[0]][e[1]] < e[2]:
        ans+=1
print ans

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
abc = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]

dist = [[9999999 for _ in range(n)] for _ in range(n)]

e = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    e[a][b] = c + 1
    e[b][a] = c + 1

for i in range(n):
    h = []
    heapq.heappush(h, [0, i])
    temp = set()
    #temp.add(i)
    while len(temp) < n:
        d, p = heapq.heappop(h)
        while p in temp:
            d, p = heapq.heappop(h)
        dist[i][p] = d
        temp.add(p)
        for x in e[p].keys():
            heapq.heappush(h, [d + e[p][x], x])

#for i in range(n): print(dist[i])

ans = m
for a, b, c in abc:
    for i in range(n):
        if c + 1 == dist[a][i] - dist[b][i]:
            ans -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(w):
    #d[i][j]: iからjへの最短距離
    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])
    return w

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

d = [[10**7]*n for i in range(n)]
w = [[10**10]*n for i in range(n)]

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

w = warshall_floyd(w)


res = 0
for i in range(n):
    for j in range(n):
        if w[i][j] == d[i][j]:
            res += 1
print(m-res//2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
edges=[[] for _ in range(n)]
ABC=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    edges[a].append((b,c))
    edges[b].append((a,c))
    ABC.append([a,b,c])

def dijkstra(x,route):
    d=[float('inf')]*n
    d[x]=0
    visited={x}
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        visited.add(u)
        for node,cost in route[u]:
            if (node not in visited) and d[node]>d[u]+cost:
                d[node]=d[u]+cost
                heapq.heappush(hq,(d[node],node))
    return d

dist=[[] for _ in range(n)]
for i in range(n):
    dist[i]=dijkstra(i,edges)
ans=0
for a,b,c in ABC:
    if dist[a][b]!=c:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(d, V, M): #d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
    for k in range(V):
        for i in range(V):
            for j in range(V):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
                
    return d
    
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
dist = [[10 ** 5 for i in range(N)] for i in range(N)]

for l in L:
    l[0] -= 1
    l[1] -= 1
      
for i in range(M):
    dist[L[i][0]][L[i][1]] = L[i][2]
    dist[L[i][1]][L[i][0]] = L[i][2]

dist = warshall_floyd(dist, N, M)

res = 0

for i in range(M):
    if dist[L[i][0]][L[i][1]] != L[i][2]:
        res += 1
            
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict


def dd(N, abc, ne_table, start_i):
    used_edge = set()
    pivot = start_i

    kouho = {start_i: (0, 0, True)}  # value: (d, path,kakutei)

    for _ in range(N - 1):

        current_dist, path, kaku = kouho[pivot]
        assert kaku
        edges_i = ne_table[pivot]  # エッジリスト取得
        for i in edges_i:
            a, b, weight = abc[i]
            target = a if a != pivot else b

            if target in kouho:
                tmp_d, tmp_path, kakutei = kouho[target]
                if kakutei:
                    continue
                if current_dist + weight < tmp_d:  # 更新
                    kouho[target] = (current_dist + weight, i, False)
                continue
            kouho[target] = (current_dist + weight, i, False)

        min_kouho = min([(k, d, p) for k, (d, p, kakutei) in kouho.items() if not kakutei], key=lambda q: q[1])
        min_kouho_i = min_kouho[0]
        used_edge.add(min_kouho[2])
        kouho[min_kouho_i] = (kouho[min_kouho_i][0], kouho[min_kouho_i][1], True)
        pivot = min_kouho_i
    return used_edge


def main():
    N, M = [int(a) for a in input().split()]

    def pre(a, b, c):
        return a - 1, b - 1, c

    abc = [
        pre(*[int(a) for a in input().split()])
        for _ in range(M)
    ]

    ne_table = defaultdict(lambda: [])
    for i, (a, b, c) in enumerate(abc):
        ne_table[a].append(i)
        ne_table[b].append(i)

    total_used = set()

    for i in range(N):
        used = dd(N, abc, ne_table, i)
        total_used.update(used)

    print(M - len(total_used))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from collections import *
d=defaultdict(list)
n,m=map(int,input().split())

for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#print(d.keys())

#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})

def DIJKSTRA(point,d):
    cost      = {node:np.inf for node in d.keys()}
    preference= {node:  None for node in d.keys()}#最適路のこと 
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while True:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
   #     del Q[prefnd]
        if len(Q)==0:
            break #全部の点消したら終了
        for pathcost in d[prefnd]:  #次の点とそこまでのコスト
            tempcost=cost[prefnd]+pathcost[1]  #スタートからそこまでのコストを計算
            if tempcost<cost[pathcost[0]]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[pathcost[0]]=tempcost #最小値更新
                preference[pathcost[0]]=prefnd
    return [tuple(sorted([k,v])) for k,v in preference.items() if v!=None]
path=[]
for s in range(1,n+1):
    path.extend(DIJKSTRA(s,d))
print(m-len(set(path)))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n,m=map(int,input().split())
g=[[]for i in range(n)]
s=set()
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1].append((c,b-1))
    g[b-1].append((c,a-1))
    if a>b:
        a,b=b,a
    s.add((a-1,b-1))

def dijkstra(g,st,s):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st,-1))
    while que:
        c,v,past=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        try:
            s.remove((v,past) if v<past else (past,v))
        except:
            pass
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1],v))

for i in range(n):
    dijkstra(g,i,s)
print(len(s))

Submission status: Accepted

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

inf = float("inf")
dist  =  [[inf] * N for _ in range(N)]

for i in range(M):
    dist[inp[i][0]][inp[i][1]] = inp[i][2]
    dist[inp[i][1]][inp[i][0]] = inp[i][2]

for mid in range(N):
    for start in range(N):
        for end in range(N):
            dist[start][end] = min(dist[start][end],
                    dist[start][mid] + dist[mid][end])


ans = 0
for ai,bi,ci in inp:
    if dist[ai][bi] != ci:
        ans += 1

print(ans)

Submission status: Accepted

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

dist=[]
def makedist(start,branch):
    check={start,}
    mind=[10**7 for i in range(n)]
    mind[start]=0
    while len(check)>0:
        now=check.pop()
        for k in branch[now]:
            if k[1]+mind[now]<mind[k[0]]:
                mind[k[0]]=k[1]+mind[now]
                check|={k[0],}
    return mind
for i in range(n):
    dist.append(makedist(i,branch))
ans=0
for k in edge:
    for s in range(n):
        if abs(dist[s][k[0]]-dist[s][k[1]])==k[2]:
            ans+=1
            break
print(m-ans)

Submission status: Accepted

Solution code:
# D 
N,M = map(int, input().split())
a,b,c = [],[],[]
for _ in range(M):
    ai,bi,ci = map(int, input().split())
    a.append(ai-1)
    b.append(bi-1)
    c.append(ci)

dist = [[float('inf')]*N for _ in range(N)]
for i in range(M):
    dist[a[i]][b[i]] = c[i]
    dist[b[i]][a[i]] = c[i]
#print(dist)
for mid in range(N):
    for start in range(N):
        for end in range(N):
            dist[start][end] = min(dist[start][end],
                                   dist[start][mid] + dist[mid][end])

ans = 0
for ai,bi,ci in zip(a,b,c):
    if dist[ai][bi]!=ci:
        ans += 1
print(ans)

Submission status: Accepted

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

import numpy as np
dists = np.ones((n + 1, n + 1)) * (10 ** 6)
edges = []
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
    edges.append((a, b, c))
for i in range(1, n + 1):
    dists[i, i] = 0
for i in range(1, 1 + n):
    dists = np.minimum(dists, dists[i: i + 1] + dists[:, i: i + 1])
cnt = 0
for a, b, c in edges:
    if dists[a, b] < c:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall as fw
n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]

mapm = [[0] * (n) for _ in range(n)]
for i in abc:
    mapm[i[0] - 1][i[1] - 1] = i[2]
    mapm[i[1] - 1][i[0] - 1] = i[2]

f = fw(mapm)
count = 0
for i in abc:
    if f[i[0]-1][i[1]-1] != i[2]:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
dist=[[9999 for _ in range(N)]for _ in range(N)]
cost=[[9999 for _ in range(N)]for _ in range(N)]
for _ in range(M):
    a,b,c=map(int,input().split())
    cost[a-1][b-1]=c
    cost[b-1][a-1]=c
    dist[a-1][b-1]=c
    dist[b-1][a-1]=c

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

ans =0
for i in range(N):
    for j in range(N):
        if i <= j:
            continue
        if cost[i][j] ==9999:
            continue
        if cost[i][j] != dist[i][j]:
            ans +=1

print(ans)

Submission status: Accepted

Solution code:
INFTY = (1<<32)

def floyd(n, d):
    for k in range(n):
        for i in range(n):
            if d[i][k] == INFTY:
                continue
            for j in range(n):
                if d[k][j] == INFTY:
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])


N, M = [int(i) for i in input().split()]

g = [[INFTY] * N for i in range(N)]
for i in range(N):
    g[i][i] = 0

edge_dict = {}
for i in range(M):
    a, b, c = [int(v) for v in input().split()]
    a -= 1
    b -= 1
    edge_dict[(a, b)] = c
    g[a][b] = c
    g[b][a] = c

floyd(N, g)

ans = M
for e, c in edge_dict.items():
    a, b = e
    for s in range(N):
        if g[s][a] + c == g[s][b]:
            ans -= 1
            break

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# 本スクリプトを通じて以下の意味で用いる
# dist: 直接結ぶエッジの長さ
# shortest path (sp): 他のノードを経由しうる最短経路

from heapq import heappush, heappop

HUGE = 10 ** 15

def main():
    n, m = map(int, input().split())
    dist_sets = [{} for i in range(n)]
    for i in range(m):
        a1, b1, c = map(int, input().split())
        dist_sets[a1 - 1][b1 - 1] = c
        dist_sets[b1 - 1][a1 - 1] = c
    shortest_path_mat = [get_shortest_path_dijkstra(i, dist_sets) for i in range(n)]
    res = 0
    for i in range(n):
        for j in dist_sets[i].keys():
            if i > j:
                continue
            if shortest_path_mat[i][j] < dist_sets[i][j]:
                res += 1
    print(res)

def get_shortest_path_dijkstra(root, dist_sets):
    n = len(dist_sets)
    known_sp = [HUGE for i in range(n)]
    known_sp[root] = 0
    determined = [(i == root) for i in range(n)]
    pq = [(known_sp[root], root)]  # 第一要素はキュー追加時の shortest path 候補
    while len(pq) > 0:
        sp_cand, i = heappop(pq)
        determined[i] = True
        if known_sp[i] < sp_cand:
            continue
        for j, dist_ij in dist_sets[i].items():
            if determined[j]:
                continue
            if known_sp[i] + dist_ij < known_sp[j]:
                known_sp[j] = known_sp[i] + dist_ij
                heappush(pq, (known_sp[j], j))
    return known_sp

main()

Submission status: Accepted

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

from heapq import heappush, heappop

HUGE = 10 ** 15

def main():
    n, m = map(int, input().split())
    dist_sets = [{} for i in range(n)]
    for i in range(m):
        a1, b1, c = map(int, input().split())
        dist_sets[a1 - 1][b1 - 1] = c
        dist_sets[b1 - 1][a1 - 1] = c
    shortest_path_mat = [dijkstra(i, dist_sets) for i in range(n)]
    res = 0
    for i in range(n):
        for j in dist_sets[i].keys():
            if i > j:
                continue
            if dist_sets[i][j] != HUGE and shortest_path_mat[i][j] < dist_sets[i][j]:
                res += 1
    print(res)

def dijkstra(root, dist_sets):
    # rootからの距離のリストを返す (TLE本 p302)
    n = len(dist_sets)
    sp = [(0 if i == root else HUGE) for i in range(n)]  # Shortest path from root
    color = [(2 if i == root else 0) for i in range(n)]  # 0: unknown. 1: one path is found. 2: shortest path is found
    pq = []
    heappush(pq, (sp[root], root))
    while len(pq) > 0:
        sp_i_when_queued, i = heappop(pq)
        color[i] = 2
        if sp[i] < sp_i_when_queued:
            continue
        for j in dist_sets[i].keys():
            if color[j] != 2 and sp[i] + dist_sets[i][j] < sp[j]:
                sp[j] = sp[i] + dist_sets[i][j]
                color[j] = 1
                heappush(pq, (sp[j], j))
    return sp

main()

Submission status: Accepted

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

from heapq import heappush, heappop
import numpy as np

HUGE = 10 ** 15

def main():
    n, m = map(int, input().split())
    dist_mat = [[HUGE for j in range(n)] for i in range(n)]
    for i in range(m):
        a1, b1, c = map(int, input().split())
        dist_mat[a1 - 1][b1 - 1] = c
        dist_mat[b1 - 1][a1 - 1] = c
    shortest_path_mat = [dijkstra(i, dist_mat) for i in range(n)]
    res = 0
    for i in range(n):
        for j in range(i + 1, n):
            if dist_mat[i][j] != HUGE and shortest_path_mat[i][j] < dist_mat[i][j]:
                res += 1
    print(res)

def dijkstra(root, dist_mat):
    # rootからの距離のリストを返す (TLE本 p302)
    n = len(dist_mat)
    sp = [(0 if i == root else HUGE) for i in range(n)]  # Shortest path from root
    color = [(2 if i == root else 0) for i in range(n)]  # 0: unknown. 1: one path is found. 2: shortest path is found
    pq = []
    heappush(pq, (sp[root], root))
    while len(pq) > 0:
        sp_i_when_queued, i = heappop(pq)
        color[i] = 2
        if sp[i] < sp_i_when_queued:
            continue
        for j in range(n):  # Use adjacent list for speedup
            if dist_mat[i][j] == HUGE:
                continue
            if color[j] != 2 and sp[i] + dist_mat[i][j] < sp[j]:
                sp[j] = sp[i] + dist_mat[i][j]
                color[j] = 1
                heappush(pq, (sp[j], j))
    return sp

main()

Submission status: Accepted

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

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

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