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: Time Limit Exceeded

Solution code:
class MakeGraph:
    
    # 隣接行列もしくは隣接リストの初期化
    # node_num：ノード数
    # isMat：隣接行列(True) / 隣接リスト(False)
    def __init__(self, node_num:int, isMat:bool) -> None:
        self.n = node_num
        self.isMat = isMat

        # 隣接行列の初期化
        if self.isMat:
            INF = float("inf")
            self.graph = [[INF for _ in range(self.n)] for _ in range(self.n)]
    
        # 隣接リストの初期化
        else:
            self.graph = [[] for _ in range(self.n)]

    # エッジの追加
    # frm, to：起点ノード, 終点ノード
    # dist：frm→toへのコスト
    def add_undr_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        self.graph[to][frm] = dist
        
    def add_drct_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        
    def add_undr_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))
        self.graph[to].append((dist, frm))
        
    def add_drct_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))

                
    # 完成したグラフを取り出す
    def get_graph(self) -> list:
        return self.graph


N,M = map(int, input().split())
ABC = []
for i in range(M):
    ABC.append(tuple(map(int, input().split())))
    
graphMaker = MakeGraph(N,True)
add_edge = graphMaker.add_undr_edge_mat
for a,b,c in ABC:
    add_edge(a-1, b-1, c)
    
graph = graphMaker.get_graph()
for i in range(N):
    graph[i][i] = 0

# WF        
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]:
                graph[i][j] = graph[i][k]+graph[k][j]
 
# 辺集合
edge_list = []
for a,b,c in ABC:
    edge_list.append([a-1,b-1, c])   

ans = 0
for i,j,cost in edge_list:
    flag = 1
    for frm in range(N):
        for to in range(N):
            if frm == to:
                continue

            if graph[frm][i]+cost+graph[j][to] == graph[frm][to]:
                flag = 0
                    
    ans += flag
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
connect = {}
dist = {}
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in connect.keys(): connect[a] = [b]
    else: connect[a].append(b)
    if not b in connect.keys(): connect[b] = [a]
    else: connect[b].append(a)
    
    dist[tuple(sorted([a, b]))] = c

ans = 0
for s in range(1, n):
    for t in range(s+1, n+1):
        if not (s, t) in dist.keys():
            continue
        
        dists = [1000]*(n+1)
        dists[s] = 0
        stack = [(s, sc) for sc in connect[s]]
        while len(stack) > 0:
            s0, s1 = stack[0]
            stack = stack[1:]
            if dists[s0]+dist[tuple(sorted((s0, s1)))] >= dists[s1]:
                continue
            else:
                dists[s1] = dists[s0]+dist[tuple(sorted((s0, s1)))]
                for s2 in connect[s1]:
                    stack.append((s1, s2))
        # print(dists)
        if dists[t] < dist[(s, t)]:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
n,m=map(int,input().split())
v=[[0 for i in range(n)] for i in range(n)]
used=[[0 for i in range(n)] for i in range(n)]
cost_table=[[99999999 for i in range(n)] for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    v[a-1][b-1]=1
    v[b-1][a-1]=1
    cost_table[a-1][b-1]=c
    cost_table[b-1][a-1]=c

init_cost_table=[]
for i in range(n):
    init_cost_table.append(cost_table[i][:])

for i in range(n):
    for j in range(n):
        for k in range(n):
            if cost_table[i][k]>cost_table[i][j]+cost_table[j][k]:
                cost_table[i][k]=cost_table[i][j]+cost_table[j][k]
    cost_table[i][i]=0

def Path(start,goal):
    cur = start;
    while cur != goal:
        for i in range(n):
            if (i != cur and init_cost_table[cur][i] + cost_table[i][goal] == cost_table[cur][goal]):
                used[cur][i]=1
                cur = i
                break

for i in range(n):
    for j in range(n):
        if i==j:
            continue
        Path(i,j)
ans=0
for i in range(n):
    ans+=sum(v[i])
for i in range(n):
    ans-=sum(used[i])
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

INF = 10 ** 10
def main():
    N, M = map(int, input().split())

    dp = [[INF] * N for _ in range(N)]
    edges = []
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        dp[a][b] = c
        dp[b][a] = c
        edges.append((a, b, c))
        
    for i in range(N):
        dp[i][i] = 0

    for m in range(N):
        for s in range(N):
            for e in range(N):
                if dp[s][m] != INF and dp[m][e] != INF:
                    dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e])

    ans = 0
    for a, b, c in edges:
        found = False
        for s in range(N):
            for e in range(N):
                if dp[s][a] + c + dp[b][e] == dp[s][e]:
                    found = True
                    break
            if found:
                break
        if not found:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product as prod

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

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

