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
input = sys.stdin.readline
def main():
    N, M = map( int, input().split())
    d = dict()
    for i in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = c
    V = [[1000000]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for (s,t), c in d.items():
        V[s][t] = V[t][s] = c
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            for k in range(N):
                if V[i][k] + V[k][j] < V[i][j]:
                    V[i][j] = V[i][k] + V[k][j]
    ans = 0
    for (s,t), c in d.items():
        check = False
        for k in range(N**2):
            i = k//N
            j = k%N
            if V[i][s] + c + V[t][j] == V[i][j]:
                check = True
                break
        if check == False:
            ans += 1

    print(ans)
                
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M = map( int, input().split())
    d = dict()
    for i in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = c
    V = [[1000000]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for (s,t), c in d.items():
        V[s][t] = V[t][s] = c
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            for k in range(N):
                if V[i][k] + V[k][j] < V[i][j]:
                    V[i][j] = V[i][k] + V[k][j]
    ans = 0
    for (s,t), c in d.items():
        check = False
        for k in range(N**2):
            i = k//N
            j = k%N
            if V[i][s] + c + V[t][j] == V[i][j]:
                check == True
                break
        if check == False:
            ans += 1

    print(ans)
                
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M = map( int, input().split())
    d = dict()
    for i in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = c
    V = [[1000000]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for (s,t), c in d.items():
        V[s][t] = V[t][s] = c
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            for k in range(N):
                if V[i][k] + V[k][j] < V[i][j]:
                    V[i][j] = V[i][k] + V[k][j]
    ans = 0
    for (s,t), c in d.items():
        for k in range(N**2):
            i = k//N
            j = k%N
            if V[i][s] + c + V[t][j] == V[i][j]:
                break
        else:
            ans += 1
            
                
    print(ans)
                
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

N, M = map(int, input().split())
graph = {i:[] for i in range(1, N+1)}
v = set()
route = {}

for i in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((c, b))
    graph[b].append((c, a))
    v.add(a)
    v.add(b)
    if a > b:
        route[(a,b)] = False
    else:
        route[(b,a)] = False
        
while v:
    visited = [False for i in range(N+1)]
    q = []
    s = v.pop()
    for c, r in graph[s]:
        heapq.heappush(q, (c, r, s))
        
    while q:
        c, r, s = heapq.heappop(q)    
        if not visited[r]:
            visited[r] = True
            
            if r in v:
                #v.remove(r)
                pass
            if r > s:
                route[(r,s)] = True
            else:
                route[(s,r)] = True
            
            for c_, r_ in graph[r]:
                if not visited[r_]:
                    heapq.heappush(q, (c+c_, r_, r))
ans = 0
for i in route.values():
    if not i:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N, M = map(int, input().split())
graph = {i:[] for i in range(1, N+1)}
v = set()
route = {}

for i in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((c, b))
    graph[b].append((c, a))
    v.add(a)
    v.add(b)
    if a > b:
        route[(a,b)] = False
    else:
        route[(b,a)] = False
        
while v:
    visited = [False for i in range(N+1)]
    q = []
    s = v.pop()
    for c, r in graph[s]:
        heapq.heappush(q, (c, r, s))
        
    visited[1] = True    
    while q:
        c, r, s = heapq.heappop(q)    
        if not visited[r]:
            visited[r] = True
            
            if r in v:
                v.remove(r)
            if r > s:
                route[(r,s)] = True
            else:
                route[(s,r)] = True
            
            for c_, r_ in graph[r]:
                if not visited[r_]:
                    heapq.heappush(q, (c+c_, r_, r))
ans = 0
for i in route.values():
    if not i:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N, M = map(int, input().split())
graph = {i:[] for i in range(1, N+1)}
visited = [False for i in range(N+1)]
cost = [10**20 for i in range(N+1)]
ans = 0

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

q = []
for r in graph[1]:
    heapq.heappush(q, r)
    
visited[1] = True    
cost[1] = 0

while q:
    c, r = heapq.heappop(q)    
    if not visited[r]:
        cost[r] = c
        visited[r] = True
        ans += 1
        
        for c_, r_ in graph[r]:
            if not visited[r_]:
                heapq.heappush(q, (c+c_, r_))
        
print(M-ans)

Submission status: Wrong Answer

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

for i in range(N + 1):
    costs[i][i] = 0
paths = []
for i in range(M):
    a, b, c = [int(_) for _ in input().split()]
    costs[a][b] = c
    costs[b][a] = c
    paths.append((a, b, c))

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

for i in range(N):
    paths2 = paths.copy()
    for p in paths:
        # 点i から 経路p をつかってp[1]への経路をもつかチェック
        if costs[i][p[0]] >= INF or costs[i][p[1]] >= INF: continue
        if costs[i][p[0]] + p[2] == costs[i][p[1]]:
            paths2.remove(p)
    paths = paths2
print(len(paths))

Submission status: Wrong Answer

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

for i in range(N + 1):
    costs[i][i] = 0
paths = []
for i in range(M):
    a, b, c = [int(_) for _ in input().split()]
    costs[a][b] = c
    costs[b][a] = c
    paths.append((a, b, c))

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

for i in range(N):
    paths2 = paths.copy()
    for p in paths:
        # 点i から 経路p をつかってp[1]への経路をもつかチェック
        if costs[i][p[0]] + p[2] == costs[i][p[1]]:
            paths2.remove(p)
    paths = paths2
print(len(paths))

Submission status: Wrong Answer

Solution code:

from collections import defaultdict
import heapq


def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    graph_data = defaultdict(set)
    weight_data = defaultdict(int)

    for i in range(edge_num):
        a, b, c = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)
        weight_data[(a, b)] = c
        weight_data[(b, a)] = c

    used_edge = set()

    inf = 10 ** 5 + 1

    for i in range(1, node_num + 1):
        visit_flg = [0 for i in range(node_num + 1)]
        length_data = [inf for i in range(node_num + 1)]
        length_data[i] = 0
        heap_list = []
        for ele in graph_data[i]:
            weight = weight_data[(i, ele)]
            heapq.heappush(heap_list, (weight, ele, i))

            while len(heap_list) > 0:
                now_weight, now_ele, pre_ele = heapq.heappop(heap_list)
                # print(visit_flg, 'vf')
                if visit_flg[now_ele]:
                    continue
                visit_flg[now_ele] = 1
                length_data[now_ele] = length_data[pre_ele] + weight_data[(pre_ele, now_ele)]
                used_edge.add((min(now_ele, pre_ele), max(now_ele, pre_ele)))
                for next_ele in graph_data[now_ele]:

                    if visit_flg[next_ele]:
                        continue
                    next_weight = weight_data[(now_ele, next_ele)] + length_data[now_ele]
                    heapq.heappush(heap_list, (next_weight, next_ele, now_ele))

                # print(used_edge, 'ue')
                # print(heap_list, 'hl')
                # print(visit_flg, 'vf')
                # print(length_data, 'ld')
                # print()

    print(edge_num - len(used_edge))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:


def main():
    node_num, edge_num = map(int, input().split())

    print(edge_num - node_num + 1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
link = [[] for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    link[a-1].append([b-1, c])
    link[b-1].append([a-1, c])
visited = [[0] * 2 for _ in range(N)]

def dfs(v, d, cnt, pv):
    if visited[v][0]:
        return
    visited[v][0] = 1
    for nv in link[v]:
        t = nv[0]
        if t == pv:
            continue
        d += nv[1]
        if visited[t][1] == 0:
            visited[t][1] = d
            visited[v][1] = d
        else:
            if visited[t][1] < d:
                cnt += 1
            elif visited[t][1] == d:
                pass
            elif visited[t][1] > d:
                cnt += 1
                visited[t][1] = d
                visited[v][1] = d
        dfs(t, d, cnt, v)
    return cnt

ans = dfs(0, 0, 0, -1)

print(ans)

Submission status: Wrong Answer

Solution code:
class Kruskal_UnionFind():
    # 無向グラフであるという前提に注意
    def __init__(self, N):
        self.edges = []
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def add(self, u, v, d):
        """
        u = from, v = to, d = cost
        """
        self.edges.append([u, v, d])

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def size(self, x):
        x = self.find(x)
        return self.counter[x]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def Kruskal(self):
        """
        return: 最小全域木のコストの和
        """
        edges = sorted(self.edges, key=lambda x: x[2])  # costでself.edgesをソートする
        res = 0
        counter = 0
        for e in edges:
            if not self.same(e[0], e[1]):
                self.unite(e[0], e[1])
                res += e[2]
                counter += 1
        return res, counter

N, M = map(int, input().split())
a = []
b = []
c = []

for i in range(M):
    _a, _b, _c = map(int, input().split())
    a.append(_a)
    b.append(_b)
    c.append(_c)

kruskal = Kruskal_UnionFind(N+1)
for i in range(M):
    kruskal.add(a[i], b[i], c[i])


print(M-kruskal.Kruskal()[1])

Submission status: Wrong Answer

Solution code:
import itertools

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

# graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**20
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]
edges = []
for i in range(M):
    a,b,c = list(map(int,input().split(" ")))
    cost[a][b] = c
    cost[b][a] = c
    edges.append((a,b,c))
for i in range(1,N+1):
    cost[i][i] = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j])
            cost[j][i] = min(cost[j][i], cost[j][k] + cost[k][i])
ans = 0
for k,edge in enumerate(edges):
            a,b,c = edge
            if  cost[a][b] !=c:
                ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

# graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**20
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]
edges = []
for i in range(M):
    a,b,c = list(map(int,input().split(" ")))
    cost[a][b] = c
    cost[b][a] = c
    edges.append((a,b,c))
