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

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 = [[0]*N for i in range(N)]

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

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

count = 0
for i in range(M):
    if d[a[i]][b[i]] != c[i]:
        count += 1
print(count)

Submission status: Wrong Answer

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

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

for i in range(M):
    d[a[i]-1][b[i]-1] = c[i]
    d[b[i]-1][a[i]-1] = c[i]

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

count = 0
for i in range(M):
    if d[a[i]-1][b[i]-1] != c[i]:

        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import copy
n, m = map(int, input().split())
# 隣接行列
e = [[float('inf')]*n for i in range(n)]
for i in range(m):
    a, b,c = map(int, input().split())
    e[a-1][b-1]=c
    e[b-1][a-1]=c


ans=[[float('inf')]*n for i in range(n)]
d=copy.deepcopy(e)
# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i==j or k==i or k==j:
                    continue

                if d[i][j]==float('inf') and (d[i][k]==float('inf') or d[k][j]==float('inf')):
                    continue
                else:
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j]=d[i][k]+d[k][j]
                        ans[i][k] = 0
                        ans[k][j] = 0
                        ans[i][j] = 1
                    elif d[i][j] < d[i][k] + d[k][j]:
                        ans[i][j] = 0
                    else:
                        ans[i][k] = 0
                        ans[k][j] = 0
                        ans[i][j] = 0
warshall_floyd(d)
x=0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float('inf'):
            if ans[i][j]!=0:
                x+=1
print(x//2)

Submission status: Wrong Answer

Solution code:
import copy
n, m = map(int, input().split())
# 隣接行列
e = [[float('inf')]*n for i in range(n)]
for i in range(m):
    a, b,c = map(int, input().split())
    e[a-1][b-1]=c
    e[b-1][a-1]=c


ans=[[float('inf')]*n for i in range(n)]
d=copy.deepcopy(e)
# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if i==j or k==i or k==j:
                    continue

                if d[i][j]==float('inf') and (d[i][k]==float('inf') or d[k][j]==float('inf')):
                    continue
                else:
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j]=d[i][k]+d[k][j]
                        ans[i][k] = 0
                        ans[k][j] = 0
                    elif d[i][j] < d[i][k] + d[k][j]:
                        ans[i][j] = 0
                    else:
                        ans[i][k] = 0
                        ans[k][j] = 0
                        ans[i][j] = 0
warshall_floyd(d)
x=0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float('inf'):
            if ans[i][j]!=0:
                x+=1
print(x//2)

Submission status: Wrong Answer

Solution code:
import copy
n, m = map(int, input().split())
# 隣接行列
e = [[float('inf')]*n for i in range(n)]
for i in range(m):
    a, b,c = map(int, input().split())
    e[a-1][b-1]=c
    e[b-1][a-1]=c


ans=[[float('inf')]*n for i in range(n)]
d=copy.deepcopy(e)
# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i==j or k==i or k==j:
                    continue

                if d[i][j]==float('inf') and (d[i][k]==float('inf') or d[k][j]==float('inf')):
                    continue

                else:
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j]=d[i][k]+d[k][j]
                        ans[i][k] = 0
                        ans[k][j] = 0
                    elif d[i][j] < d[i][k] + d[k][j]:
                        ans[i][j] = 0
                    else:
                        ans[i][k] = 0
                        ans[k][j] = 0
                        ans[i][j] = 0
warshall_floyd(d)
x=0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float('inf'):
            if ans[i][j]!=0:
                x+=1
print(x//2)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
# 隣接行列
e = [[float('inf')]*n for i in range(n)]
for i in range(m):
    a, b,c = map(int, input().split())
    e[a-1][b-1]=c
    e[b-1][a-1]=c


ans=[[float('inf')]*n for i in range(n)]
d=e
# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i==j or k==i or k==j:
                    continue

                if d[i][j]==float('inf') and (d[i][k]==float('inf') or d[k][j]==float('inf')):
                    continue

                else:
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j]=d[i][k]+d[k][j]
                        ans[i][k] = 0
                        ans[k][j] = 0
                    elif d[i][j] < d[i][k] + d[k][j]:
                        ans[i][j] = 0
                    else:
                        ans[i][k] = 0
                        ans[k][j] = 0
                        ans[i][j] = 0