def dist(i, j, gr=gr):
    tmp_d = float("inf")
    if i == j:
        return 0
    for (node, d) in gr[i]:
        if node == j:
            tmp_d = d
    gr_cp = gr.copy()
    gr_cp[i] = []
    routes = [d + dist(n, j, gr=gr_cp) for (n, d) in gr[i]]

    return min(routes + [tmp_d])

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

print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product as prod

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

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

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

    return min(routes + [tmp_d])

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

print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product as prod

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

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

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

    return min(routes + [tmp_d])

ans = 0
for i, j in prod(range(1, n), range(1, n)):
    for (node, d) in gr[i]:
        if node == j and d > dist(i, j):
            ans += 1
print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product as prod

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

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

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

    return min(routes + [tmp_d])

ans = 0
for i, j in prod(range(1, m), range(1, m)):
    for (n, d) in gr[i]:
        if n == j and d > dist(i, j):
            ans += 1
print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product as prod

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

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

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

    return min(routes + [tmp_d])

ans = 0
for i, j in prod(range(1, m), range(1,m)):
    for (n, d) in gr[i]:
        if n == j and d > dist(i, j):
            ans += 1
print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

my_input = lambda : map(int, input().split(" "))

N, M = my_input()
dist = 100 * 1000 * np.ones([N, N])

edges = []
for i in range(M):
    a, b, c = my_input()
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
    edges.append((a, b, c))

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

print(len([e for e in edges if e[2] != dist[e[0]-1][e[1]-1]]))

Submission status: Time Limit Exceeded

Solution code:

# D - Candidates of No Shortest Paths

MAXI = 999999999

# 入力
N, M = map(int, input().split())
cost = [[-1 for i in range(N)] for j in range(N)]

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

# iからjへの最短距離を表すテーブルの初期化
dist = [[MAXI for i in range(N)] for j in range(N)]

# iからjへの辺があったら、最短距離をその辺のコストで初期化
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif cost[i][j] != -1:
            dist[i][j] = cost[i][j]
            dist[j][i] = dist[i][j]

# ワーシャルフロイドで各i,j間の最短距離を求めておく
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# print(dist)

ans = 0

for i in range(N):
    for j in range(i, N):
        if cost[i][j] != -1: # 各辺がどの異なる２点の最短経路にも含まれないかを調べる
            flag = 1

            for k in range(N):
                for l in range(k + 1, N):
                    # 一つでも最短経路に含まれていたならブレイク
                    if dist[k][l] == dist[k][i] + cost[i][j] + dist[j][l]:
                        flag = 0
                        break
            
            # 全ての異なる２点間の最短経路に含まれていなかったら+1カウント
            ans += flag


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import random

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

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

    random.shuffle(es)

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

nd = [[] for _ in range(n + 1)]
eg = [True] * m
for i in range(m):
    a, b, c = map(int, input().split())
    nd[a].append([b, c, i])
    nd[b].append([a, c, i])

for i in range(1, n):
    for j in range(i + 1, n + 1):
        tr = [10 * 10] * (n + 1)
        fg = [False] * (n + 1)
        fr = [[] for _ in range(n + 1)]
        tr[i] = 0
        while True:
            mi = 0
            for k in range(1, n + 1):
                if fg[k]:
                    continue
                if mi == 0 or tr[k] < tr[mi]:
                    mi = k
            if mi == 0:
                break
            fg[mi] = True
            for xc in nd[mi]:
                x, c, e = xc
                nc = c + tr[mi]
                if nc < tr[x]:
                    tr[x] = nc
                    fr[x] = [mi, e]
        mi, e = fr[j]
        eg[e] = False
        while len(fr[mi]) > 0:
            mi, e = fr[mi]
            eg[e] = False

ans = 0
for f in eg:
    if f:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

    dp=[[float('inf')]*n for _ in range(n)]
    for i in range(n):
        dp[i][i]=0
    for u,v,w in es:
        dp[u][v]=dp[v][u]=w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
    res=0
    for u,v,w in es:
        used=False
        for i in range(n):
            for j in range(i+1,n):
                if dp[i][j]==dp[i][u]+w+dp[v][j] or dp[i][j]==dp[i][v]+w+dp[u][j]:
                    used=True
        if not used:
            res+=1
    print(res)

Submission status: Accepted

