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: Wrong Answer

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
dist=defaultdict(int)
branch=[]
for k in range(m):
    branch.append(tuple(map(int,input().split())))
branch.sort(key=lambda x:x[2],reverse=True)
ans=0
for k in range(m):
    check=branch.pop()
    a,b,c=check[0],check[1],check[2]
    if dist[(a,b)]==0:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            elif dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            elif dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
            elif dist[(a,i)]!=0 and dist[(a,i)]!=0:
                if dist[(a,i)]+c<dist[(b,i)]:
                    dist[(b,i)]=dist[(a,i)]+c
                    dist[(i,b)]=dist[(a,i)]+c
                if dist[(b,i)]+c<dist[(a,i)]:
                    dist[(a,i)]=c+dist[(b,i)]
                    dist[(i,a)]=c+dist[(b,i)]
    elif dist[(a,b)]<c:
        ans+=1
    elif dist[(a,b)]>c:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            elif dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            elif dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
            elif dist[(a,i)]!=0 and dist[(a,i)]!=0:
                if dist[(a,i)]+c<dist[(b,i)]:
                    dist[(b,i)]=dist[(a,i)]+c
                    dist[(i,b)]=dist[(a,i)]+c
                if dist[(b,i)]+c<dist[(a,i)]:
                    dist[(a,i)]=c+dist[(b,i)]
                    dist[(i,a)]=c+dist[(b,i)]
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
dist=defaultdict(int)
branch=[]
for k in range(m):
    branch.append(tuple(map(int,input().split())))
branch.sort(key=lambda x:x[2],reverse=True)
ans=0
for k in range(m):
    check=branch.pop()
    a,b,c=check[0],check[1],check[2]
    if dist[(a,b)]==0:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            if dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            if dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
            if dist[(a,i)]!=0 and dist[(a,i)]!=0:
                if dist[(a,i)]+c<dist[(b,i)]:
                    dist[(b,i)]=dist[(a,i)]+c
                    dist[(i,b)]=dist[(a,i)]+c
                if dist[(b,i)]+c<dist[(a,i)]:
                    dist[(a,i)]=c+dist[(b,i)]
                    dist[(i,a)]=c+dist[(b,i)]
    elif dist[(a,b)]<c:
        ans+=1
    elif dist[(a,b)]>c:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            if dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            if dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
            if dist[(a,i)]!=0 and dist[(a,i)]!=0:
                if dist[(a,i)]+c<dist[(b,i)]:
                    dist[(b,i)]=dist[(a,i)]+c
                    dist[(i,b)]=dist[(a,i)]+c
                if dist[(b,i)]+c<dist[(a,i)]:
                    dist[(a,i)]=c+dist[(b,i)]
                    dist[(i,a)]=c+dist[(b,i)]
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
dist=defaultdict(int)
branch=[]
for k in range(m):
    branch.append(tuple(map(int,input().split())))
branch.sort(key=lambda x:x[2],reverse=True)
ans=0
for k in range(m):
    check=branch.pop()
    a,b,c=check[0],check[1],check[2]
    if dist[(a,b)]==0:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            if dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            if dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
    elif dist[(a,b)]<c:
        ans+=1
    elif dist[(a,b)]>c:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            if dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            if dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
            if dist[(a,i)]!=0 and dist[(a,i)]!=0:
                if dist[(a,i)]+c<dist[(b,i)]:
                    dist[(b,i)]=dist[(a,i)]+c
                    dist[(i,b)]=dist[(a,i)]+c
                if dist[(b,i)]+c<dist[(a,i)]:
                    dist[(a,i)]=c+dist[(b,i)]
                    dist[(i,a)]=c+dist[(b,i)]
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
dist=defaultdict(int)
branch=[]
for k in range(m):
    branch.append(tuple(map(int,input().split())))
branch.sort(key=lambda x:x[2],reverse=True)
ans=0
for k in range(m):
    check=branch.pop()
    a,b,c=check[0],check[1],check[2]
    if dist[(a,b)]==0:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            if dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            if dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
    elif dist[(a,b)]<c:
        ans+=1
    elif dist[(a,b)]>c:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            if dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            if dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
from collections import defaultdict
dist=defaultdict(int)
branch=[]
for k in range(m):
    branch.append(tuple(map(int,input().split())))
