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:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
edges = [[10**18]*N for _ in range(N)]
used = [[False]*N for _ in range(N)]

ab = []
for _ in range(M):
    a, b, c = mapint()
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c
    ab.append((a-1, b-1))

from heapq import heappop, heappush

def dijkstra(start):
    dist = [10**18]*N
    Q = [(0, start, start)]
    cnt = 0
    while Q:
        d, v, e = heappop(Q)
        if d>=dist[v]:
            continue
        else:
            dist[v] = d
        cnt += 1
        used[v][e] = True
        used[e][v] = True
        for nx in range(N):
            if edges[v][nx]==10**18:
                continue
            if dist[nx] > d + edges[v][nx]:
                heappush(Q, (d + edges[v][nx], nx, v))
        if cnt==N:
            break

for i in range(N):
    dijkstra(i)
ans = 0
for a, b in ab:
    if not used[a][b]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
edges = [[10**18]*N for _ in range(N)]
used = [[False]*N for _ in range(N)]

ab = []
for _ in range(M):
    a, b, c = mapint()
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c
    ab.append((a-1, b-1))

from heapq import heappop, heappush

def dijkstra(start):
    dist = [10**18]*N
    Q = [(0, start, start)]
    cnt = 0
    while Q:
        d, v, e = heappop(Q)
        if d>=dist[v]:
            continue
        else:
            dist[v] = d + edges[v][e]
        cnt += 1
        used[v][e] = True
        used[e][v] = True
        for nx in range(N):
            if edges[v][nx]==10**18:
                continue
            if dist[nx] > d + edges[v][nx]:
                heappush(Q, (d + edges[v][nx], nx, v))
        if cnt==N:
            break

for i in range(N):
    dijkstra(i)
ans = 0
for a, b in ab:
    if not used[a][b]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
edges = [[10**18]*N for _ in range(N)]
used = [[False]*N for _ in range(N)]

ab = []
for _ in range(M):
    a, b, c = mapint()
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c
    ab.append((a-1, b-1))

from heapq import heappop, heappush

def dijkstra(start):
    dist = [10**18]*N
    dist[start] = 0
    Q = [(0, start, start)]
    cnt = 0
    while Q:
        d, v, e = heappop(Q)
        cnt += 1
        used[v][e] = True
        used[e][v] = True
        for nx in range(N):
            if edges[v][nx]==10**18:
                continue
            if dist[nx] > dist[v] + edges[v][nx]:
                dist[nx] = dist[v] + edges[v][nx]
                heappush(Q, (dist[nx], nx, v))
        if cnt==N:
            break

for i in range(N):
    dijkstra(i)
ans = 0
for a, b in ab:
    if not used[a][b]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
edges = [[10**18]*N for _ in range(N)]
used = [[False]*N for _ in range(N)]

ab = []
for _ in range(M):
    a, b, c = mapint()
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c
    ab.append((a-1, b-1))

from heapq import heappop, heappush

def dijkstra(start):
    dist = [10**18]*N
    dist[start] = 0
    Q = [(0, start, start, start)]
    cnt = 0
    while Q:
        d, v, s, e = heappop(Q)
        cnt += 1
        used[s][e] = True
        used[e][s] = True
        for nx in range(N):
            if dist[nx] > dist[v] + edges[v][nx]:
                dist[nx] = dist[v] + edges[v][nx]
                heappush(Q, (dist[nx], nx, v, nx))
        if cnt==N:
            break

for i in range(N):
    dijkstra(i)
ans = 0
for a, b in ab:
    if not used[a][b]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
ans = [1 for _ in range(m)]

graph = [set() for _ in range(n)]
side = dict()
ans = [0 for _ in range(m + 1)]
for i in range(m):
    a, b, c = map(int, input().split())
    t = (a - 1, b - 1, c)
    side[i] = t
    graph[a-1].add(i)
    graph[b-1].add(i)

for j in range(n):
    D = [(j, j, m), ]
    heapq.heapify(D)
    done = [True for _ in range(n)]

    while D:
        d = heapq.heappop(D)
        if done[d[1]]:
            done[d[1]] = False
            ans[d[2]] = 1

            for i in graph[d[1]]:
                a, b, c = side[i]
                if b == d[1]:
                    a, b = b, a
                if done[b]:
                    heapq.heappush(D, (d[0] + c, b, i))

print(m - (sum(ans) - 1))

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
ans = [1 for _ in range(m)]
done = [True for _ in range(n)]
graph = [set() for _ in range(n)]
side = dict()
ans = [0 for _ in range(m + 1)]
for i in range(m):
    a, b, c = map(int, input().split())
    t = (a - 1, b - 1, c)
    side[i] = t
    graph[a-1].add(i)
    graph[b-1].add(i)

