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, raw_input().split())
EDGES = {}
d = [[float('inf') for j in range(N)] for i in range(N)]
for i in range(M):
  a,b,c = map(int, raw_input().split())
  a -= 1
  b -= 1
  EDGES[(min(a,b),max(a,b))] = c
  d[a][b] = c
  d[b][a] = 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]

unused = 0
for e,v in EDGES.items():
  if v != d[e[0]][e[1]]:
    unused += 1
print unused

Submission status: Accepted

Solution code:
N,M = map(int, raw_input().split())
EDGES = {}
d = [[float('inf') for j in range(N)] for i in range(N)]
for i in range(M):
  a,b,c = map(int, raw_input().split())
  a -= 1
  b -= 1
  EDGES[(min(a,b),max(a,b))] = c
  d[a][b] = c
  d[b][a] = 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]

unused = 0
for j in range(N):
  for i in range(j):
    if((i,j) in EDGES and EDGES[(i,j)] != d[i][j]):
      unused += 1
print unused

Submission status: Accepted

Solution code:
import numpy as np
INF = 10**10
N, M = map(int, raw_input().split())
G = [map(int, raw_input().split()) for i in range(M)]
d = np.full((N+1, N+1), INF)
for i in range(N+1):
    d[i, i] = 0
for u, v, c in G:
    d[u, v] = d[v, u] = c
for u in range(N+1):
    for s in range(N+1):
        for t in range(N+1):
            d[s, t] = d[t, s] = min(d[s, t], d[s, u] + d[u, t])
ans = 0
for u, v, c in G:
    if c > d[u, v]:
        ans += 1
print ans

Submission status: Accepted

Solution code:
import sys

inf = 1<<60

def solve():
    N, M = map(int, sys.stdin.readline().split())

    cost = [[inf]*N for i in range(N)]

    for mi in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1
        cost[a][b] = cost[b][a] = c

    dist = [[0]*N for i in range(N)]

    for i in range(N):
        for j in range(i + 1, N):
            dist[i][j] = dist[j][i] = cost[i][j]

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

    ans = 0

    for i in range(N):
        for j in range(i + 1, N):
            if cost[i][j] < inf and cost[i][j] != dist[i][j]:
                ans += 1

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
inf = 10**6
abc = []
d = [[inf]*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
	abc.append((a-1,b-1,c))

for k in range(N):
	for i in range(N):
		for j in range(N):
			d[i][j] = min(d[i][k]+d[k][j], d[i][j])
ans = 0
for i in range(M):
	a, b, c = abc[i]
	if d[a][b] < inf and d[a][b] < c:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
INF=10**10

def main():
    
    n,m=list(map(int,input().split()))
    a=[0 for _ in range(m)]
    b=[0 for _ in range(m)]
    c=[0 for _ in range(m)]
    d=[[INF for i in range(n)] for i in range(n)]
    for i in range(m):
        a[i],b[i],c[i]=list(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])
                d[j][i]=d[i][j]
    ans=0
    for j in range(m):
        temp=1
        for i in range(n):
            if d[i][b[j]]==d[i][a[j]]+c[j]:
                temp=0
                break
        ans+=temp
    print(ans)
    
    
    
        
        
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n, m = map(int, input().split())
links = [set() for _ in range(n)]
link_list = []
for _ in range(m):
    s, t, c = map(int, input().split())
    s, t = s - 1, t - 1
    link_list.append((s, t, c))
    links[s].add((c, t))
    links[t].add((c, s))

result = 0
for s, t, limit in link_list:
    queue = [(0, s)]
    visited = set()
    while queue:
        c, v = heappop(queue)
        if c >= limit:
            break
        if v == t:
            result += 1
            break
        if v in visited:
            continue
        visited.add(v)
        for nc, nv in links[v]:
            if nv in visited:
                continue
            if v == s and nv == t:
                continue
            heappush(queue, (c + nc, nv))
print(result)

Submission status: Accepted

Solution code:
import heapq as hq

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