warshall_floyd(d)
x=0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float('inf'):
            if ans[i][j]!=0:
                x+=1
print(x//2)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
# 隣接行列
e = [[float('inf')]*n for i in range(n)]
for i in range(m):
    a, b,c = map(int, input().split())
    e[a-1][b-1]=c
    e[b-1][a-1]=c


ans=[[float('inf')]*n for i in range(n)]
d=e
# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i==j or k==i or k==j:
                    continue

                if d[i][j]==float('inf') and (d[i][k]==float('inf') or d[k][j]==float('inf')):
                    continue

                else:
                    if d[i][j] > d[i][k] + d[k][j]:

                        ans[i][k] = 0
                        ans[k][j] = 0
                    elif d[i][j] < d[i][k] + d[k][j]:
                        ans[i][j] = 0
                    else:
                        ans[i][k] = 0
                        ans[k][j] = 0
                        ans[i][j] = 0
warshall_floyd(d)
x=0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float('inf'):
            if ans[i][j]!=0:
                x+=1
print(x//2)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
# 隣接行列
d = [[float('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


ans=[[float('inf')]*n for i in range(n)]

# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i==j or k==i or k==j:
                    continue

                if d[i][j]==float('inf') and (d[i][k]==float('inf') or d[k][j]==float('inf')):
                    continue

                else:
                    if d[i][j] > d[i][k] + d[k][j]:
                        ans[i][k] = 0
                        ans[k][j] = 0
                    elif d[i][j] < d[i][k] + d[k][j]:
                        ans[i][j] = 0
                    else:
                        ans[i][k] = 0
                        ans[k][j] = 0
                        ans[i][j] = 0
warshall_floyd(d)
x=0
for i in range(n):
    for j in range(n):
        if d[i][j]!=float('inf'):
            if ans[i][j]!=0:
                x+=1
print(x//2)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
# 隣接行列
d = [[float('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


ans=[[float('inf')]*n for i in range(n)]

# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i==j or k==i or k==j:
                    continue
                if d[i][j]==float('inf') and (d[i][k]==float('inf') or d[k][j]==float('inf')):
                    continue
                else:
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j] = d[i][k] + d[k][j]
                        ans[i][k] = 0
                        ans[k][j] = 0
                    elif d[i][j] < d[i][k] + d[k][j]:
                        ans[i][j] = 0
                    else:
                        ans[i][k] = 0
                        ans[k][j] = 0
                        ans[i][j] = 0
warshall_floyd(d)
x=0
for i in range(n):
    for j in range(n):
        if d[i][j]==float('inf'):
            if ans[i][j]!=0:
                x+=1
print(x//2)

Submission status: Wrong Answer

Solution code:
INF = float("inf")

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M


N, M, *ABC = map(int, open(0).read().split())

E = [[INF] * (N + 1) for _ in range(N + 1)]
for a, b, c in zip(*[iter(ABC)] * 3):
    E[a][b] = c
    E[b][a] = c

D = WarshallFloyd(E)

cnt = 0
for a, b, c in zip(*[iter(ABC)] * 3):
    if any(D[s][a] + c == D[s][b] for s in range(1, N + 1)):
        cnt += 1

print(M - cnt)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import defaultdict

N,M=map(int,input().split())
paths_dict={n:set() for n in range(1,N+1)}#key:int value:set of (int as point_num,int as dist)
all_paths=set()#set of tuples
for m in range(1,M+1):
    a,b,c=map(int,input().split())
    paths_dict[a].add((b,c))
    paths_dict[b].add((a,c))
    all_paths.add((min(a,b),max(a,b)))

pairs=set(combinations(range(1,N+1),2))#set of tuples
while pairs!=set():
    start,goal=pairs.pop()
    visited_dict=defaultdict(lambda: [set(),1+max(visited_dict[visited][1] for visited in visited_dict)])
    visited_dict[start]=[{0},0]#key:int value:[{int as former_point},int as dist_from_start]
    ends={start:[{0},0]}#key:int value:[int as former_point,int as dist_from_start]

    while ends!={} and visited_dict[goal][1]>min(ends[end][1] for end in ends):
        frontier={}#key:int value:[{ints as former_points},int as dist_from_start]
        for end in (end for end in ends if ends[end][1]<visited_dict[goal][1]):
            for num_dist in [num_dist for num_dist in paths_dict[end]]:
                if num_dist[0] in visited_dict:
                    if num_dist[0] in frontier:
                        if ends[end][1]+num_dist[1]<frontier[num_dist[0]][1]:
                            frontier[num_dist[0]]=[{end},ends[end][1]+num_dist[1]]
                        elif ends[end][1]+num_dist[1]==frontier[num_dist[0]][1]:
                            frontier[num_dist[0]][0].add(end)
                    else:
                        if ends[end][1]+num_dist[1]<visited_dict[num_dist[0]][1]:
                            visited_dict[num_dist[0]]=[{end},ends[end][1]+num_dist[1]]
                        elif ends[end][1]+num_dist[1]==visited_dict[num_dist[0]][1]:
                            visited_dict[num_dist[0]][0].add(end)
                else:
                    frontier[num_dist[0]]=[{end},ends[end][1]+num_dist[1]]
        visited_dict.update(frontier)
        ends=frontier

    used_paths=set()
    used_pairs=set()
    points={goal}
    while points!=set():
        former_points=set()
        for point in points:
            if point!=start:
                for former_point in visited_dict[point][0]:
                    former_points.add(former_point)
                    used_paths.add((min(former_point,point),max(former_point,point)))
                    used_pairs|={(min(former_point,point),max(former_point,point)),(min(former_point,goal),max(former_point,goal))}
        points=former_points
    all_paths-=used_paths
    pairs-=used_pairs

print(len(all_paths))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
G=[[10**10 for i in range(N)] for i in range(N)]
for i in range(N):
    G[i][i]=0
edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
    edge.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])
ans=0
for e in edge:
    fin=False
    for i in range(N-1):
        for j in range(i+1,N):
            if G[i][e[0]]+e[2]+G[e[1]][j]==G[i][j]:
                ans+=1
                fin=True
            if fin:
                break
        if fin:
            break
print(len(edge)-ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
INF = 10**10
graph = [[INF for _ in range(N)] for _ in range(N)]

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

cnt = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if(graph[i][j] > graph[i][k]+graph[k][j]):
                if(graph[i][j] != INF):
                    cnt += 1
                graph[i][j] = graph[i][k]+graph[k][j]
print(cnt//2)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc051/tasks/abc051_d
# 考えたこと
# 1.warshal floydからの経路復元でやってみる←御解答
# s→tまでは最短経路が2つ存在する場合がある。そのときうまくいかない

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate
from copy import deepcopy


def read_ints():
    return list(map(int, read().split()))


from collections import defaultdict
INF = 10**9
N, M = read_ints()
D = [[INF] * N for _ in range(N)]

edges = defaultdict(lambda: INF)
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c
    edges[b, a] = c
    edges[a, b] = c
for i in range(N):
    D[i][i] = 0

# warshal floyd
for k in range(N):
    for i in range(N):
        if D[i][k] >= INF:  # 定数倍高速化
            # ノード同士がつながってなければ更新しない
            continue
        for j in range(N):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])


# 経路復元


def restore_path(s: int, t: int, edges: dict, D: list):
    '''
    s→tまでの最短経路を復元する
    edgesはオリジナルの辺のリスト edges[a,b]=a,bを結ぶ辺の長さ。ないときは0(?INF)
    Dは最短経路D[s][t]=s→tの最短経路
    '''
    ret = []  # 経路
    cur = s
    while cur != t:
        for i in range(N):
            if i != cur and edges[cur, i] + D[i][t] == D[cur][t]:
                ret.append((cur, i) if cur < i else (i, cur))  # 大小関係をはっきりさせておく
                cur = i
                break
    return ret


#
from itertools import combinations
edges_used = set()
for s, t in combinations(range(N), 2):
    edges_used |= set(restore_path(s, t, edges, D))
print(M - len(edges_used))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc051/tasks/abc051_d
# 考えたこと
# 1.warshal floydからの経路復元でやってみる

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate
from copy import deepcopy


def read_ints():
    return list(map(int, read().split()))


INF = 10**9
N, M = read_ints()
adj_mat = [[INF] * N for _ in range(N)]
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj_mat[a][b] = c
    adj_mat[b][a] = c
for i in range(N):
    adj_mat[i][i] = 0

D = deepcopy(adj_mat)
# warshal floyd
for k in range(N):
    for i in range(N):
        if D[i][k] >= INF:  # 定数倍高速化
            # ノード同士がつながってなければ更新しない
            continue
        for j in range(N):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])

# print(*adj_mat, sep='\n')

# 経路復元


def restore_path(s: int, t: int, adj_mat: list, D: list):
    '''
    s→tまでの最短経路を復元する
    adj_mat
    '''
    ret = []  # 経路
    cur = s
    while cur != t:
        for i in range(N):
            if i != cur and adj_mat[cur][i] + D[i][t] == D[cur][t]:
                ret.append((cur, i) if cur < i else (i, cur))  # 大小関係をはっきりさせておく
                cur = i
                break
    return ret


#
from itertools import combinations
edges = set()
for s, t in combinations(range(N), 2):
    edges |= set(restore_path(s, t, adj_mat, D))
print(M - len(edges))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    inf = 10**17

    def dijkstra_heap(start,edge):
        #始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf]*N
        used = [False]*N
        d[start] = 0
        used[start] = True
        edgelist = []
        #a:重み(//), b:次の頂点(%)
        for a,b,i in edge[start]:
            heappush(edgelist,(a*(10**6)+b, i))

        while len(edgelist):
            #まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge, i = heappop(edgelist)
            if used[minedge%(10**6)]:
                continue
            node = minedge%(10**6)
            d[node] = minedge//(10**6)
            res[i] = 1
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist,((e[0]+d[node])*(10**6)+e[1], e[2]))
        return d

    #N:頂点数   W:辺数
    N, W = map(int, input().split())
    edge = [[] for i in range(N)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for i in range(W):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1,i))
        edge[y-1].append((z,x-1,i))
        
    res = [0]*W
    for i in range(N):
        d = dijkstra_heap(i, edge)
    print(W - sum(res))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[[0]*n for i in range(n)]
edges=[]
for i in range(m):
  u,v,c=map(int,input().split())
  g[u-1][v-1]=g[v-1][u-1]=c
  edges.append((u-1,v-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])
cnt=0
flag=False
for u,v,c in edges:
  if g[u][v]==c:
    cnt+=1
print(m-cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[[0]*n for i in range(n)]
edges=[]
for i in range(m):
  u,v,c=map(int,input().split())
  g[u-1][v-1]=g[v-1][u-1]=c
  edges.append((u-1,v-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])
cnt=0
flag=False
for u,v,c in edges:
  flag=False
  for i in range(n):
    for j in range(i+1,n):
      if g[i][j]==(g[i][u]+c+g[v][j]) or g[i][j]==(g[i][v]+c+g[u][j]):
        cnt+=1
        flag=True
        break
    if flag:
      break
print(m-cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[[0]*n for i in range(n)]
edges=[]
for i in range(m):
  u,v,c=map(int,input().split())
  g[u-1][v-1]=g[v-1][u-1]=c
  edges.append((u-1,v-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])
cnt=0
flag=False
for u,v,c in edges:
  flag=False
  for i in range(n):
    for j in range(i+1,n):
      if g[i][j]==g[i][u]+c+g[v][j]:
        cnt+=1
        flag=True
        break
    if flag:
      break
print(m-cnt)

Submission status: Wrong Answer

Solution code:
#051_D
from heapq import heappop, heappush
inf = 10 ** 10
n, m = map(int, input().split())
d = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    d[i][i] = 0
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    edges.append((a-1, b-1, c))

def warshall_floyd(d):
    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])
                
warshall_floyd(d)

ans = 0
for u, v, c in edges:
    for i in range(n):
        if i == u or i == v:
            continue
        if abs(d[u][i] - d[v][i]) == c:
            ans += 1
            break

print(m - ans)

Submission status: Wrong Answer

Solution code:
#051_D
from heapq import heappop, heappush
inf = 10 ** 10
n, m = map(int, input().split())
d = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    d[i][i] = 0
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    edges.append((a-1, b-1, c))

def warshall_floyd(d):
    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])
                
warshall_floyd(d)

ans = 0
for u, v, c in edges:
    for i in range(n):
        if i == u or i == v:
            continue
        if d[u][i] + d[i][v] <= c:
            ans += 1
            break

print(ans)

Submission status: Wrong Answer

Solution code:
#051_D
from heapq import heappop, heappush
inf = 10 ** 10
n, m = map(int, input().split())
d = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    d[i][i] = 0
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    edges.append((a-1, b-1))

def warshall_floyd(d):
    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])
                