Solution code:
def dijkstra(s):
    import  heapq
    dist=[inf for i in range(n)] #sからの距離のリスト
    dist[s]=0
    mirai=[True for i in range(n)] #Trueなら未確定
    mirai[s]=False

    queue=[] #こいつがheapqになる
    for kyori,to in G[s]:
        heapq.heappush(queue , kyori*10**6+to)  #重みと行先を1つの変数で表してる！
    while queue:
        minedge= heapq.heappop(queue)
        #miraiがTrueのやつ(未確定なやつ)から最小距離のものをさがす
        if not mirai[minedge%(10**6)]: continue
        #距離が小さいものから"確定"していく
        v=minedge%(10**6) #最小距離の頂点
        dist[v] = minedge//(10**6) #その距離
        mirai[v]=False
        for kyori,to in G[v]:
            if mirai[to]:
                heapq.heappush(queue, (kyori+dist[v])*(10**6)+to)
                #queueに入る数は、必ず「sからの」距離と行先を持っている
    return dist
n,m=map(int,input().split())
inf=10**10
G=[[] for i in range(n)]
HEN=[]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    G[a].append((c,b))
    G[b].append((c,a))
    HEN.append((a,b,c))

MIN=[[10**10]*n for i in range(n)]
for i in range(n):
    MIN[i]=dijkstra(i)
ans=0
for a,b,c in HEN:
    for s in range(n):
        if MIN[s][a]+c == MIN[s][b]:
            break
        if MIN[s][b]+c == MIN[s][a]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]

edge = set()
INF = float('inf')
cost = [[INF]*n for _ in range(n)]
for i in range(n):
    cost[i][i] = 0
for a, b, c in abc:
    a, b = a-1, b-1
    cost[a][b] = c
    cost[b][a] = c
    edge.add((a, b, c))

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

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

Submission status: Accepted

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


for i in range(m):
    a, b, c = map(int, input().split())
    edges[i] = (a - 1, b - 1, c)
    graph[a - 1].add(i)
    graph[b - 1].add(i)

# (cost,done,node,edge)
for i in range(n):
    done = [True for _ in range(n)]
    D = [(0, 0, i, m), ]
    heapq.heapify(D)

    while D:
        d = heapq.heappop(D)
        cost, mark, node, edge = d

        if done[node]:
            done[node] = False
            ans[edge] = 1

            for g in graph[node]:
                a, b, c = edges[g]

                if b == node:
                    a, b = b, a

                if done[b]:
                    heapq.heappush(D, (cost + c, ans[g], b, g))

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

Submission status: Accepted

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: Accepted

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

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 = [(0, 0, j, m), ]
    heapq.heapify(D)
    done = [True for _ in range(n)]

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

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

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

Submission status: Accepted

Solution code:
INFTY = 10**5+10
N,M = map(int,input().split())
L = [list(map(int,input().split())) for _ in range(M)]
G = {i:[] for i in range(1,N+1)}
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for j in range(M):
    a,b,c = L[j]
    G[a].append(b)
    G[b].append(a)
    dist[a][b] = c
    dist[b][a] = c
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
cnt = 0
for j in range(M):
    a,b,c = L[j]
    if dist[a][b]<c:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import heapq
def dijkstra(s, n, g): # s: start, n: |V|, g; glaph 
    INF = 10**18
    prev_vl = [-1]*n # record the prev vertex of each one for restoring the route
    d = [INF] * n
    d[s] = 0
    que = [] # (a,b): a... shortest dist, b... v
    heapq.heappush(que, (0, s))

    while que:
        dist, v = heapq.heappop(que)
        if d[v] < dist: continue # if v has been already used -> continue
        for next_v, cost in g[v]:
            if d[next_v] > d[v] + cost:
                d[next_v] = d[v] + cost
                prev_vl[next_v] = v
                heapq.heappush(que, (d[next_v], next_v))
    
    # resotre the route
    # route = [g]
    # curr_v = g
    # while True:
    #     prev_v = prev_vl[curr_v]
    #     if prev_v == -1: break
    #     else: route.append(prev_v)
    # route = route[::-1]
    # return d, route

    used_edges = []
    for i in range(n):
        if i == s: continue
        used_edges.append((prev_vl[i],i))
    return d, used_edges


n,m = map(int, input().split())
g = [ [] for _ in range(n)]
edges = [ [False]*n 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))
    edges[a][b] = True
    edges[b][a] = True

for i in range(n):
    d, used_edges = dijkstra(i, n, g)
    for a,b in used_edges:
        edges[a][b] = False
        edges[b][a] = False

ans = 0
for i in range(n):
    for j in range(n):
        if edges[i][j]: ans += 1