costs = dict()
adj = [list() for _ in range(N)]

e = lambda a,b: (a,b) if a<=b else (b,a)

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

max_dist = sum(costs.values())+1
used_edge = set()

for s in range(N):
  q = [(0,s)]
  dist = [max_dist]*N
  dist[s] = 0

  while q:
    c, u = hq.heappop(q)
    if c > dist[u]:
      continue

    for v in adj[u]:
      ee = e(u,v)
      if dist[v] > dist[u] + costs[ee]:
        dist[v] = dist[u] + costs[ee]
        hq.heappush(q, (dist[v], v))

  for t in adj[s]:
    if costs[e(s,t)] == dist[t]:
      used_edge.add(e(s,t))

print(len(costs.keys()-used_edge))

Submission status: Accepted

Solution code:
import copy
from itertools import product as prod

n, m = [int(x) for x in input().split()]

wait = [[float("inf") for _ in range(n)] for _ in range(n)]
for i in range(n):
    wait[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    wait[a-1][b-1] = c
    wait[b-1][a-1] = c

dist = copy.deepcopy(wait)
for k, i, j in prod(range(n), range(n), range(n)):
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    dist[j][i] = min(dist[j][i], dist[j][k] + dist[k][i])

ans = 0
for i, j in prod(range(n), range(n)):
    if not wait[i][j] == float("inf") and dist[i][j] < wait[i][j]:
        ans += 1

print(ans // 2)

Submission status: Accepted

Solution code:
INF = 123456789

def main():
    n,m = map(int,input().split())

    d = [ [INF for i in range(n)] for j in range(n) ]
    for i in range(n):
        d[i][i] = 0

    a = [0 for _ in range(m)]
    b = [0 for _ in range(m)]
    c = [0 for _ in range(m)]
    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]] = min(d[a[i]][b[i]], c[i])
        d[b[i]][a[i]] = min(d[b[i]][a[i]], c[i])

    # Warshall-Floyd
    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):
        found = 1
        for j in range(n):
            if d[j][a[i]] + c[i] == d[j][b[i]]:
                found = 0
                break
        ans += found
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

INF = 123456789

def main():
    n,m = map(int,input().split())

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

    used = set()
    for i in range(n):
        d = [INF for _ in range(n)]
        par = [-1 for _ in range(n)]

        # dijkstra
        que = queue.PriorityQueue()
        d[i] = 0
        que.put((0,i))
        while not que.empty():
            p = que.get()
            v = p[1]
            if d[v] < p[0]:
                continue
            for (to,cost) in G[v]:
                if d[to] > d[v]+cost:
                    d[to] = d[v]+cost
                    par[to] = v
                    que.put((d[to],to))

        for j in range(n):
            if i != j:
                a,b = j,par[j]
                if a>b:
                    a,b = b,a
                used.add((a,b))

    print(m - len(used))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int,raw_input().split())
INF = 10 ** 8
cost = [[INF for j in xrange(N+10)] for i in xrange(N+10)]
E = [[INF for j in xrange(N+10)] for i in xrange(N+10)]
for _ in xrange(M):
    a,b,c = map(int,raw_input().split())
    a -= 1
    b -= 1
    cost[a][b] = c
    cost[b][a] = c
    E[a][b] = c
    E[b][a] = c
for v in xrange(N):
    cost[v][v] = 0
for k in xrange(N):
    for i in xrange(N):
        for j in xrange(N):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
ans = 0
for a in xrange(N):
    for b in xrange(a+1,N):
        if E[a][b] == INF:
            continue
        OK = False
        for s in xrange(N):
            for t in xrange(s+1,N):
                if cost[s][a] + E[a][b] + cost[b][t] == cost[s][t]:
                    OK = True
            if OK:
                break
        if not OK:
            ans += 1
print ans

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sys

