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())
Adj = [[10 ** 7 for j in range(N)] for i in range(N)]
for i in range(N):
  Adj[i][i] = 0
Edge = []
for m in range(M):
  a, b, c = map(int, input().split())
  Adj[a - 1][b - 1] = c
  Adj[b - 1][a - 1] = c
  Edge.append([a - 1, b - 1, c])
for i in range(N):
  for j in range(N):
    for k in range(N):
      Adj[j][k] = min(Adj[j][i] + Adj[i][k], Adj[j][k])
Unused = [1 for m in range(M)]
for i, e in enumerate(Edge):
  for s in range(N):
    if Adj[s][e[0]] + e[2] == Adj[s][e[1]]:
      Unused[i] = 0
print(sum(Unused))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
Adj = [[] for n in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  Adj[a - 1].append([b - 1, c, i])
  Adj[b - 1].append([a - 1, c, i])
E = [1 for m in range(M + 1)]
def Dijkstra(s):
  L = [[10 ** 7, n, 0] for n in range(N)]
  L[s] = [0, 0, 0]
  Q = []
  heapq.heappush(Q, [0, s, M])
  while Q:
    q = heapq.heappop(Q)
    if L[q[1]][2] == 0:
      L[q[1]][2] = 1
      E[q[2]] = 0
      for adj in Adj[q[1]]:
        if q[0] + adj[1] < L[adj[0]][0]:
          L[adj[0]][0] = q[0] + adj[1]
          heapq.heappush(Q, [q[0] + adj[1], adj[0], adj[2]])
for n in range(N):
  Dijkstra(n)
print(sum(E))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
G = [[] for n in range(N)]
for m in range(M):
  a, b, c = map(int, input().split())
  G[a - 1].append([b - 1, c, m])
  G[b - 1].append([a - 1, c, m])
E = [1 for m in range(M + 1)]
def Dijkstra(s):
  L = [[10 ** 7, n, 0] for n in range(N)]
  L[s] = [0, 0, 0]
  Q = []
  heapq.heappush(Q, [0, s, M])
  while Q:
    q = heapq.heappop(Q)
    if L[q[1]][2] == 0:
      L[q[1]][2] = 1
      E[q[2]] = 0
      for adj in G[q[1]]:
        if q[0] + adj[1] < L[adj[0]][0]:
          L[adj[0]][0] = q[0] + adj[1]
          heapq.heappush(Q, [q[0] + adj[1], adj[0], adj[2]])
for n in range(N):
  Dijkstra(n)
print(sum(E))

Submission status: Accepted

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

class MakeGraph:
    
    # 隣接行列もしくは隣接リストの初期化
    # node_num：ノード数
    # isMat：隣接行列(True) / 隣接リスト(False)
    def __init__(self, node_num:int, isMat:bool) -> None:
        self.n = node_num
        self.isMat = isMat

        # 隣接行列の初期化
        if self.isMat:
            INF = float("inf")
            self.graph = [[INF for _ in range(self.n)] for _ in range(self.n)]
    
        # 隣接リストの初期化
        else:
            self.graph = [[] for _ in range(self.n)]

    # エッジの追加
    # frm, to：起点ノード, 終点ノード
    # dist：frm→toへのコスト
    def add_undr_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        self.graph[to][frm] = dist
        
    def add_drct_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        
    def add_undr_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))
        self.graph[to].append((dist, frm))
        
    def add_drct_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))

                
    # 完成したグラフを取り出す
    def get_graph(self) -> list:
        return self.graph

# 入力    
N,M = map(int, input().split())
ABC = []
for i in range(M):
    ABC.append(tuple(map(int, input().split())))
    
#file = open("sampleABC051D.txt", "r")
#
#N,M = map(int, file.readline().split())
#ABC = []
#for i in range(M):
#    ABC.append(tuple(map(int, file.readline().split())))
    
graphMaker = MakeGraph(N,False)
add_edge = graphMaker.add_undr_edge_lst

for a,b,c in ABC:
    add_edge(a-1, b-1, c)

graph = graphMaker.get_graph()