branch.sort(key=lambda x:x[2],reverse=True)
ans=0
for k in range(m):
    check=branch.pop()
    a,b,c=check[0],check[1],check[2]
    if dist[(a,b)]==0:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            if dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            if dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
    elif dist[(a,b)]<=c:
        ans+=1
    elif dist[(a,b)]>c:
        dist[(a,b)]=c
        dist[(b,a)]=c
        for i in range(1,1+n):
            if i==a or i==b:continue
            if dist[(a,i)]!=0 and dist[(b,i)]==0:
                dist[(b,i)]=c+dist[(a,i)]
                dist[(i,b)]=c+dist[(a,i)]
            if dist[(b,i)]!=0 and dist[(a,i)]==0:
                dist[(a,i)]=c+dist[(b,i)]
                dist[(i,a)]=c+dist[(b,i)]
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

Nmax = 100
Mmax = 1000
cmax = 1000
inf = Nmax * cmax * 100

(N,M) = map(int,input().split())
A = np.empty((M,3),dtype=np.int)
for i in range(M):
    (a,b,c) = map(int,input().split())
    if a < b:
        (a,b) = (b,a)
    A[i] = (a-1,b-1,c)

A=np.array(sorted(A,key=lambda x: (x[0],x[1],x[2])),dtype=np.int)

distance = np.ones((N,N),dtype=np.int)*inf
for i in range(N):
    distance[i,i] = 0

for i in range(M):
    (a,b,c) = A[i]
    if c <= distance[a,b]:
        distance[a,b] = distance[b,a] = c
        for m in range(a+1):
            for n in range(m):
                distance[m,n] = min(distance[m,n],
                                    distance[m,a]+distance[n,b]+c,
                                    distance[m,b]+distance[b,n]+c)
                distance[n,m] = distance[m,n]
        
ans = 0
for i in range(M):
    (a,b,c) = A[i]
    if c > distance[a,b]:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
d=[[9999 for _ in range(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

ans=0

for i in range(N):
    for j in range(N):
        if j <= i:
            continue
        for k in range(N):
            if i ==k or j ==k:
                continue
            if d[i][j]==9999:
                continue
            if d[i][j]>d[i][k]+d[k][j]:
                ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
d=[[9999 for _ in range(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

ans=0
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 d[i][j]==9999:
                continue
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]
                d[j][i]=d[i][k]+d[k][j]
                ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
d=[[9999 for _ in range(N)]for _ in range(N)]

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

ans=0
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 d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]
                d[j][i]=d[i][k]+d[k][j]
                ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
d=[[9999 for _ in range(N)]for _ in range(N)]

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

ans=0
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
            print(d[i][j],d[i][k]+d[k][j])
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]
                d[j][i]=d[i][k]+d[k][j]
                ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]
wf = [[[2000 for _ in range(N + 10)] for _ in range(N + 10)] for _ in range(N + 10)]
for i in range(N):
    for j in range(N):
        wf[i][j][j] = 0
for item in edge:
    a, b, c = item
    wf[0][a][b] = c
    wf[0][b][a] = c

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

ans = 0
for item in edge:
    a, b, c = item
    if c > wf[N][a - 1][b - 1]:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

l=[list(map(int,input().split())) for _ in range(m)]
d=[[float("inf")]*n for _ in range(n)]

for a,b,c in l:
  d[a-1][b-1]=c
  d[b-1][a-1]=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=m
for i,(a,b,c) in enumerate(l):
  f=False
  for s in range(n):
    if d[s][a-1]+c==d[s][b-1]:
      f=True
  if f:ans-=1

print(ans)

Submission status: Wrong Answer

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

l=[list(map(int,input().split())) for _ in range(m)]
d=[[float("inf")]*n for _ in range(n)]

for a,b,c in l:
  d[a-1][b-1]=c
  d[b-1][a-1]=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])

used=[False]*m
for s in range(n):
  for i,(a,b,c) in enumerate(l):
    if d[s][a-1]+c==d[s][b-1] or d[s][b-1]+c==d[s][a-1]:
      used[i]=True

print(m-sum(used))

Submission status: Wrong Answer

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

l=[list(map(int,input().split())) for _ in range(m)]
d=[[float("inf")]*n for _ in range(n)]

for a,b,c in l:
  d[a-1][b-1]=c
  d[b-1][a-1]=c

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