for i in range(1,N+1):
    cost[i][i] = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j])
for i in range(1,N+1):
    for j in range(1,N+1):
        for k,edge in enumerate(edges):
            a,b,c = edge
            if  cost[i][j] == (cost[i][a] + c +  cost[b][j]):
                used[k] = True
print(used.count(False))

Submission status: Wrong Answer

Solution code:
import itertools

N,M = list(map(int,input().split(" ")))
graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**20
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]

for i  in range(1,N+1):
    cost[i][i] = 0
for a,b,c in graph:
    cost[a][b] =min(c,cost[a][b])
    cost[b][a] = min(c,cost[b][a])


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


ans = 0
for k,temp  in enumerate(graph):
    a,b,c = temp
    if cost[a][b]  <  c:
        ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N,M = list(map(int,input().split(" ")))
graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**10
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]

for i  in range(1,N+1):
    cost[i][i] = 0
for a,b,c in graph:
    cost[a][b] = c
    cost[b][a] = c



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


ans = 0
for k,temp  in enumerate(graph):
    a,b,c = temp
    if cost[a][b]  <  c:
        ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N,M = list(map(int,input().split(" ")))
graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**10
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]

for i  in range(1,N+1):
    cost[i][i] = 0
for a,b,c in graph:
    cost[a][b] = c
    cost[b][a] = c



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