dist = []
for i in range(N):
    dist_temp = dijkstra(graph, N, i)
    dist.append(dist_temp)
    
ans = 0
for i in range(N):
    for cost, node in graph[i]:
        if dist[i][node] != cost:
            ans += 1
            
            
print(ans//2)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
d = [[float("inf")] * n for _ in range(n)]
d_org = [[float("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
	d_org[a - 1][b - 1] = c
	d_org[b - 1][a - 1] = c

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]

ans = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		if d_org[i][j] < float("inf") and d_org[i][j] > d[i][j]:
			ans += 1

print(ans)

Submission status: Accepted

Solution code:
class MakeGraph:
    
    # 隣接行列もしくは隣接リストの初期化
    # node_num：ノード数
    # isMat：隣接行列(True) / 隣接リスト(False)
    def __init__(self, node_num:int, isMat:bool) -> None:
        self.n = node_num
        self.isMat = isMat

        # 隣接行列の初期化
        if self.isMat:
            INF = float("inf")
            self.graph = [[INF for _ in range(self.n)] for _ in range(self.n)]
    
        # 隣接リストの初期化
        else:
            self.graph = [[] for _ in range(self.n)]

    # エッジの追加
    # frm, to：起点ノード, 終点ノード
    # dist：frm→toへのコスト
    def add_undr_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        self.graph[to][frm] = dist
        
    def add_drct_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        
    def add_undr_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))
        self.graph[to].append((dist, frm))
        
    def add_drct_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))

                
    # 完成したグラフを取り出す
    def get_graph(self) -> list:
        return self.graph
    
N,M = map(int, input().split())
ABC = []
for i in range(M):
    ABC.append(tuple(map(int, input().split())))
    
graphMaker = MakeGraph(N,True)
distMaker = MakeGraph(N,True)
add_edge = graphMaker.add_undr_edge_mat
add_edge2 = distMaker.add_undr_edge_mat
for a,b,c in ABC:
    add_edge(a-1, b-1, c)
    add_edge2(a-1, b-1, c)

graph = graphMaker.get_graph()
dist = distMaker.get_graph()

# WF
for i in range(N):
    dist[i][i] = 0

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(N):
    for j in range(N):
        if graph[i][j] != float("inf") and graph[i][j] != dist[i][j]:
            ans += 1

  
print(ans//2)

Submission status: Accepted

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

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

e = [[100000 for i in range(n)] for j in range(n)]

for i in range(n):
    e[i][i] = 0
for i in d:
    e[i[0]][i[1]] = i[2]
    e[i[1]][i[0]] = i[2]

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

ans = 0

for i in d:
    if e[i[0]][i[1]] != i[2]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
dist_given = {}
dist = [[1000]*(n+1) for _ in range(n+1)]
for i in range(1, n+1): dist[i][i] = 0
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dist[a][b] = c
    dist[b][a] = c
    dist_given[tuple(sorted([a, b]))] = c

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])
# print(dist)
ans = 0
for i in range(1, n):
    for j in range(i+1, n+1):
        if (i, j) in dist_given.keys() and dist[i][j] < dist_given[(i, j)]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
N, M = map(int, input().split())
a = [0]*M
b = [0]*M
c = [0]*M
for m in range(M):
    a[m], b[m], c[m] = map(int, input().split())
    if a[m] > b[m]:
        a[m], b[m] = b[m], a[m]
        assert(a[m] < b[m])
    a[m] -= 1
    b[m] -= 1
#
temp = [10**7] * N
d = [temp[:] for i in range(N)]
 
for i in range(N):
    for j in range(i, N):
        assert(i<=j)
        if i == j:
            d[i][j] = 0
        else:
            for m in range(M):
                if a[m]==i and b[m]==j:
                    d[i][j] = c[m]
 
for k in range(N):
    for i in range(N):
        for j in range(i, N):
            assert(i<=j)
            if i <= k:
                dik = d[i][k]
            else:
                dik = d[k][i]
            if k <= j:
                dkj = d[k][j]
            else:
                dkj = d[j][k]
            if d[i][j] > dik + dkj:
                d[i][j] = dik + dkj
 