def main(argv):
    line = sys.stdin.readline().rstrip("\n")

    while line:
        n, m = line.split()
        n = int(n)
        m = int(m)

        edges = []
        path = [[-1 for i in xrange(n)] for i in xrange(n)]
        distance = [[1001 for i in xrange(n)] for i in xrange(n)]
        for i in xrange(m):
            a, b, c = raw_input().split()
            a = int(a) - 1
            b = int(b) - 1
            c = int(c)
            distance[a][b] = c
            distance[b][a] = c
            edges.append((a,b))

        for i in xrange(n):
            distance[i][i] = 0

        for k in xrange(n):
            for i in xrange(n):
                for j in xrange(n):
                    candidate = distance[i][k] + distance[k][j]
                    if candidate < distance[i][j]:
                        distance[i][j] = candidate
                        path[i][j] = k

        counter = 0
        for (x, y) in edges:
            if path[x][y] != -1:
                counter += 1
        print counter

        line = sys.stdin.readline().rstrip("\n")

if __name__ == "__main__":
    main(sys.argv)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# problem D
MAX = 9999 # c_i <= 1000 より.

n, m = map(int, input().split())
cost = []

dist = [[MAX] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
    
for _ in range(m):
    cost.append(list(map(int, input().split())))

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

# Warshall-Floyd Algorithm
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 a, b, c in cost:
    if dist[a-1][b-1] < c:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
a = [0] * m
b = [0] * m
c = [0] * m

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

d = [[float('inf') for i in range(n)] for j in range(n)]

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

for i in range(m):
    d[a[i]][b[i]] = c[i]
    d[b[i]][a[i]] = c[i]

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

ans = m
for i in range(m):
    f = False
    for j in range(n):
        if d[j][b[i]] == c[i] + d[j][a[i]]:
            f = True

    if f:
        ans -= 1

print(ans)

Submission status: Accepted

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

dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
  dist[i][i] = 0
for _ in range(m):
  abc.append(list(map(int,input().split())))

for a,b,c in abc:
  dist[a-1][b-1] = c
  dist[b-1][a-1] = 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 = 0
for a,b,c in abc:
    if dist[a-1][b-1]  < c:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
INF = 1000000

N, M = map(int, raw_input().split(" "))

dat = [[INF for _ in xrange(N)] for _ in xrange(N)]
isMinimal = [[True for _ in xrange(N)] for _ in xrange(N)]

for i in xrange(N):
    dat[i][i] = 0

a = [0 for _ in xrange(M)]
b = [0 for _ in xrange(M)]
c = [0 for _ in xrange(M)]
for i in xrange(M):
    a[i], b[i], c[i] = map(int, raw_input().split(" "))
    a[i] -= 1
    b[i] -= 1
    dat[a[i]][b[i]] = c[i]
    dat[b[i]][a[i]] = c[i]

for k in xrange(N):
    for i in xrange(N):
        for j in xrange(N):
            if dat[i][j] > dat[i][k] + dat[k][j]:
                dat[i][j] = dat[i][k] + dat[k][j]
                isMinimal[i][j] = False

res = 0
for i in xrange(M):
        res += 0 if isMinimal[a[i]][b[i]] else 1

print res

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()

class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v,d])
        self.e[v].append([u,d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s, t):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            if u == t:
                return d[t]
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return None


def main():
    n,m = LI()
    dk = Dijkstra()
    t = []
    r = 0
    for _ in range(m):
        a,b,c = LI()
        dk.add(a,b,c)
        t.append([a,b,c])
    for a,b,c in t:
        d = dk.search(a,b)
        if d < c:
            r += 1
    return r


print(main())

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra

my_input = lambda : map(int, input().split(" "))

N, M = my_input()
dist = 100 * 1000 * (np.ones([N, N]) - np.eye(N)).astype(int)

edges = []
for i in range(M):
    a, b, c = my_input()
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
    edges.append((a, b, c))

dist = dijkstra(dist, directed=False)
print(len([e for e in edges if e[2] != dist[e[0]-1][e[1]-1]]))

Submission status: Accepted

Solution code:

# D - Candidates of No Shortest Paths

MAXI = 999999999

# 入力
N, M = map(int, input().split())
cost = [[-1 for i in range(N)] for j in range(N)]

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

# iからjへの最短距離を表すテーブルの初期化
dist = [[MAXI for i in range(N)] for j in range(N)]

# iからjへの辺があったら、最短距離をその辺のコストで初期化
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif cost[i][j] != -1:
            dist[i][j] = cost[i][j]
            dist[j][i] = dist[i][j]

# ワーシャルフロイドで各i,j間の最短距離を求めておく
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(i, N):
        # i,j間に辺があって、そこを通らない方が近道になるとき、全ての最短経路でその辺は使われない
        if cost[i][j] != -1 and cost[i][j] != dist[i][j]:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# D - Candidates of No Shortest Paths

MAXI = 999999999

# 入力
N, M = map(int, input().split())
cost = [[-1 for i in range(N)] for j in range(N)]

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

# iからjへの最短距離を表すテーブルの初期化
dist = [[MAXI for i in range(N)] for j in range(N)]

# iからjへの辺があったら、最短距離をその辺のコストで初期化
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif cost[i][j] != -1:
            dist[i][j] = cost[i][j]
            dist[j][i] = dist[i][j]

# ワーシャルフロイドで各i,j間の最短距離を求めておく
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# print(dist)

ans = 0

for i in range(N):
    for j in range(i, N):
        if cost[i][j] != -1: # 各辺がどの異なる２点の最短経路にも含まれないかを調べる
            flag = 1

            for k in range(N):
                for l in range(k + 1, N):
                    # 一つでも最短経路に含まれていたならブレイク
                    if dist[k][l] == dist[k][i] + cost[i][j] + dist[j][l]:
                        flag = 0
                        break
            
            # 全ての異なる２点間の最短経路に含まれていなかったら+1カウント
            ans += flag


print(ans)

Submission status: Accepted

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

dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0

for _ in range(m):
    abc.append(list(map(int, input().split())))

for a, b, c in abc:
    dist[a-1][b-1] = c
    dist[b-1][a-1] = 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 = 0
for a, b, c in abc:
    if dist[a-1][b-1] < c:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
abc = []
dis = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
    abc.append(list(map(int, input().split())))

for a, b, c in abc:
    dis[a-1][b-1] = c
    dis[b-1][a-1] = c

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

count = 0
for a, b, c in abc:
    if c > dis[a-1][b-1]:
        count += 1

print(count)

Submission status: Accepted

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

import collections
import itertools


INF = 10 ** 8
UNDEF = -1


def floyd_warshall(num_vs, edges):
    n = num_vs
    dist = [[INF for _ in range(n)] for _ in range(n)]
    for u in range(n):
        dist[u][u] = 0
    for (u, v), c in edges.items():
        dist[u][v] = c
    for t, u, v in itertools.product(range(n), repeat=3):
        nl = dist[u][t] + dist[t][v]
        if nl < dist[u][v]:
            dist[u][v] = nl
    return dist


def main():
    n, m = (int(x) for x in input().split())
    edges = dict()
    used = dict()
    for _ in range(m):
        a, b, c = (int(x) for x in input().split())
        a -= 1
        b -= 1
        edges[(a, b)] = c
        edges[(b, a)] = c
        used[(a, b)] = False
    dist = floyd_warshall(n, edges)
    ans = 0
    for (u, v), c in edges.items():
        if u < v:
            if dist[u][v] != c:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import collections
import itertools


INF = 10 ** 8
UNDEF = -1


def floyd_warshall_undirected(num_vs, edges):
    n = num_vs
    dist = [[INF for _ in range(n)] for _ in range(n)]
    pred = [[UNDEF for _ in range(n)] for _ in range(n)]
    for u in range(n):
        dist[u][u] = 0
    for (u, v), c in edges.items():
        dist[u][v] = c
        dist[v][u] = c
        pred[u][v] = u
        pred[v][u] = v
    for t, u, v in itertools.product(range(n), repeat=3):
        nl = dist[u][t] + dist[t][v]
        if nl < dist[u][v]:
            dist[u][v] = nl
            pred[u][v] = pred[t][v]
    return dist, pred


def construct_shortest_path(s, t, pred):
    path = collections.deque()
    path.appendleft(t)
    while t != s:
        t = pred[s][t]
        path.appendleft(t)
    return list(path)


def main():
    n, m = (int(x) for x in input().split())
    edges = dict()
    used = dict()
    for _ in range(m):
        a, b, c = (int(x) for x in input().split())
        a -= 1
        b -= 1
        a, b = min(a, b), max(a, b)
        edges[(a, b)] = c
        used[(a, b)] = False
    _, pred = floyd_warshall_undirected(n, edges)
    for s in range(n):
        for t in range(s + 1, n):
            path = construct_shortest_path(s, t, pred)
            for u, v in zip(path[:-1], path[1:]):
                u, v = min(u, v), max(u, v)
                used[(u, v)] = True
    ans = m - sum(used.values())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [0 for i in range(M)]
B = [0 for i in range(M)]
C = [0 for i in range(M)]
dist = [[float('inf') for j in range(N)] for i in range(N)]
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]

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