for i in range(1,N+1):
    for j in range(1,N+1):
        for k,temp  in enumerate(graph):
            a,b,c = temp
            if cost[i][j] == cost[i][a] + c +   cost[b][j]:
                used[k] = True
            if cost[i][j] == cost[i][b] + c +   cost[a][j]:
                used[k] = True
print(used.count(False))

Submission status: Wrong Answer

Solution code:
import itertools

N,M = list(map(int,input().split(" ")))
graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**10
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]

for i  in range(1,N+1):
    cost[i][i] = 0
for a,b,c in graph:
    cost[a][b] = c
    cost[b][a] = c



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



for i in range(1,N+1):
    for j in range(1,N+1):
        for k,temp  in enumerate(graph):
            a,b,c = temp
            if cost[i][j] == cost[i][a] + c +   cost[b][j]:
                used[k] = True

print(used.count(False))

Submission status: Wrong Answer

Solution code:
import itertools

N,M = list(map(int,input().split(" ")))
graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**10
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]

for i  in range(1,N+1):
    cost[i][i] = 0
for a,b,c in graph:
    cost[a][b] = c
    cost[b][a] = c



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



for k,temp  in enumerate(graph):
        a,b,c = temp
        if cost[i][j] == cost[i][a] + c +   cost[b][j]:
            used[k] = True

print(used.count(False))

Submission status: Wrong Answer

Solution code:
import itertools

N,M = list(map(int,input().split(" ")))
graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**10
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]

for i  in range(1,N+1):
    for j in range(1,N+1):
        cost[i][j] = 0
for a,b,c in graph:
    cost[a][b] = c
    cost[b][a] = c



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


ans = 0
for k,temp  in enumerate(graph):
        a,b,c = temp
        if  cost[a][b] < c :
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N,M = list(map(int,input().split(" ")))
graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**10
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]

for i  in range(1,N+1):
    for j in range(1,N+1):
        cost[i][j] = 0