for j in range(n):
    D = [(j, j, m), ]
    heapq.heapify(D)

    while D:
        d = heapq.heappop(D)
        if done[d[1]]:
            done[d[1]] = False
            ans[d[2]] = 1

            for i in graph[d[1]]:
                a, b, c = side[i]
                if b == d[1]:
                    a, b = b, a
                if done[b]:
                    heapq.heappush(D, (d[0] + c, b, i))

print(m - (sum(ans) - 1))

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
ans = [1 for _ in range(m)]
done = [True for _ in range(n)]
graph = [set() for _ in range(n)]
side = dict()
ans = [0 for _ in range(m + 1)]
for i in range(m):
    a, b, c = map(int, input().split())
    t = (a - 1, b - 1, c)
    side[i] = t
    graph[a-1].add(i)
    graph[b-1].add(i)

D = [(0, 0, m), ]
heapq.heapify(D)

while D:
    d = heapq.heappop(D)
    if done[d[1]]:
        done[d[1]] = False
        ans[d[2]] = 1

        for i in graph[d[1]]:
            a, b, c = side[i]
            if b == d[1]:
                a, b = b, a
            if done[b]:
                heapq.heappush(D, (d[0] + c, b, i))

print(m - (sum(ans) - 1))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
g = []
dp = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    g.append((a-1,b-1,c))
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
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(dp)
cnt = 0

for a,b,c in g:
    f = True
    for i in range(n):
        if dp[i][a]+c==dp[i][b]:
            f = False
            break
    if f:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

inf = 10 ** 9 + 7
dp = [[inf] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    dp[a][b] = c
    dp[b][a] = c

check = [[False] * N for _ in range(N)]
count = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dp[i][j] != inf and dp[i][j] > dp[i][k] + \
                    dp[k][j] and not check[i][j] and not check[j][i]:
                check[i][j] = True
                check[j][i] = True

            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])


count = 0
for i in range(N):
    for j in range(N):
        if check[i][j]:
            count += 1

print(count // 2)

Submission status: Wrong Answer

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

inf = 10 ** 9 + 7
dp = [[inf] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    dp[a][b] = c
    dp[b][a] = c

check = [[False] * N for _ in range(N)]
count = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dp[i][j] != inf and dp[i][j] > dp[i][k] + \
                    dp[k][j] and not check[i][j] and not check[j][i]:
                check[i][j] = True
                check[j][i] = True
                count += 1

            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])


print(count)

Submission status: Wrong Answer

Solution code:
import sys
import heapq

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

INF = 10 ** 18


def dijkstra(N, s0, edge):

    d = [INF] * N
    used = [False] * N
    edgelist = [(0, s0, -1)]
    heapq.heapify(edgelist)

    ret = set()
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True

        if minedge[2] != -1:
            p = minedge[2]
            ret.add((min(p, v), max(p, v)))

        for e in edge[v]:
            if d[e[1]] == (e[0] + d[v]):
                ret.add((min(v, e[1]), max(v, e[1])))
                continue
            if d[e[1]] <= (e[0] + d[v]) or used[e[1]]:
                continue
            heapq.heappush(edgelist, (e[0] + d[v], e[1], v))

    return ret


def main():
    N, M = in_nn()
    edge = [[] for _ in range(N)]

    for i in range(M):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge[a].append((c, b))
        edge[b].append((c, a))

    used = set()
    for i in range(N):
        used |= dijkstra(N, i, edge)

    print(M - len(used))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

INF = 10 ** 18


def dijkstra(N, s0, edge):

    d = [INF] * N
    used = [False] * N
    edgelist = [(0, s0, -1)]
    heapq.heapify(edgelist)

    ret = set()
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True

        if minedge[2] != -1:
            p = minedge[2]
            ret.add((min(p, v), max(p, v)))

        for e in edge[v]:
            if d[e[1]] < (e[0] + d[v]) or used[e[1]]:
                continue
            if d[e[1]] == (e[0] + d[v]) or used[e[1]]:
                ret.add((min(v, e[1]), max(v, e[1])))
                continue
            heapq.heappush(edgelist, (e[0] + d[v], e[1], v))

    return ret


def main():
    N, M = in_nn()
    edge = [[] for _ in range(N)]

    for i in range(M):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge[a].append((c, b))
        edge[b].append((c, a))

    used = set()
    for i in range(N):
        used |= dijkstra(N, i, edge)

    print(M - len(used))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

INF = 10 ** 18