used=[False]*m
for s in range(n):
  for i,(a,b,c) in enumerate(l):
    if d[s][a-1]+c==d[s][b-1] or d[s][b-1]+c==d[s][a-1]:
      used[i]=True

print(m-sum(used))

Submission status: Wrong Answer

Solution code:
import heapq


def dist(N, a, b, w_mat):
    ds = [1000 * 1000 + 1 for _ in range(N + 1)]
    q = [(0, a)]
    ds[a] = 0
    heapq.heapify(q)
    # print("\n".join([str(r) for r in w_mat]))
    while len(q):
        # print(q)
        # print(a, b, ds[1:])
        w, i = heapq.heappop(q)
        if i == b:
            break
        for ni, wi in [(ni, wi) for ni, wi in enumerate(w_mat[i]) if wi > 0]:
            if ds[ni] > w + wi:
                ds[ni] = w + wi
                heapq.heappush(q, (w + wi, ni))
    # print("\n".join([str(r) for r in d_mat]))
    # print(a, b, ds[1:])
    return ds[b]


def solve(N, M, ABCs):
    # print(N, ",", M, ",", ABCs)
    d_mat = [[0 for __ in range(N + 1)] for _ in range(N + 1)]
    w_mat = [[-1 for __ in range(N + 1)] for _ in range(N + 1)]

    for i in range(N + 1):
        w_mat[i][i] = 0

    for a, b, c in ABCs:
        w_mat[a][b] = c
        w_mat[b][a] = c

    for s in range(1, N + 1):
        for e in range(s + 1, N + 1):
            d = dist(N, s, e, w_mat)
            d_mat[s][e] = d
            d_mat[e][s] = d

    ans = 0
    for a, b, c in ABCs:
        if all(d_mat[s][e] != d_mat[s][a] + c + d_mat[b][e]
               for s in range(1, N + 1)
               for e in range(s + 1, N + 1)):
            ans += 1

    #    print("\n".join([str(r) for r in d_mat]))
    return ans



if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABCs))

Submission status: Wrong Answer

Solution code:
import heapq

def dist(N, a, b, w_mat):
    ds = [10**10 for _ in range(N + 1)]
    q = [(0, a)]
    ds[a] = 0
    heapq.heapify(q)
    # print("\n".join([str(r) for r in w_mat]))
    while len(q):
        # print(q)
        # print(a, b, ds[1:])
        w, i = heapq.heappop(q)
        for ni, wi in [(ni, wi) for ni, wi in enumerate(w_mat[i]) if wi > 0]:
            if ds[ni] > w + wi:
                ds[ni] = w + wi
                heapq.heappush(q, (w + wi, ni))
    # print("\n".join([str(r) for r in d_mat]))
    # print(a, b, ds[1:])
    return ds[b]


def solve(N, M, ABCs):
    # print(N, ",", M, ",", ABCs)
    d_mat = [[0] * (N + 1) for _ in range(N + 1)]

    w_mat = [[-1] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        w_mat[i][i] = 0

    for a, b, c in ABCs:
        w_mat[a][b] = c
        w_mat[b][a] = c

    for s in range(1, N + 1):
        for e in range(s + 1, N + 1):
            d = dist(N, s, e, w_mat)
            d_mat[s][e] = d
            d_mat[e][s] = d

    ans = len(ABCs)
    for a, b, c in ABCs:
        if any(d_mat[s][e] == d_mat[s][a] + c + d_mat[b][e]
               for s in range(1, N + 1)
               for e in range(s + 1, N + 1)):
            ans -= 1

    #    print("\n".join([str(r) for r in d_mat]))
    return ans


# assert (solve(3, 3, [(1, 2, 1), (1, 3, 1), (2, 3, 3)]) == 1)
# assert (solve(3, 2, [(1, 2, 1), (2, 3, 1)]) == 0)

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABCs))

Submission status: Wrong Answer

Solution code:
import heapq