count = 0
for i in range(M):
	if dist[A[i]-1][B[i]-1] < C[i]:
		count = count+1

print(count)

Submission status: Accepted

Solution code:
[N, M] = [ int(i) for i in raw_input().split() ]
INF = int(1e9)
G = [ [ 0 if i==j else INF for j in xrange(N)] for i in xrange(N) ]
E = []

for _ in xrange(M):
	[a,b,c] = [ int(i) for i in raw_input().split() ]
	G[a-1][b-1] = c
	G[b-1][a-1] = c
	E.append([a-1,b-1,c])
	
for k in xrange(N):
	for i in xrange(N):
		for j in xrange(N):
			G[i][j] = min(G[i][j], G[i][k] + G[k][j])

res = 0
for [i,j,c] in E:
	res += 1 if G[i][j]	< c else 0
	
print res

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
n, m = map(int, raw_input().split())
G = [[] for i in xrange(n)]
E = {}
for i in xrange(m):
    a, b, c = map(int, raw_input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))
    E[a-1, b-1] = E[b-1, a-1] = [c, 0]
def dijkstra(s):
    dist = [10**18]*n
    prev = [-1]*n
    que = [(0, s)]
    dist[s] = 0
    dic = set()
    while que:
        co, v = heappop(que)
        if dist[v] < co:
            continue
        for t, cost in G[v]:
            if co + cost < dist[t]:
                dist[t] = co + cost
                heappush(que, (co+cost, t))
                prev[t] = v
    for i in xrange(n):
        if prev[i] != -1:
            dic.add((i, prev[i]))
    return dic