warshall_floyd(d)

ans = 0
for u, v in edges:
    for i in range(n):
        if i == u or i == v:
            continue
        if d[u][i] + d[i][v] == d[u][v]:
            ans += 1
            break

print(ans)

Submission status: Wrong Answer

Solution code:
#051_D
#最小全域木問題(kruskal)
n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((c, a-1, b-1))

par=[i for i in range(n)]
size=[1 for _ in range(n)]
rank=[0 for _ in range(n)]

#Unionfind 
def find(x):#木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
    
def merge(x,y):#併合
    x=find(x)
    y=find(y)
    if x==y:
        return
    if rank[x]>rank[y]:
        par[y]=x
        size[x]+=size[y]
    else:
        par[x]=y
        size[y]+=size[x]
        if rank[x]==rank[y]:
            rank[y]+=1
            
def same(x,y):
    return find(x)==find(y)

def kruskal():
    edges.sort()
    
    res = 0
    for i in range(0, m):
        cost, u, v = edges[i]
        if not same(u, v):
            merge(u, v)
            res += 1
            
    return m - res

print(kruskal())

Submission status: Wrong Answer

Solution code:
# cadidates of no shortest paths
n, m = map(int, input().split())

d = [[float("inf") for i in range(n + 1)] for i in range(n + 1)]
edge_data=[]
connect={i:[] for i in range(1,n+1)}
for i in range(m):
    x, y, z = map(int, input().split())
    # 有向グラフか無向グラフかによってここで場合わけが生じる
    d[x][y] = z
    d[y][x] = z
    connect[x].append(y)
    connect[y].append(x)    
    edge_data.append((x,y))