print(ans//2)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
L=[[] for i in range(n+1)]
DIC={}
for _ in range(m):
    a,b,c=map(int,input().split())
    L[a].append((b,c))
    L[b].append((a,c))
    DIC[(a,b)]=0

que=[] #あとで


heapq.heapify(que)

for tar in range(1,n+1):
    sc=[10**8 for i in range(n+1)]
    sc[tar]=0
    pre=[tar for i in range(n+1)]
    heapq.heappush(que,(0,tar))
    while len(que)>0:
        nco,now=heapq.heappop(que)
        
        for can in L[now]:
            nex=can[0]
            cos=can[1]
            if sc[nex]>cos+nco:
                sc[nex]=cos+nco
                heapq.heappush(que,(cos+nco,nex))
                pre[nex]=now
    for i in range(1,n+1):
        if pre[i]!=i:
            a,b=i,pre[i]
            if a>b:
                a,b=b,a
            DIC[(a,b)]=1

ans=m
for val in DIC.values():
    ans-=val
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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])
    return d

##############################
n,m = map(int,input().split()) #n:頂点数  w:辺の数
lst=[]

d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    x,y,z = map(int,input().split())
    x-=1
    y-=1
    d[x][y] = z
    d[y][x] = z
    lst.append([x,y,z])
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

table=warshall_floyd(d)
ans=0

for x,y,z in lst:
    if table[x][y]!=z:
        ans+=1


print(ans)

Submission status: Accepted

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

from heapq import heappush, heappop
def dijkstra(n, graph, s):
    dist = [float('inf')] * n
    hq = [(0, s)]
    dist[s] = 0
    while hq:
        c, v = heappop(hq)
        if dist[v] < c:
            continue
        for t, cost in graph[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(hq, (dist[t], t))
    return dist

graph = [[] for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((b, c))
    graph[b].append((a, c))
    edges_used[(a, b, c)] = False
dist = [dijkstra(N, graph, i) for i in range(N)]

for edge in edges_used.keys():
    a, b, c = edge
    for i in range(N):
        if dist[i][a] == dist[i][b] + c or dist[i][b] == dist[i][a] + c:
            edges_used[edge] = True

ans = 0
for used in edges_used.values():
    if not used:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
E = set()
d = [[10**9]*N for k in range(N)]
for k in range(N):
    d[k][k] = 0
for k in range(M):
    a, b, c = map(int,input().split())
    E.add((a-1,b-1,c))
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
ans = 0
for e in E:
    if d[e[0]][e[1]] != e[2]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


N,M = map(int,input().split())
f = lambda x: (int(x[0])-1,int(x[1])-1,int(x[2]))
edges = list(f(input().split()) for _ in range(M))

g = np.zeros((N,N), dtype=float)

for a,b,c in edges:
    g[a,b] = c
    g[b,a] = c

floyd_warshall(g, directed=False, overwrite=True)

res = sum(int(g[a,b] != c) for a,b,c in edges)
print(res)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]

INF = float('inf')
ds = [[INF]*N for _ in range(N)]
for i in range(N):
    ds[i][i] = 0
for a,b,c in ABC:
    a,b = a-1,b-1
    ds[a][b] = ds[b][a] = c

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

ans = 0
for a,b,c in ABC:
    a,b = a-1,b-1
    if c != ds[a][b]:
        ans += 1
print(ans)

Submission status: Accepted

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

Solution code:
import copy
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

old_dp = copy.deepcopy(dp)
check = [[False] * N for _ in range(N)]
count = 0
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])

count = 0
for i in range(N):
    for j in range(N):
        if old_dp[i][j] != dp[i][j] and old_dp[i][j] != inf:
            count += 1

print(count // 2)

Submission status: Accepted

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 warshall_floyd(V, cost):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])


def main():
    N, M = in_nn()
    cost = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        cost[i][i] = 0

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

    warshall_floyd(N, cost)

    ans = set()
    for i in range(N):
        for j in range(i + 1, N):
            for e in edge:
                a, b, c = e
                if cost[i][j] == cost[i][a] + c + cost[b][j]:
                    ans.add((a, b))
                elif cost[i][j] == cost[i][b] + c + cost[a][j]:
                    ans.add((a, b))

    print(M - len(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
DP = [[float('inf')]*N for _ in range(N)]
B = []
for i in range(N):
  DP[i][i] = 0
for _ in range(M):
  a,b,c = map(int,input().split())
  DP[a-1][b-1] = c
  DP[b-1][a-1] = c
  B.append([a-1,b-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])   
ans = 0
for i in range(M):
    a,b,c = B[i]
    for j in range(N):
        if DP[j][b] == DP[j][a] + c:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
d = [[10**10]*N for i in range(N)]
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[a[i]][b[i]] = c[i]
  d[b[i]][a[i]] = c[i]
for i in range(N):
  d[i][i] = 0

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

ans = M
for i in range(M):
  tmp = 0
  for j in range(N):
    if d[j][a[i]] + c[i] == d[j][b[i]]:
      tmp = 1
  ans -= tmp
print(ans)