ans = 0
for m in range(M):
    if c[m] > d[a[m]][b[m]]:
        ans += 1
    elif c[m] < d[a[m]][b[m]]:
        raise Exception()
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

INF = 2147483647
G = [[] for i in range(n)]
MST = [[-1 for j in range(n)] for i in range(n)]


def dijkstra(s):
    check, dist = [0 for i in range(n)], [INF for i in range(n)]
    dist[s], pq = 0, []
    heapq.heappush(pq, (0, s))
    p = [-1 for i in range(n)]

    while len(pq) != 0:
        u = heapq.heappop(pq)
        check[u[1]] = 2

        if dist[u[1]] < u[0]:
            continue

        if p[u[1]] != -1:
            MST[p[u[1]]][u[1]], MST[u[1]][p[u[1]]] = 1, 1
        for v in G[u[1]]:
            if check[v[0]] != 2:
                if dist[u[1]] + v[1] < dist[v[0]]:
                    dist[v[0]], check[v[0]] = dist[u[1]] + v[1], 1
                    p[v[0]] = u[1]
                    heapq.heappush(pq, (dist[v[0]], v[0]))


def main():
    for i in range(m):
        a, b, c = map(int, input().split())
        G[a-1].append((b-1, c))
        G[b-1].append((a-1, c))
        MST[a-1][b-1] = MST[b-1][a-1] = INF

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

    cnt = 0
    for i in range(n):
        for j in range(n):
            if MST[i][j] == INF:
                cnt += 1

    print(cnt//2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
g = [[] for _ in range(0,N+1)]
e = []
for i in range(0,M):
    a,b,t = map(int,input().split())
    g[a].append((b,t))
    g[b].append((a,t))
    e.append((a,b,t))

d = [[float("inf") for _ in range(0,N+1)]for _ in range(0,N+1)]
def dijkstra(s):
    d[s][s] = 0
    queue = deque([[s,g[s]]])
    while queue:
        start,edge = queue.popleft()
        for to,cost in edge:
            if d[s][to] > d[s][start] + cost:
                d[s][to] = d[s][start] + cost
                queue.append((to,g[to]))
for i in range(1,N+1):
    dijkstra(i)

ans = [1 for _ in range(0,M)]
for i in range(1,N+1):
    j = 0
    for a,b,t in e:
        if d[i][a] + t == d[i][b]:
            ans[j] = 0
        j += 1
print(sum(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
D = [[float("inf")]*(N+1) for i in range(N+1)]
E = []
for i in range(M):
    a, b, c = map(int, input().split())
    E.append([a, b, c])
    D[a][b] = D[b][a] = c
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
cnt = 0
for e in E:
    a, b, c = e
    if D[a][b] != c:
        cnt += 1
print(cnt)

Submission status: Accepted

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

N, M = map(int, input().split())
a = [0]*M
b = [0]*M
c = [0]*M
for m in range(M):
    a[m], b[m], c[m] = map(int, input().split())
    if a[m] > b[m]:
        a[m], b[m] = b[m], a[m]
        assert(a[m] < b[m])
    a[m] -= 1
    b[m] -= 1
#
temp = [10**7] * N
d = [temp[:] for i in range(N)]

for i in range(N):
    for j in range(i, N):
        assert(i<=j)
        if i == j:
            d[i][j] = 0
        else:
            for m in range(M):
                if a[m]==i and b[m]==j:
                    d[i][j] = c[m]

for k in range(N):
    for i in range(N):
        for j in range(i, N):
            assert(i<=j)
            if i <= k:
                dik = d[i][k]
            else:
                dik = d[k][i]
            if k <= j:
                dkj = d[k][j]
            else:
                dkj = d[j][k]
            if d[i][j] > dik + dkj:
                d[i][j] = dik + dkj

ans = 0
for m in range(M):
    if c[m] > d[a[m]][b[m]]:
        ans += 1
    elif c[m] < d[a[m]][b[m]]:
        raise Exception()
print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 9

n, m = map(int, input().split())
a = [[INF] * n for _ in range(n)]
e = [None] * m
for i in range(n): a[i][i] = 0
for i in range(m):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    e[i] = (u, v, w)
    a[u][v] = w
    a[v][u] = w
for k in range(n):
    for i in range(n):
        for j in range(n):
            a[i][j] = min(a[i][j], a[i][k] + a[k][j])
c = 0
for u, v, w in e:
    if a[u][v] != w: c += 1
print(c)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(m)]
c,ans = [[float("inf") for i in range(n+1)] for i in range(n+1)],0
for i in range(n+1): c[i][i] = 0
for i,j,k in x: c[i][j],c[j][i] = k,k
for k in range(1,n+1):
	for i in range(1,n+1):
		for j in range(1,n+1): c[i][j] = min(c[i][k]+c[k][j],c[i][j])
for i,j,k in x:
	if c[i][j] != k: ans += 1
print(ans)

Submission status: Accepted

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

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]

not_change = set()
for i in range(N):
    for j in range(N):
        if G[i][j] == G2[i][j]:
            not_change.add((i, j))

print(M - len(not_change)//2)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = [[10**5 for _ in range(N)] for _ in range(N)]
E = []
Ans = 0

for i 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 k in range(N):
    for i in range(N):
        for j in range(N):
            if i==j:
                G[i][j] = 0
            else:
                G[i][j] = min(G[i][j], G[i][k]+G[k][j])


for i in range(M):
    a,b,c = E[i]
    for j in range(N):
        if G[j][b] == G[j][a] + c:
           break
    else:
        Ans += 1

print(Ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
INF = float('inf')
d = [[INF for i in range(N)] for j in range(N)]
es = []
for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    d[a][b] = d[b][a] = c
    es.append((a,b,c))

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

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
d = [[float('inf') for j in range(N)] for i in range(N)]
es = {}
for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    d[a][b] = d[b][a] = c
    es[(a,b)] = es[(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 (a,b),c in es.items():
    if c != d[a][b]:
        ans += 1
print(ans // 2)

Submission status: Accepted

Solution code:
def bellman_ford(num, start):
    dist = [float("inf") for i in range(num)]
    path = [float("inf") for i in range(num)]
    dist[start] = 0
    while 1:
        update = False
        for i, j, k in adj:
            if dist[j-1] > dist[i-1] + k:
                dist[j-1] = dist[i-1] + k
                path[j-1] = [i, j]
                update = True
            if dist[i-1] > dist[j-1] + k:
                dist[i-1] = dist[j-1] + k
                path[i-1] = [j, i]
                update = True
        if not update:
            break
    return path

n, m = map(int, input().split(" "))
adj = []
all_path = []
for i in range(m):
    a, b, c = map(int, input().split(" "))
    adj.append([a, b, c])
    all_path.append([a, b])
    all_path.append([b, a])
for i in range(n):
    p = bellman_ford(n, i)
    for j in range(n):
        if p[j] in all_path:
            m -= 1
            all_path.remove(p[j])
            all_path.remove([p[j][1], p[j][0]])
print(m)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return map(int, input().split())
N, M = inpl()
INF = float("inf")

G = [[INF]*(N) for _ in range(N)]
E = []
for _ in range(M):
    a, b, c = inpl()
    G[a-1][b-1] = c
    G[b-1][a-1] = c
    E.append([a-1, b-1, c])

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(sum([G[a][b] < c for a, b, c in E]))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
d=[[float('inf') for x in range(N)] for y in range(N)]
for i in range(N):
  d[i][i]=0
ans=[]
for i in range(M):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=c
  d[b-1][a-1]=c
  ans.append([a-1,b-1,c])

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]

res=0
for a,b,c in ans:
  if d[a][b]!=c:
    res+=1

print(res)

Submission status: Accepted

Solution code:
INF = float('inf')
ans,d,g = 0,[],[]
n,m = map(int,input().split())
for i in range(n):
	d.append([])
	for j in range(n):
		d[i].append(0 if i == j else INF)

for i in range(m):
	a,b,c = map(int,input().split())
	a -= 1
	b -= 1
	g.append([a,b,c])
	d[a][b],d[b][a] = c,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])

for e in g:
	if d[e[0]][e[1]] != e[2]:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
INF=100000000000


def floyd_warshall(dist):
    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])

n,m = map(int,input().split())
dist=[[INF]*n for i in range(n)]
edges=[]

for i in range(m):
    ai,bi,ci=map(int,input().split())
    edges.append(tuple([ai-1,bi-1,ci]))
    dist[ai-1][bi-1]=ci
    dist[bi-1][ai-1]=ci

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

floyd_warshall(dist)

#print(dist)
ans = m
for edge in edges:
    ai,bi,ci=edge
    flag = 0
    for s in range(n):
        if dist[s][ai]+ci == dist[s][bi]:
            flag+=1

    if flag > 0:
        ans-=1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
map1=[[float('inf')]*n for i in range(n)]
map2=[[float('inf')]*n for i in range(n)]
for i in range(n):
    map1[i][i]=0
    map2[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    map1[a-1][b-1]=c
    map1[b-1][a-1]=c
    map2[a-1][b-1]=c
    map2[b-1][a-1]=c

#Warshall_Floyd法
for k in range(n):
    for i in range(n):
        for j in range(n):
            map1[i][j]=min(map1[i][j],map1[i][k]+map1[k][j])
ans=0
for i in range(n):
    for j in range(n):
        if map2[i][j]!=float('inf') and map2[i][j]!=map1[i][j]:
            ans+=1
print(int(ans/2))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = [[float('inf')]*N for i in range(N)]
graph2 = [[float('inf')]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
    graph2[a-1][b-1] = c
    graph2[b-1][a-1] = c

edge = set()

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == graph2[i][j]:
                edge.add(tuple([i, j]))


print(M - len(edge)//2)

Submission status: Accepted

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

dp=[ [ float("inf") for i in range(N+1) ]  for j in range(N+1)]
for i in range(N+1): dp[i][i]=0
l={}

for i in range(M):
	A,B,C=map(int, raw_input().split())
	dp[A][B]=C
	dp[B][A]=C
	l[(A,B)]=C


for k in range(1,N+1):
	for x in range(1,N+1):
		for y in range(1,N+1):
			dp[x][y]=min(dp[x][y], dp[x][k]+dp[k][y])


ans=0
for i  in l.items():
	x=i[0][0]
	y=i[0][1]
	c=i[1]
	if dp[x][y]==c:
		pass
	else:
		ans+=1
print ans

Submission status: Accepted

Solution code:
def d_Candidates_of_No_Shortest_Paths(N, M, E):
    # 初期化
    dist = [[float('inf') for j in range(N)] for i in range(N)]
    for i in range(N):
        dist[i][i] = 0
    # 構築
    for a, b, c in E:
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = 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])
    ans = M  # 最短経路として使われない辺の数
    for a, b, c in E:
        a -= 1
        b -= 1
        for s in range(N):
            if dist[s][a] + c == dist[s][b]:
                # 条件を満たした辺は使われる。1引く
                ans -= 1
                break
    return ans

N,M = [int(i) for i in input().split()]
E = [[int(i) for i in input().split()] for j in range(M)]
print(d_Candidates_of_No_Shortest_Paths(N, M, E))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a, b, c = [0] * M, [0] * M, [0] * M
INF = int(1e9)
d = [[INF] * N for i in range(N)]
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    d[a[i]][b[i]] = c[i]
    d[b[i]][a[i]] = c[i]

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

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

ans = 0
for i in range(M):
    isUsed = False
    for j in range(N):
        for k in range(j, N):
            # print("d[%d][%d]: %d, d[%d][%d] + c[%d] + d[%d][%d]: %d" % (j, k, d[j][k], j, a[i], i, b[i], k, d[j][a[i]] + c[i] + d[b[i]][k]))
            isUsed = isUsed \
                or d[j][k] == d[j][a[i]] + c[i] + d[b[i]][k] \
                or d[j][k] == d[j][b[i]] + c[i] + d[a[i]][k]
    if not isUsed:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j] = min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

N,M=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(M)]
A=[[float("inf") for j in range(N)] for i in range(N)]#最短距離map
for i in range(N):
  A[i][i]=0