for i in range(n + 1):
    d[i][i] = 0  # 自身のところに行くコストは０


def warshall_floyd(d):
    # d[i][j]=i番目の頂点からj番目の頂点までの最短距離
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

warshall_floyd(d)

#最短距離を求めた
cnt=0
for some in edge_data:
    x,y=some[0],some[1]
    flag=True
    for child in connect[y]:
        if x!=child and d[x][child]+d[child][y]<=d[x][y]:
            flag=False
    if flag is False  or len(connect[x])==1:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
# cadidates of no shortest paths
n, m = map(int, input().split())

d = [[float("inf") for i in range(n + 1)] for i in range(n + 1)]
edge_data=[]
connect={i:[] for i in range(1,n+1)}
for i in range(m):
    x, y, z = map(int, input().split())
    # 有向グラフか無向グラフかによってここで場合わけが生じる
    d[x][y] = z
    d[y][x] = z
    connect[x].append(y)
    connect[y].append(x)    
    edge_data.append((x,y))
for i in range(n + 1):
    d[i][i] = 0  # 自身のところに行くコストは０


def warshall_floyd(d):
    # d[i][j]=i番目の頂点からj番目の頂点までの最短距離
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

warshall_floyd(d)

#最短距離を求めた
cnt=0
for some in edge_data:
    x,y=some[0],some[1]
    flag=True
    for child in connect[y]:
        if x!=child and d[x][child]+d[child][y]<=d[x][y]:
            flag=False
    if flag is False:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