def dijkstra(N, s0, edge):

    d = [INF] * N
    used = [False] * N
    edgelist = [(0, s0, -1)]
    heapq.heapify(edgelist)

    ret = set()
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True

        if minedge[2] != -1:
            p = minedge[2]
            ret.add((min(p, v), max(p, v)))

        for e in edge[v]:
            if d[e[1]] <= (e[0] + d[v]) or used[e[1]]:
                continue
            heapq.heappush(edgelist, (e[0] + d[v], e[1], v))

    return ret


def main():
    N, M = in_nn()
    edge = [[] for _ in range(N)]

    for i in range(M):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge[a].append((c, b))
        edge[b].append((c, a))

    used = set()
    for i in range(N):
        used |= dijkstra(N, i, edge)

    print(M - len(used))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

INF = 10 ** 18


def dijkstra(N, s0, edge):

    d = [INF] * N
    used = [False] * N
    edgelist = [(0, s0, -1)]
    pre_v = [-1] * N
    heapq.heapify(edgelist)

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        pre_v[v] = minedge[2]
        for e in edge[v]:
            if d[e[1]] <= (e[0] + d[v]) or used[e[1]]:
                continue
            heapq.heappush(edgelist, (e[0] + d[v], e[1], v))

    ret = set()
    for i in range(N):
        if i == s0:
            continue

        now = i
        while True:
            if pre_v[now] == -1:
                break
            else:
                p = min(pre_v[now], now)
                n = max(pre_v[now], now)
                ret.add((p, n))
                now = pre_v[now]

    return ret


def main():
    N, M = in_nn()
    edge = [[] for _ in range(N)]

    for i in range(M):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge[a].append((c, b))
        edge[b].append((c, a))

    used = set()
    for i in range(N):
        used |= dijkstra(N, i, edge)

    print(M - len(used))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

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):
    visit=[0]*n
    q=[(0,i,-1)]
    dist=[0]*n

    while len(q)>0:
        d,u,v=heapq.heappop(q)

        if visit[u]==1:
            continue

        if v>=0:
            used.add((max(u,v),min(u,v)))

        visit[u]=1
        dist[u]=d

        for w,nd in g[u]:
            heapq.heappush(q,(dist[u]+nd,w,u))

print(m-len(used))

Submission status: Wrong Answer

Solution code:
import heapq

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):
    visit=[0]*n
    q=[(0,i,-1)]
    dist=[0]*n

    while len(q)>0:
        d,u,v=heapq.heappop(q)

        if visit[u]==1:
            continue

        if v>=0:
            used.add((max(u,v),min(u,v)))

        visit[u]=1
        dist[u]=dist[v]+d

        for w,nd in g[u]:
            if visit[w]==1:
                continue

            heapq.heappush(q,(nd,w,u))

print(m-len(used))

Submission status: Wrong Answer

Solution code:
import heapq

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):
    visit=[0]*n
    q=[(0,i,-1)]
    dist=[0]*n

    while len(q)>0:
        d,u,v=heapq.heappop(q)

        if visit[u]==1:
            continue

        if v>=0:
            used.add((max(u,v),min(u,v)))

        visit[u]=1
        dist[u]=d

        for w,nd in g[u]:
            if visit[w]==1:
                continue

            heapq.heappush(q,(dist[u]+nd,w,u))

print(m-len(used))

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

INF = float("inf")
import copy

def warshall_floyd(d):
    n = len(d)
    wf = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    return wf #d[i][j]に頂点i, j間の最短距離を格納

##############################