for i in range(M):
  A[abc[i][0]-1][abc[i][1]-1]=abc[i][2]
  A[abc[i][1]-1][abc[i][0]-1]=abc[i][2]
dist = Warshall_Floyd(A,N)
ans = 0
for j in range(M):
  u = abc[j][0] - 1
  v = abc[j][1] - 1
  for s in range(N):
    if dist[s][u] + abc[j][2] == dist[s][v]:
      ans += 1
      break
print(M - ans)

Submission status: Accepted

Solution code:
def Warshall_Floyd(edges,N):
  import copy
  d=copy.deepcopy(edges)
  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

inf=float("inf")
N,M=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(M)]
A=[[inf for j in range(N)] for i in range(N)]#最短距離map
for i in range(N):
  A[i][i]=0
for i in range(M):
  A[abc[i][0]-1][abc[i][1]-1]=abc[i][2]
  A[abc[i][1]-1][abc[i][0]-1]=abc[i][2]
Ans=Warshall_Floyd(A,N)
ans=0
for j in range(M):
  u=abc[j][0]-1
  v=abc[j][1]-1
  for s in range(N):
    if Ans[s][u]+abc[j][2]==Ans[s][v]:
      ans+=1
      break
print(M-ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [[float('inf')] * n for i in range(n)]
d = [[float('inf')] * n for i in range(n)]
nv = [[j for j in range(n)] for i in range(n)]

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

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]
                nv[i][j] = nv[i][k]