for a,b,c in graph:
    cost[a][b] = c
    cost[b][a] = c



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



for k,temp  in enumerate(graph):
        a,b,c = temp
        if  cost[a][b] < c :
            used[k] = True

print(used.count(False))

Submission status: Wrong Answer

Solution code:
import itertools

N,M = list(map(int,input().split(" ")))
graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**10
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]

for i  in range(1,N+1):
    for j in range(1,N+1):
        cost[i][j] = 0
for a,b,c in graph:
    cost[a][b] = c
    cost[b][a] = c



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



for i in range(1,N+1):
    for j in range(1,N+1):
        for k,temp  in enumerate(graph):
            a,b,c = temp
            if cost[i][j] == cost[i][a] + cost[a][b] +   cost[b][j]:
                used[k] = True

print(used.count(False))

Submission status: Wrong Answer

Solution code:
import itertools

N,M = list(map(int,input().split(" ")))
graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**10
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]

for i  in range(1,N+1):
    for j in range(1,N+1):
        cost[i][j] = 0
for a,b,c in graph:
    cost[a][b] = c
    cost[b][a] = c



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



for i in range(1,N+1):
    for j in range(1,N+1):
        for k,temp  in enumerate(graph):
            a,b,c = temp
            if cost[i][j] == cost[i][a] + c +   cost[b][j]:
                used[k] = True
            if cost[i][j] == cost[i][b] + c +   cost[a][j]:
                used[k] = True
print(used.count(False))

Submission status: Wrong Answer

Solution code:
import itertools

N,M = list(map(int,input().split(" ")))
graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**10
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]

for i  in range(1,N+1):
    for j in range(1,N+1):
        cost[i][j] = 0
for a,b,c in graph:
    cost[a][b] = c
    cost[b][a] = c



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



for i in range(N+1):
    for j in range(N+1):
        for k,temp  in enumerate(graph):
            a,b,c = temp
            if cost[i][j] == cost[i][a] + c +   cost[b][j]:
                used[k] = True
            if cost[i][j] == cost[i][b] + c +   cost[a][j]:
                used[k] = True

print(used.count(False))

Submission status: Wrong Answer

Solution code:
import itertools

N,M = list(map(int,input().split(" ")))
graph = [list(map(int,input().split(" "))) for _  in range(M)]
used = [False] * M
INF = 10**10
cost = [[INF for _ in range(N+1)] for _ in range(N+1)]

for i  in range(1,N+1):
    for j in range(1,N+1):
        cost[i][j] = 0
for a,b,c in graph:
    cost[a][b] = c
    cost[b][a] = c



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



for i in range(N+1):
    for j in range(N+1):
        for k,temp  in enumerate(graph):
            a,b,c = temp
            if cost[i][j] == cost[i][a] + c +   cost[b][j]:
                used[k] = True

print(used.count(False))

Submission status: Wrong Answer

Solution code:
import collections
import heapq