ans = m
for i in xrange(n):
    dic = dijkstra(i)
    for k in dic:
        e = E[k]
        if e[1] == 0:
            ans -= 1
            e[1] = 1
print ans

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
a=[0]*m;b=[0]*m;c=[0]*m
p=[[10e9 for i in range(n)] for i in range(n)]
for i in range(n):p[i][i]=0
for i in range(m):
    a[i],b[i],c[i]=map(int,raw_input().split())
    a[i]-=1;b[i]-=1
    p[a[i]][b[i]]=p[b[i]][a[i]]=c[i]
for i in range(n):
    for j in range(n):
        for k in range(n):
            p[j][k]=min(p[j][k],p[j][i]+p[i][k])
            p[k][j]=p[j][k]
cnt=0
for i in range(m):
    if p[a[i]][b[i]]<c[i]:cnt+=1
print cnt

Submission status: Accepted

Solution code:
import heapq

def dijkstra(s,g,n):
    d=[float('inf')]*n
    d[s]=0
    pq=[]
    cnt=0
    eused=[False]*m
    visited=[False]*n
    nowe=[-1]*n
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        if d[u]<t:
            continue
        for v,c,e in g[u]:
            if d[u]+c<d[v]:
                if not visited[v]:
                    visited[v]=True
                    eused[e]=True
                    nowe[v]=e
                else:
                    idx=nowe[v]
                    eused[idx]=False
                    eused[e]=True
                    nowe[v]=e
                    #print nowe,eused,idx
                d[v]=d[u]+c
                heapq.heappush(pq,[d[v],v])
    return eused