edges = set((i, j) for i in range(n) for j in range(i + 1, n) if g[i][j] < float('inf'))

for i in range(n):
    for j in range(i + 1, n):
        k = nv[i][j]
        t = min((i, k), (k, i))
        if t in edges:
            edges.remove(t)
print(len(edges))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path as sp
n, m = map(int, input().split())
G = [[0 for i in range(n)] for i in range(n)]
edges = []
for i in range(m):
    a,b,c = map(int, input().split())
    G[a-1][b-1] = c
    edges.append((a-1,b-1,c))
dist = sp(G, method='D', directed=False)

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

Submission status: Accepted

Solution code:
n,m=[int(x) for x in input().split()]
path=[]
d=[[float("inf") for _ in [0]*n] for _2 in [0]*n]
for _ in [0]*m:
    a,b,c=[int(x) for x in input().split()]
    path.append((a-1,b-1,c))
    d[a-1][b-1]=d[b-1][a-1]=c
from itertools import product
for k,i,j in product(range(n),range(n),range(n)):
    if d[i][j]>d[i][k]+d[k][j]:
        d[i][j]=d[i][k]+d[k][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())
INF = 10 ** 9
adjs = [[INF] * N for _ in range(N)]
for i in range(N):
    adjs[i][i] = 0
edges = []
for _ in range(M):
    a, b, c = map(lambda x: int(x) - 1, input().split())
    c += 1
    edges.append((a, b, c))
    adjs[a][b] = adjs[b][a] = c

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

print(sum(adjs[a][b] != c and adjs[b][a] != c for a, b, c in edges))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

    for m in range(N):
        for s in range(N):
            for e in range(N):
                if dp[s][m] != INF and dp[m][e] != INF:
                    dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e])

    ans = 0
    for a, b, c in edges:
        ans += dp[a][b] != c
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

    for m in range(N):
        for s in range(N):
            for e in range(N):
                if dp[s][m] != INF and dp[m][e] != INF:
                    dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e])

    ans = 0
    for a, b, c in edges:
        for s in range(N):
            if dp[s][a] + c == dp[s][b]:
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
inf = 10000000000
mat = [[inf if j!=i else 0 for j in range(i+1)] for i in range(n)]
abcs = [list(map(int, input().split())) for _ in range(m)]
for a, b, c in abcs:
    i, j = max(a, b)-1, min(a, b)-1
    mat[i][j] = min(mat[i][j], c)

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

print(sum(1 for a, b, c in abcs if c > mat[max(a, b)-1][min(a, b)-1]))

Submission status: Accepted

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

INF = 100000000
D = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for a, b, c in X:
    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 a, b, c in X:
    if D[a][b] != c:
        ans += 1
print ans