def dist(N, a, b, w_mat):
    d_mat = [[10**9] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        d_mat[i][i] = 0
    q = [(0, a)]
    heapq.heapify(q)
    # print("\n".join([str(r) for r in w_mat]))
    s = set()
    while len(q):
        # print(q)
        w, i = heapq.heappop(q)
        s.add(i)
        for ni, wi in [(ni, wi) for ni, wi in enumerate(w_mat[i])
                       if wi > 0 and ni not in s]:
            if d_mat[a][ni] > w + wi:
                d_mat[a][ni] = w + wi
                d_mat[ni][a] = w + wi
                heapq.heappush(q, (w + wi, ni))
    # print("\n".join([str(r) for r in d_mat]))
    # print("")
    return d_mat[a][b]


def solve(N, M, ABCs):
    # print(N, ",", M, ",", ABCs)
    d_mat = [[0] * (N + 1) for _ in range(N + 1)]

    w_mat = [[-1] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        w_mat[i][i] = 0

    for a, b, c in ABCs:
        w_mat[a][b] = c
        w_mat[b][a] = c

    for s in range(1, N + 1):
        for e in range(s + 1, N + 1):
            d = dist(N, s, e, w_mat)
            d_mat[s][e] = d
            d_mat[e][s] = d

    ans = len(ABCs)
    for a, b, c in ABCs:
        if any(d_mat[s][e] == d_mat[s][a] + c + d_mat[b][e]
               for s in range(1, N + 1)
               for e in range(s + 1, N + 1)):
            ans -= 1

    #    print("\n".join([str(r) for r in d_mat]))
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABCs))

Submission status: Wrong Answer

Solution code:
import heapq


def dist(N, a, b, w_mat):
    d_mat = [[100] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        d_mat[i][i] = 0
    q = [(0, a)]
    heapq.heapify(q)
    # print("\n".join([str(r) for r in w_mat]))
    s = set()
    while len(q):
        # print(q)
        w, i = heapq.heappop(q)
        s.add(i)
        for ni, wi in [(ni, wi) for ni, wi in enumerate(w_mat[i])
                       if wi > 0 and ni not in s]:
            if d_mat[a][ni] > w + wi:
                d_mat[a][ni] = w + wi
                d_mat[ni][a] = w + wi
                heapq.heappush(q, (w + wi, ni))
    # print("\n".join([str(r) for r in d_mat]))
    # print("")
    return d_mat[a][b]


def solve(N, M, ABCs):
    # print(N, ",", M, ",", ABCs)
    d_mat = [[0] * (N + 1) for _ in range(N + 1)]

    w_mat = [[-1] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        w_mat[i][i] = 0

    for a, b, c in ABCs:
        w_mat[a][b] = c
        w_mat[b][a] = c

    for s in range(1, N + 1):
        for e in range(s + 1, N + 1):
            d = dist(N, s, e, w_mat)
            d_mat[s][e] = d
            d_mat[e][s] = d

    ans = len(ABCs)
    for a, b, c in ABCs:
        if any(d_mat[s][e] == d_mat[s][a] + c + d_mat[b][e]
               for s in range(1, N + 1)
               for e in range(s + 1, N + 1)):
            ans -= 1

    #    print("\n".join([str(r) for r in d_mat]))
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABCs))

Submission status: Wrong Answer

Solution code:
import heapq


def dist(N, a, b, w_mat):
    d_mat = [[100] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        d_mat[i][i] = 0
    q = [(0, a)]
    heapq.heapify(q)
    # print("\n".join([str(r) for r in w_mat]))
    s = set()
    while len(q):
        # print(q)
        w, i = heapq.heappop(q)
        s.add(i)
        for ni, wi in [(ni, wi) for ni, wi in enumerate(w_mat[i])
                       if wi > 0 and ni not in s]:
            if d_mat[a][ni] > w + wi:
                d_mat[a][ni] = w + wi
                d_mat[ni][a] = w + wi
                heapq.heappush(q, (w + wi, ni))
    # print("\n".join([str(r) for r in d_mat]))
    # print("")
    return d_mat[a][b]


def solve(N, M, ABCs):
    # print(N, ",", M, ",", ABCs)
    d_mat = [[0] * (N + 1) for _ in range(N + 1)]

    w_mat = [[-1] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        w_mat[i][i] = 0

    for a, b, c in ABCs:
        w_mat[a][b] = c
        w_mat[b][a] = c

    for s in range(1, N + 1):
        for e in range(s + 1, N + 1):
            d = dist(N, s, e, w_mat)
            d_mat[s][e] = d
            d_mat[e][s] = d

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

    #    print("\n".join([str(r) for r in d_mat]))
    return ans



if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABCs))

Submission status: Wrong Answer

Solution code:
import heapq