n,m=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
for i in xrange(m):
    a,b,c=map(int,raw_input().split())
    a-=1;b-=1;
    g[a].append([b,c,i])
    g[b].append([a,c,i])
used_edge=[False]*m
for i in xrange(n):
    tmp=dijkstra(i,g,n)
    for j in xrange(m):
        if (not used_edge[j]) and tmp[j]:
            used_edge[j]=True
ans=0
for i in xrange(m):
    if not used_edge[i]:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = [int(x) for x in raw_input().split()]

d = [[1000000000] * n for i in range(n)]

edges = []
for i in range(m):
    a, b, c = [int(x) for x in raw_input().split()]
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    edges.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 edges:
    if d[a][b] < c:
        ans += 1

print ans

Submission status: Accepted

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

INF = 0x3f3f3f3f
dp = [[INF for i in range(110)] for j in range(110)]
v = [(0,0,0) for i in range(M)]

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

ans = 0
for i in range(M):
	if dp[v[i][0]][v[i][1]] < v[i][2]:
		ans += 1

print(ans)

Submission status: Accepted

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

INF = 100000000

g = [ [INF] * N for _ in range(N) ]

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

t = [ [INF] * N for _ in range(N) ]
for i in range(N):
  for j in range(N):
    t[i][j] = g[i][j]

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

ans = 0
for i in range(N):
  for j in range(i):
    if g[i][j] != INF:
      if t[i][j] != g[i][j]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding=utf-8

import sys
stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().strip()

def main():
    n,m = na()
    g = []
    for i in range(n):
        g.append([99999999]*n)
    for i in range(n):
        g[i][i] = 0
    es = []
    for i in range(m):
        a,b,c = na()
        es.append((a-1,b-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):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    ct = 0
    for e in es:
        if g[e[0]][e[1]] != e[2]:
            ct += 1
    print(ct)
    pass


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    import numpy as np    
    from scipy.sparse import csr_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    omat = csr_matrix((c, (a, b)), shape=(N+1, N+1), dtype=np.int32, directed=False)
    smat = floyd_warshall(omat)
    return ((omat-smat) > 0).sum() // 2


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    print(solve(N, M, a, b, c))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
def warshall_floyd(d,n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if(i!=j):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
def main():

    n,m=map(int, input().split())
    edge = [[] for _ in range(n)]
    d = [[float("inf")]*n for i in range(n)]
    d_1 = [[float("inf")]*n for i in range(n)]
    e_lis = [0]*m
    for i in range(m):
        a,b,c=map(int, input().split())
        d[a-1][b-1]=d[b-1][a-1]=d_1[a-1][b-1]=d_1[b-1][a-1]=c
    res = warshall_floyd(d,n)
    cnt=0
    for i in range(n):
        for j in range(n):
            if(res[i][j]!=d_1[i][j] and d_1[i][j]<10000):
                cnt+=1
    print(cnt//2)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import heapq

def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    used = set()
    for i in range(N):
        H = []
        for b, c in G[i]:
            heapq.heappush(H, (c, i, b))
        todo = set(range(N))
        todo.remove(i)
        D = [10**10] * N
        D[i] = 0
        while H:
            c, a, b = heapq.heappop(H)
            if D[b] < c:
                continue
            D[b] = c
            if a < b:
                used.add((a, b))
            else:
                used.add((b, a))
            todo.remove(b)
            for d, cc in G[b]:
                if d in todo:
                    heapq.heappush(H, (c + cc, b, d))
    return M - len(used)

print(main())