class Dijkstra():
    def __init__(self, N):
        self.N = N
        self.e = [[float('inf') for i in range(self.N)] for i in range(N)]

    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u][v] = d
            self.e[v][u] = d
        else:
            self.e[u][v] = d

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

    def Dijkstra_search(self, s):
        """
        0-indexedであることに注意
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True
            for uv, ud in enumerate(self.e[u]):
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    def getDijkstraPath(self, s, t):
        # sからtへの最短経路の経路復元
        prev = [s] * self.N  # 最短経路の直前の頂点
        d = [float("inf")] * self.N
        used = [False] * self.N
        d[s] = 0

        while True:
            v = -1
            for i in range(self.N):
                if (not used[i]) and (v == -1):
                    v = i
                elif (not used[i]) and d[i] < d[v]:
                    v = i
            if v == -1:
                break
            used[v] = True

            for i in range(self.N):
                if d[i] > d[v] + self.e[v][i]:
                    d[i] = d[v] + self.e[v][i]
                    prev[i] = v

        path = [t]
        while prev[t] != s:
            path.append(prev[t])
            prev[t] = prev[prev[t]]
        path.append(s)
        path = path[::-1]
        return path


N, M = map(int, input().split())
graph = Dijkstra(N)
paths = []
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c, directed=False)
    paths.append([a-1, b-1])

usedPaths = collections.defaultdict(set)
for i in range(N):
    for j in range(i+1, N):
        path = graph.getDijkstraPath(i, j)
        if len(path) == 2:
            usedPaths[path[0]].add(path[1])
            usedPaths[path[1]].add(path[0])
        else:
            for k, v in enumerate(path[:-1]):
                usedPaths[v].add(path[k + 1])
                usedPaths[path[k+1]].add(v)

ans = M - (sum([len(a) for a in list(usedPaths.values())]) - N)//2
print(ans)

Submission status: Wrong Answer

Solution code:
# 頂点の数（N）および辺の数（M）を入力する
N, M = map(int, input().split())

# 辺の長さを格納する辞書（dic_edge_dist）を設定する
dic_edge_dist = {(i, j) : float("inf") for i in range(1, N + 1) for j in range(1, N + 1)}
for i in range(1, N + 1):
    dic_edge_dist[(i, i)] = 0
# 辺を格納するリスト（list_edge）を設定する
list_edge = []

def warshall_floyd(dic_edge_dist):
    dic_shortest_dist = dic_edge_dist.copy()
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                dic_shortest_dist[(j, k)] = min(dic_shortest_dist[(j, k)], dic_shortest_dist[(j, i)] + dic_shortest_dist[(i, k)])
    return dic_shortest_dist

# 各辺について、、
for _ in range(M):
    # 頂点および辺の長さを入力する
    a, b, c = map(int, input().split())
    # dic_edge_distに辺の長さを格納する
    dic_edge_dist[(a, b)] = c
    dic_edge_dist[(b, a)] = c
    # list_edgeに辺を格納する
    list_edge.append((min(a, b), max(a, b)))

dic_shortest_dist = warshall_floyd(dic_edge_dist)
    
edge_count = 0
for i, j in list_edge:
    for k in range(1, N + 1):
        if dic_shortest_dist[(k, i)] + dic_edge_dist[(i, j)] == dic_shortest_dist[(k, j)]:
            edge_count += 1
            print(i, j, k)
            break
        if dic_shortest_dist[(k, j)] + dic_edge_dist[(j, i)] == dic_shortest_dist[(k, i)]:
            edge_count += 1
            print(i, j, k)
            break

print(dic_edge_dist)
print(dic_shortest_dist)
print(len(list_edge) - edge_count)

Submission status: Wrong Answer

Solution code:
import collections
import heapq


class Dijkstra():
    def __init__(self, N):
        self.N = N
        self.e = [[float('inf') for i in range(self.N)] for i in range(N)]

    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u][v] = d
            self.e[v][u] = d
        else:
            self.e[u][v] = d

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

    def Dijkstra_search(self, s):
        """
        0-indexedであることに注意
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True
            for uv, ud in enumerate(self.e[u]):
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    def getDijkstraPath(self, s, t):
        # sからtへの最短経路の経路復元
        prev = [s] * self.N  # 最短経路の直前の頂点
        d = [float("inf")] * self.N
        used = [False] * self.N
        d[s] = 0

        while True:
            v = -1
            for i in range(self.N):
                if (not used[i]) and (v == -1):
                    v = i
                elif (not used[i]) and d[i] < d[v]:
                    v = i
            if v == -1:
                break
            used[v] = True

            for i in range(self.N):
                if d[i] > d[v] + self.e[v][i]:
                    d[i] = d[v] + self.e[v][i]
                    prev[i] = v

        path = [t]
        while prev[t] != s:
            path.append(prev[t])
            prev[t] = prev[prev[t]]
        path.append(s)
        path = path[::-1]
        return path


N, M = map(int, input().split())
graph = Dijkstra(N)
paths = []
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c, directed=False)
    paths.append([a-1, b-1])

#d = graph.Dijkstra_search(0)
for i in range(N):
    for j in range(i, N):
        path = graph.getDijkstraPath(i, j)
        if len(path) == 2:
            if path in paths:
                paths.remove(path)
        else:
            for k, v in enumerate(path[:-2]):
                if [v, path[k + 1]] in paths:
                    paths.remove([v, path[k + 1]])

print(len(paths))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
INF = 10**9
N, M = map(int, input().split())
d = [[INF] * (N+1) for i in range(N+1)]
for i in range(N+1):
    d[i][i] = 0
es = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b], d[b][a] = c, c
    es[i] = (a, b, c)
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])
ans = M
for k in range(M):
    i, j, c = es[k]
    for s in range(1, N):
        if d[s][i] + c == d[s][j]:
            ans -= 1
            break
print(ans)