def dist(N, a, b, w_mat):
    d_mat = [[100] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        d_mat[i][i] = 0
    q = [(0, a)]
    heapq.heapify(q)
    # print("\n".join([str(r) for r in w_mat]))
    s = set()
    while len(q):
        # print(q)
        w, i = heapq.heappop(q)
        s.add(i)
        for ni, wi in [(ni, wi) for ni, wi in enumerate(w_mat[i])
                       if wi > 0 and ni not in s]:
            if d_mat[a][ni] > w + wi:
                d_mat[a][ni] = w + wi
                d_mat[ni][a] = w + wi
                heapq.heappush(q, (w + wi, ni))
    # print("\n".join([str(r) for r in d_mat]))
    # print("")
    return d_mat[a][b]


def solve(N, M, ABCs):
    # print(N, ",", M, ",", ABCs)

    w_mat = [[-1] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        w_mat[i][i] = 0
    for a, b, c in ABCs:
        w_mat[a][b] = c
        w_mat[b][a] = c
    # print("\n".join([str(r) for r in w_mat]))
    ans = 0
    for a, b, c in ABCs:
        d = dist(N, a, b, w_mat)
        if d != w_mat[a][b]:
            ans += 1
    return ans


# assert (solve(3, 3, [(1, 2, 1), (1, 3, 1), (2, 3, 3)]) == 1)
# assert (solve(3, 2, [(1, 2, 1), (2, 3, 1)]) == 0)

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABCs))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
COSTLIST=[list(map(int,input().split())) for i in range(M)]#aからbへのcostがx

USED=[0]*M
Distance=[[float("inf") for i in range(N+1)] for j in range(N+1)]

COSTLIST.sort(key=lambda x:x[2])

for j in range(M):
    a,b,c=COSTLIST[j]
    if Distance[a][b]>=c:
        Distance[a][b]=Distance[b][a]=c
        for i in range(1,N+1):
            if Distance[i][a]>Distance[i][b]+c:
                Distance[i][a]=Distance[a][i]=Distance[i][b]+c


            if Distance[i][b]>Distance[i][a]+c:
                Distance[i][b]=Distance[b][i]=Distance[i][a]+c
        USED[j]=1

print(USED.count(0))

Submission status: Wrong Answer

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

d = [[INF for _ in range(N)] for _ in range(N)]
abc = []

for _ in range(M):
  a, b, c = map(int, input().strip().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][j], d[i][k]+d[k][j])

ans = M
for a, b, c in abc:
  shortest = False
  for j in range(N):
    if d[j][a]+c == d[j][b]:
      shortest = True
  if shortest:
    ans -= 1
print(ans)

Submission status: Wrong Answer

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

ans = 0
for k in range(N):
    flg = 0
    for i in range(N):
        for j in range(N):
            if G[i][j] > G[i][k] + G[k][j]:
                flg = 1
                G[i][j] = G[k][j]
    ans += flg

print(M - ans)

Submission status: Wrong Answer

Solution code:
V, E = [int(_) for _ in input().split()]
G = {}
for i in range(V):
    G[i] = {}
    G[i][i] = 0

for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  # 0を始点とする場合
    t -= 1  # 0を始点とする場合
    G[s][t] = c
    G[t][s] = c

INF = 10**10

edges_used = set()
for i in range(V):
    D = [INF] * V
    D[i] = 0  # iを始点とする場合
    used = [False] * V
    used[i] = True
    prev = {}
    while True:
        for j in G[i].keys():
            if D[i] + G[i][j] < D[j]:
                D[j] = D[i] + G[i][j]
                prev[j] = i
        v = -1
        for j in range(V):
            if not used[j] and (v == -1 or D[j] < D[v]):
                v = j
        if v == -1:
            break
        else:
            used[v] = True
            i = v
    for key, value in prev.items():
        if key > value:
            key, value = value, key
        edges_used.add((key + 1, value + 1))

print(edges_used)
print(E - len(edges_used))

Submission status: Wrong Answer

Solution code:
V, E = [int(_) for _ in input().split()]
G = {}
for i in range(V):
    G[i] = {}
    G[i][i] = 0

for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  # 0を始点とする場合
    t -= 1  # 0を始点とする場合
    G[s][t] = c
    G[t][s] = c

INF = 10**10

