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: Runtime Error

Solution code:

INF = 10**6 + 1

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

a_l=[]
b_l=[]
c_l=[]

for i in range(M):
    a,b,c=map(int,raw_input().split())
    a_l.append(a-1)
    b_l.append(b-1)
    c_l.append(c-1)
    

d = [[INF for j in range(N)] for i in range(N)]

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

    

for i in range(M):
    d[a_l[i]][b_l[i]] = min(c_l[i],d[a_l[i]][b_l[i]])
    d[b_l[i]][a_l[i]] = min(c_l[i],d[b_l[i]][a_l[i]])


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

for i in range(M):
    flag=False
    for j in range(N):
        for k in range(N):
            if d[j][k]==d[j][a[i]]+d[b[i]][k]:
                flag=True
    if flag:
        ans-=1
print ans

Submission status: Runtime Error

Solution code:
INF = 10**6 + 1

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

a_l=[]
b_l=[]
c_l=[]

for i in range(M):
    a,b,c=map(int,raw_input().split())
    a_l.append(a-1)
    b_l.append(b-1)
    c_l.append(c-1)
    

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

for i in range(N):
    for j in range(N):
        if i==j:
            d[i][j].append(0)
        else:
            d[i][j].append(INF)
    

for i in range(M):
    d[a_l[i]][b_l[i]] = min(c_l[i],d[a_l[i]][b_l[i]])
    d[b_l[i]][a_l[i]] = min(c_l[i],d[b_l[i]][a_l[i]])


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

for i in range(M):
    flag=False
    for j in range(N):
        for k in range(N):
            if d[j][k]==d[j][a[i]]+d[b[i]][k]:
                flag=True
    if flag:
        ans-=1
print ans

Submission status: Runtime Error

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

r=lambda n:range(n)
l=[[inf if i!=j else 0 for j in r(n)] for i in r(n)]
a,b,c=[None]*n,[None]*n,[None]*n

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

for k in r(n):
  for i in r(n):
    for j in r(n):
      l[i][j]=min(l[i][j],l[i][k]+l[k][j])

ans=m
for i in r(m):
  f=False
  for j in r(n):
    if l[j][a[i]]+c[i]==l[j][b[i]]:
      f=True
  if f:ans-=1
print(ans)

Submission status: Runtime Error

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

r=lambda n:range(n)
l=[[inf if i!=j else 0 for j in r(n)] for i in r(n)]
a,b,c=[None]*n,[None]*n,[None]*n

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

for k in r(n):
  for i in r(n):
    for j in r(n):
      l[i][j]=min(l[i][j],l[i][k]+l[k][j])

ans=m
for i in r(m):
  f=False
  for j in r(n):
    if l[j][a[i]]+c[i]==l[j][b[i]]:
      f=True
  if f:ans-=1
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
inf=float("inf")
r=lambda n:range(n)

l=[[inf if i!=j else 0 for j in r(n)] for i in r(n)]
a,b,c=[None]*n,[None]*n,[None]*n

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

for k in r(n):
  for i in r(n):
    for j in r(n):
      l[i][j]=min(l[i][j],l[i][k]+l[k][j])

ans=m
for i in r(m):
  f=False
  for j in r(n):
    if l[j][a[i]-1]+c[i]==l[j][b[i]-1]:
      f=True
  if f:ans-=1
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import product as p
n,m=map(int,input().split())
inf=float("inf")
r=lambda n:range(n)

l=[[inf if i!=j else 0 for j in r(n)] for i in r(n)]
a,b,c=[None]*n,[None]*n,[None]*n

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

for k,i,j in p(*[r(n)]*3):
  l[i][j]=min(l[i][j],l[i][k]+l[k][j])

ans=m
for i in r(m):
  f=False
  for j in r(n):
    if l[j][a[i]-1]+c[i]==l[j][b[i]-1]:
      f=True
  if f:ans-=1
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import product as p
n,m=map(int,input().split())
inf=float("inf")
r=lambda n:range(n)

l=[[inf if i!=j else 0 for j in range(n)] for i in r(n)]
a,b,c=[None]*n,[None]*n,[None]*n

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

for k,i,j in p(*[r(n)]*3):
  l[i][j]=min(l[i][j],l[i][k]+l[k][j])

ans=m
for i in r(m):
  f=False
  for j in r(n):
    if l[j][a[i]-1]+c[i]==l[j][b[i]-1]:
      f=True
      break
  if f:ans-=1
print(ans)

Submission status: Runtime Error

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

def main():
    
    n,m=list(map(int,input().split()))
    a=[0 for _ in range(n)]
    b=[0 for _ in range(n)]
    c=[0 for _ in range(n)]
    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: Runtime Error

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

def main():
    
    n,m=list(map(int,input().split()))
    a=[0 for _ in range(n)]
    b=[0 for _ in range(n)]
    c=[0 for _ in range(n)]
    d=[[INF for i in range(n)] for i in range(n)]
    for i in range(n):
        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: Runtime Error

Solution code:
from itertools import product as prod

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

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

numset = set(range(n))
def dist(i, j, gr=gr):
    tmp_d = float("inf")
    if i == j:
        return 0
    for (node, d) in gr[i]:
        if node == j:
            tmp_d = d
    # gr_cp = [[(n, d) for (n, d) in g if n != i] for g in gr]
    numset.remove(i)
    routes = [d + dist(n, j, gr=gr) for (n, d) in gr[i] if n in numset]

    return min(routes + [tmp_d])

ans = 0
for i in range(n):
    for (j, d) in gr[i]:
        if dist(i, j) < d:
            ans += 1

print(ans // 2)

Submission status: Runtime Error

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

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

#print(dist)

for i in range(M):
	cost.append(list(map(int, input().split())))

#print(cost)

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

print(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] + dis[k][j])

ans = 0
for a, b, c in cost:
	if dist[a-1][b-1] < c:
		ans += 1
		
print(ans)

Submission status: Runtime Error

Solution code:
import numpy
import random

def used(dp,u,v,w):
    n=len(dp)
    for i in range(n):
        for j in range(i+1,n):
            if dp[i][j]==dp[i][u]+w+dp[v][j] or dp[i][j]==dp[i][v]+w+dp[u][j]:
                return True
    return False

while 1:
    try:
        n,m=map(int,input().split())
        es=[]
        for _ in range(m):
            u,v,w=map(int,input().split())
            es.append((u-1,v-1,w))
    except: break

    random.shuffle(es)

    dp=[[float('inf')]*n for _ in range(n)]
    for i in range(n):
        dp[i][i]=0
    for u,v,w in es:
        dp[u][v]=dp[v][u]=w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
    print(sum(int(not used(dp,u,v,w)) for u,v,w in es))