n, m = map(int,input().split()) #N:頂点数 m:辺の数
d = [[INF] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    u, v, w = map(int,input().split())
    d[u-1][v-1] = w
    d[v-1][u-1] = w
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
#print(floyd_warshall(d))   #d[i][j]に頂点i, j間の最短距離を格納

# 経路復元
fwd = warshall_floyd(d)

def path(s, g):
    ret = []
    if s == g or fwd[s][g] == INF:
        return ret
    cur = s
    while cur!=g:
        for nxt in range(n):
            if nxt==cur or nxt==s: continue
            if d[cur][nxt] + fwd[nxt][g] == fwd[cur][g]:
                ret.append((cur, nxt))
                ret.append((nxt, cur))
                cur = nxt
                break
    return ret

edges = set([])
for i in range(n):
    for j in range(n):
        x = path(i, j)
        edges = edges | set(x)
print(m-len(edges)//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

INF = float("inf")
import copy

def warshall_floyd(d):
    n = len(d)
    wf = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    return wf #d[i][j]に頂点i, j間の最短距離を格納

##############################

n, m = map(int,input().split()) #N:頂点数 m:辺の数
d = [[INF] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    u, v, w = map(int,input().split())
    d[u-1][v-1] = w
    d[v-1][u-1] = w
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
#print(floyd_warshall(d))   #d[i][j]に頂点i, j間の最短距離を格納

# 経路復元
fwd = warshall_floyd(d)

def path(s, g):
    ret = []
    if s == g:
        return ret
    cur = s
    while cur!=g:
        for nxt in range(n):
            if nxt==cur or nxt==s: continue
            if d[cur][nxt] + fwd[nxt][g] == fwd[cur][g]:
                ret.append((cur, nxt))
                ret.append((nxt, cur))
                cur = nxt
                break
    return ret

edges = set([])
for i in range(n):
    for j in range(n):
        x = path(i, j)
        edges = edges | set(x)
print(m-len(edges)//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

INF = float("inf")
import copy

def warshall_floyd(d):
    n = len(d)
    wf = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    return wf #d[i][j]に頂点i, j間の最短距離を格納

##############################

n, m = map(int,input().split()) #N:頂点数 m:辺の数
d = [[INF] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    u, v, w = map(int,input().split())
    d[u-1][v-1] = w
    d[v-1][u-1] = w
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
#print(warshall_floyd(d, n))
print(d)
#print(floyd_warshall(d))   #d[i][j]に頂点i, j間の最短距離を格納

# 経路復元
fwd = warshall_floyd(d)
print(d)

def path(s, g):
    ret = []
    if s == g:
        return ret
    cur = s
    while cur!=g:
        for nxt in range(n):
            if nxt==cur or nxt==s: continue
            if d[cur][nxt] + fwd[nxt][g] == fwd[cur][g]:
                print(cur,nxt,d[cur][nxt],fwd[nxt][g],fwd[cur][g])
                ret.append((cur, nxt))
                ret.append((nxt, cur))
                cur = nxt
                break
    return ret

edges = set([])
for i in range(n):
    for j in range(n):
        x = path(i, j)
        edges = edges | set(x)
print(m-len(edges)//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

INF = float("inf")
import copy

def warshall_floyd(d):
    n = len(d)
    wf = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    return wf #d[i][j]に頂点i, j間の最短距離を格納

##############################

n, m = map(int,input().split()) #N:頂点数 m:辺の数
d = [[INF] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    u, v, w = map(int,input().split())
    d[u-1][v-1] = w
    d[v-1][u-1] = w
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
#print(warshall_floyd(d, n))
print(d)
#print(floyd_warshall(d))   #d[i][j]に頂点i, j間の最短距離を格納

# 経路復元
fwd = warshall_floyd(d)
print(d)

def path(s, g):
    ret = []
    if s == g:
        return ret
    cur = s
    while cur!=g:
        for nxt in range(n):
            if nxt==cur or nxt==s: continue
            if d[cur][nxt] + fwd[nxt][g] == fwd[cur][g]:
                print(cur,nxt,d[cur][nxt],fwd[nxt][g],fwd[cur][g])
                ret.append((cur, nxt))
                ret.append((nxt, cur))
                cur = nxt
                break
    return ret

edges = set([])
for i in range(n):
    for j in range(n):
        x = path(i, j)
        print(i,j,x)
        edges = edges | set(x)
print(edges)
print(m-len(edges)//2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

INF = float("inf")

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

    return d #d[i][j]に頂点i, j間の最短距離を格納

##############################

n, m = map(int,input().split()) #N:頂点数 m:辺の数
d = [[INF] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    u, v, w = map(int,input().split())
    d[u-1][v-1] = w
    d[v-1][u-1] = w
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
#print(warshall_floyd(d, n))

#print(floyd_warshall(d))   #d[i][j]に頂点i, j間の最短距離を格納

# 経路復元
fwd = warshall_floyd(d, n)
def path(s, g):
    ret = []
    if s == g:
        return ret
    cur = s
    while cur!=g:
        for nxt in range(n):
            if nxt==cur or nxt==s: continue
            if d[cur][nxt] + fwd[nxt][g] == fwd[cur][g]:
                ret.append((cur, nxt))
                ret.append((nxt, cur))
                cur = nxt
                break
    return ret

edges = set([])
for i in range(n):
    for j in range(n):
        edges = edges | set(path(i, j))
print(max(m-len(edges)//2,0))

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

from scipy.sparse.csgraph import floyd_warshall

INF = float("inf")

n, m = map(int,input().split()) #N:頂点数 M:辺の数
d = [[INF] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    u, v, w = map(int,input().split())
    d[u-1][v-1] = w
    d[v-1][u-1] = w
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

#print(floyd_warshall(d))   #d[i][j]に頂点i, j間の最短距離を格納

# 経路復元
fwd = floyd_warshall(d)
def path(s, g):
    ret = []
    if s == g:
        return ret
    cur = s
    while cur!=g:
        for nxt in range(n):
            if nxt==cur or nxt==s: continue
            if d[cur][nxt] + fwd[nxt][g] == fwd[cur][g]:
                ret.append((cur, nxt))
                cur = nxt
                break
    return ret

edges = set([])
for i in range(n):
    for j in range(n):
        edges = edges | set(path(i, j))
print(m-len(edges)//2)

Submission status: Wrong Answer

Solution code:
N, M = [int(a) for a in input().split()]
edges = {i:[] for i in range(1,N+1)}
cost = {}
tagged = {}

for i in range(M):
  a,b,c = [int(k) for k in input().split()]
  edges[a].append(b)
  edges[b].append(a)
  cost[a*1000+b] = c
  cost[b*1000+a] = c
  tagged[a*1000+b] = 0
  
for a,lst in edges.items():
  min_val = min([cost[a*1000 + b] for b in lst])
  for b in lst:
    if cost[a*1000+b] == min_val:
      if a*1000+b in tagged:
        tagged[a*1000+b] = 1
      elif b*1000+a in tagged:
        tagged[b*1000+a] = 1


ans = len([v for k,v in tagged.items() if v == 0])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(a) for a in input().split()]

edges = {i:[] for i in range(1,N+1)}

cost = {}
tagged = {}
for i in range(M):
  a,b,c = [int(k) for k in input().split()]
  edges[a].append(b)
  edges[b].append(a)
  cost[a*100+b] = c
  cost[b*100+a] = c
  tagged[a*100+b] = 0
  
for a,lst in edges.items():
  min_val = min([cost[a*100 + i] for i in lst])
  for b in lst:
    if cost[a*100+b] == min_val:
      if a*100+b in tagged:
        tagged[a*100+b] = 1
      elif b*100+a in tagged:
        tagged[b*100+a] = 1


ans = M - sum([v for k,v in tagged.items()])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
to = [[float("INF")] * N for i in range(N)]
aa = []

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

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

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

print(to)

c = 0
for i in range(M):
    for j in range(N):
        if to[j][aa[i][1]] == to[j][aa[i][0]] + aa[i][2]:
            c += 1
            break


print(M - c)

Submission status: Wrong Answer

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

G = [[] for _ in range(N)]
INF = 10**9
D = [[ INF for _ in range(N)] for _ in range(N)]
E = []
for _ in range(M):
  a,b,c = map(int, input().split())
  a,b = a-1, b-1
  G[a].append((b,c))
  G[b].append((a,c))
  D[a][b] = c
  D[b][a] = c
  E.append((a,b,c))
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if D[i][k] + D[k][j] < D[i][j]:
        D[i][j] = D[i][k] + D[k][j]
        D[j][i] = D[i][k] + D[k][j]
  
ans = 0
for a,b,c in E:
  flg = False
  for i in range(N):
    if D[i][a] + c == D[i][b]:
      flg = True
  if not flg:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

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

G = [[] for _ in range(N)]
INF = 10**9
D = [[ INF for _ in range(N)] for _ in range(N)]
E = []
for _ in range(M):
  a,b,c = map(int, input().split())
  a,b = a-1, b-1
  G[a].append((b,c))
  G[b].append((a,c))
  D[a][b] = c
  D[b][a] = c
  E.append((a,b,c))
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if D[i][k] + D[k][j] < D[i][j]:
        D[i][j] = D[i][k] + D[k][j]
        D[j][i] = D[i][k] + D[k][j]
  
ans = 0
for a,b,c in E:
  flg = False
  for i in range(N):
    if D[i][a] + D[a][b] == D[i][b]:
      flg = True
  if not flg:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
dis = [[float("inf") for i in range(n)] for j in range(n)]
for i in range(n):
    dis[i][i] = 0
abc = []
for i in range(m):
    a, b, c = map(int, input().split())
    abc.append([a, b, c])
    dis[a-1][b-1] = c
    dis[b-1][a-1] = c
def warshall_floyd(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis1 = dis[i][j]
                dis2 = dis[i][k] + dis[k][j]
                dis[i][j] = min(dis1, dis2)
    return dis
data = warshall_floyd(dis)
ans = 0
for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    for j in range(n):
        if b - 1 != j:
            if data[a-1][b-1] + data[b-1][j] == data[a-1][j]:
                break
        if a - 1 != j:
            if data[a-1][b-1] + data[a-1][j] == data[b-1][j]:
                break
    else:
        ans += 1
print(ans)