D = [INF] * V
D[0] = 0  # 0を始点とする場合
edges_used = set()
for i in range(V):
    used = [False] * V
    used[i] = True
    prev = {}
    while True:
        for j in G[i].keys():
            if D[i] + G[i][j] < D[j]:
                D[j] = D[i] + G[i][j]
                prev[j] = i
        v = -1
        for j in range(V):
            if not used[j] and (v == -1 or D[j] < D[v]):
                v = j
        if v == -1:
            break
        else:
            used[v] = True
            i = v
    for key, value in prev.items():
        if key > value:
            key, value = value, key
        edges_used.add(key * V + value)

print(E - len(edges_used))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
# union find?
uf = list(range(N)) # uf[i] = 1 if vertice i is connected to 1
a_arr = []
b_arr = []
c_arr = []
for _ in range(M):
    a, b, c = map(int, input().split())
    a_arr.append(min(a, b) - 1)
    b_arr.append(max(a, b) - 1)
    c_arr.append(c)
c_arr = sorted(c_arr)

ans = 0
for m in range(M):
    if uf[a_arr[m]] == uf[b_arr[m]]:
        ans += 1
    else:
        for n in range(N):
            if uf[n] == uf[b_arr[m]]:
                uf[n] = uf[a_arr[m]]
# print(uf)
print(ans)

Submission status: Wrong Answer

Solution code:
V, E = [int(_) for _ in input().split()]
G = {}
for i in range(V):
    G[i] = {}
    G[i][i] = 0

for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  # 0を始点とする場合
    t -= 1  # 0を始点とする場合
    G[s][t] = c
    G[t][s] = c

INF = 10**10

D = [INF] * V
D[0] = 0  # 0を始点とする場合
used = [True] + [False] * (V - 1)
i = 0
prev = {}
while True:
    for j in G[i].keys():
        if D[i] + G[i][j] < D[j]:
            D[j] = D[i] + G[i][j]
            prev[j] = i
    v = -1
    for j in range(V):
        if not used[j] and (v == -1 or D[j] < D[v]):
            v = j
    if v == -1:
        break
    else:
        used[v] = True
        i = v

print(E - len(prev))

Submission status: Wrong Answer

Solution code:
N, M = [int(_) for _ in input().split()]
ABC = sorted([[int(_) for _ in input().split()]
              for _ in range(M)], key=lambda x: x[2])
G = [[10000] * N for _ in range(N)]
ans = 0
for a, b, c in ABC:
    a -= 1
    b -= 1
    m = min(G[a][i] + G[b][i] for i in range(N))
    if m < c:
        ans += 1
    else:
        m = c
    G[a][b], G[b][a] = m, m
print(ans)

Submission status: Wrong Answer

Solution code:
ans = 0
n,m = map(int,input().split())
dis = [[float('inf') for i in range(n)] for j in range(n)] #各点距離を最初∞に設定
abt = []
for i in range(m):
    abt.append(list(map(int,input().split()))) #入力
for a,b,t in abt:
    dis[a-1][b-1] = t #頂点aからbへの距離がt
    dis[b-1][a-1] = t # 逆も同様
for i in range(n):
    for j in range(n):
        for k in range(n):
            dis[i][j] = min(dis[k][j], dis[k][i] + dis[i][j])
for a,b,t in abt:
    if t > dis[a-1][b-1]:
        ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
ans = 0
n,m = map(int,input().split())
dis = [[float('inf') for i in range(n)] for j in range(n)] #各点距離を最初∞に設定
abt = []
for i in range(m):
    abt.append(list(map(int,input().split()))) #入力
for a,b,t in abt:
    dis[a-1][b-1] = t #頂点aからbへの距離がt
    dis[b-1][a-1] = t # 逆も同様
for i in range(n):
    for j in range(n):
        for k in range(n):
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
for a,b,t in abt:
    if t > dis[a-1][b-1]:
        ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d



V, E=map(int,input().strip().split(' '))
inf=10**9
cost=[[inf]*V for i in range(V)]
edge=[]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
    edge.append([fr-1,to-1])
    
d=[]
for i in range(V):
    d.append(dijkstra(i))

cand=E
for i in range(E):
    fl=False
    for j in range(V):
        for k in range(V):
            if d[j][edge[i][0]]==cost[edge[i][0]][edge[i][1]]+d[k][edge[i][1]]:
                cand-=1
                fl=True
                break
        if fl:
            break

print(cand)