# cadidates of no shortest paths
n, m = map(int, input().split())

d = [[float("inf") for i in range(n + 1)] for i in range(n + 1)]
edge_data=[]
connect={i:[] for i in range(1,n+1)}
for i in range(m):
    x, y, z = map(int, input().split())
    # 有向グラフか無向グラフかによってここで場合わけが生じる
    d[x][y] = z
    d[y][x] = z
    connect[x].append(y)
    connect[y].append(x)    
    edge_data.append((x,y))
for i in range(n + 1):
    d[i][i] = 0  # 自身のところに行くコストは０


def warshall_floyd(d):
    # d[i][j]=i番目の頂点からj番目の頂点までの最短距離
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

warshall_floyd(d)

#最短距離を求めた
cnt=0
for some in edge_data:
    x,y=some[0],some[1]
    sub=0
    for child in connect[y]:
        if d[x][child]+d[child][y]==d[x][y]:
            sub+=1
    if sub>1:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
N, M, *L = map(int, open(0).read().split())
dist = [[10**10]*(N+1) for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dist[a][b] = c
  dist[b][a] = c
  dist[a][a] = 0
  dist[b][b] = 0

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

ans = 0
for a,b,c in zip(*[iter(L)]*3):
  s = min(dist[a][x]+dist[x][b] if x!=a and x!=b else 10**10 for x in range(1,N+1))
  if s==dist[a][b]:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, *L = map(int, open(0).read().split())
dist = [[10**10]*(N+1) for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dist[a][b] = c
  dist[b][a] = c
  dist[a][a] = 0
  dist[b][b] = 0

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

ans = 0
for a,b,c in zip(*[iter(L)]*3):
  if c>dist[a][b]:
    ans += 1
    continue
  s = min(dist[a][x]+dist[x][b] if x!=a and x!=b else 10**10 for x in range(1,N+1))
  if s<=c:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, *L = map(int, open(0).read().split())
dist = [[10**10]*(N+1) for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dist[a][b] = c
  dist[b][a] = c
  dist[a][a] = 0
  dist[b][b] = 0

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

ans = 0
for a,b,c in zip(*[iter(L)]*3):
  s = min(dist[a][x]+dist[b][x] if x!=a and x!=b else 10**10 for x in range(1,N+1))
  if s<=c:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, *L = map(int, open(0).read().split())
dist = [[10**10]*(N+1) for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dist[a][b] = c
  dist[b][a] = c

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

ans = 0
for a,b,c in zip(*[iter(L)]*3):
  if c>dist[a][b]:
    ans += 1
    continue
  s = min(x+y for x,y in zip(dist[a],dist[b]))
  if s==c:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

# --- ワーシャルフロイド
def warshall_floyd(dp):
    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])
    return dp

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

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

warshall_floyd(d)

ans = m

for i, (a,b,c) in enumerate(abc):
    a,b = a-1,b-1
    for j in range(n):
        if  d[j][a] + c == d[j][b]:
            ans-=1
            break

print(ans)