Problem: 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.

Submission attempts (in order):

class Graph():
    
    def __init__(self,vertex_num,node_num,naive_input):
        self.vertex_num=vertex_num
        self.node_num=node_num
        
        
        node=[[] for _ in range(vertex_num)]
        for i in range(node_num):
            u,v=naive_input[i][:2]
            w=naive_input[i][2]
            node[u].append([v,i,w])
            node[v].append([u,i,w])
        self.node=node
        
        self.node_num_arr=list(map(lambda x:len(x),node))
    
    def bfs(self,s=0):
        
        def cal_distance(now_edge,next_edge_info,distance_arr,before_vertex_arr,queue,l_ind):
            next_edge=next_edge_info[0]
            weight=next_edge_info[2]
            cal_distance_val=distance_arr[now_edge]+weight
            if before_vertex_arr[next_edge]==-1:
                    queue[l_ind]=next_edge
                    #print("queue is updated")
                    l_ind+=1
            if cal_distance_val<distance_arr[next_edge]:
                
                distance_arr[next_edge]=cal_distance_val
                before_vertex_arr[next_edge]=now_edge
                
                
                #print(distance_arr)
                
                
            return l_ind

        
        q=[-1 for _ in range(self.vertex_num)]
        
        
        
        #cal_node_num_arr=self.node_num_arr.copy()
        now_ind=0
        q[now_ind]=s
        last_ind=1


        distance=[float("inf") for _ in range(self.vertex_num)]
        distance[s]=0
        before_vertex=[-1 for _ in range(self.vertex_num)]
        before_vertex[s]=s
        index_arr=[-1 for _ in range(self.node_num)]

        while last_ind<self.vertex_num:
            now_edge=q[now_ind]
            
            for next_edge_info in self.node[now_edge]:
                
                #cal_node_num_arr[now_edge]-=1
                #cal_node_num_arr[next_edge]-=1
                #q[last_ind]=next_edge
                
                

                

                last_ind=cal_distance(now_edge,next_edge_info,distance,before_vertex,q,last_ind)
                
            now_ind+=1
        
        return distance

n,m=list(map(int,input().split()))
"""
maze=[[i for i in input()] for _ in range(n)]
graph=[[] for _ in range(n*m)]
q_num=0
for i in range(n):
    for j in range(m):
        if maze[i][j]=="#":
            continue
        ind=i*m+j
        q_num+=1
        #move[i][j]=ind
        if i!=0:
            if maze[i-1][j]!="#":
                graph[ind].append((i-1)*m+j)
        if i!=n-1:
            if maze[i+1][j]!="#":
                graph[ind].append((i+1)*m+j)
        if j!=0:
            if maze[i][j-1]!="#":
                graph[ind].append(i*m+j-1)
 
        if j!=m-1:
            if maze[i][j+1]!="#":
                graph[ind].append(i*m+j+1)

a=[]
for num,i in enumerate(graph):
    for j in i:
        a.append([num,j,1])
#print(a)
tmp=0
for i in maze:
    for j in i:
        if j==".":
            tmp+=1
n=tmp
m=len(a)
"""
a=[list(map(int,input().split())) for _ in range(m)]
a=list(map(lambda x:[x[0]-1,x[1]-1,x[2]],a))
G=Graph(n,m,a)
ans=0
for i in range(n):
    cal=G.bfs(i)

#made in 2019/7/1
#modified in 2020/2/14
class Node:
    def __init__(self):
        self.next={}
    def get_data(self,new_next,weight=1):
        self.next[new_next]=weight



def dijkstra():
    total=0
    node_cost=[float("inf") for i in range(0,N)]
    now=[E-1]
    node_cost[now[0]]=0
    check=[i for i in range(0,N)]
    check.remove(E-1)
    next_node=node[now[0]].next.keys()
    while len(check):
        total+=1
        tmp=[]
        #print("now", now)
        for each in now:
            next_node=node[each].next.keys()
            for i in next_node:
                val=node[each].next[i]+node_cost[each]
                if node_cost[i]>val:
                    node_cost[i]=val
                    if i in check:
                        #check.remove(i)
                        #tmp.extend(node[i].next.keys())
                        tmp.append(i)
        now=tmp
        #print("next... ",tmp)
        #print("now...",node_cost)
        if len(now)==0:
            break
        
    print(node_cost)
    print("min_cost:",node_cost[S-1])
    



def BFS():
    total=0
    #print("start bfs")
    check_node=[i for i in range(0,N)]
    now=S-1
    tmp=[now]
    check_node.remove(now)
    new_tmp=[]
    while len(check_node)>0:
        #print("tmp:{}".format(tmp))
        total+=1
        for each in tmp:
            #print("each:{}".format(each))
            for i in node[each].next.keys():
                k=i
                #print(k)
                if k in check_node:
                    #print("append :{}".format(k))
                    new_tmp.append(k)
                    check_node.remove(k)
        #print("new_tmp:{}".format(new_tmp))
        #print("check_node:{}".format(check_node))
        tmp=new_tmp
        new_tmp=[]
    print("end")
    print("loop time:{}".format(total))
    







        
        


#??
N,M=list(map(int,input().split()))
#S,E=list(map(int,input().split()))
node=[Node() for _ in range(N)]
ans=[[100 for _ in range(N)]for _ in range(N)]
for i in range(M):
    tmp_p,tmp_n,tmp_w=list(map(int,input().split()))
    node[tmp_p-1].get_data(tmp_n-1,tmp_w)
    node[tmp_n-1].get_data(tmp_p-1,tmp_w)
#BFS()
a_num=ord("a")
for i in range(N):
    
    S=i+1
    E=i+1
    dijkstra()
    print()



import heapq
class Graph():
    def __init__(self,vertex_num,node_num,naive_input,start_zero=True,direction=False):
        self.vertex_num=vertex_num
        self.node_num=node_num
        
        
        node=[{} for _ in range(vertex_num)]
        for i in range(node_num):
            u,v,w=naive_input[i]
            if not start_zero:
                u-=1
                v-=1
            node[u][v]={"weight":w,"index":i}
            #node[v][u]={"weight":w,"index":i}
            if not direction:
                node[v][u]={"weight":w,"index":i}
                #node[u][v]["reverse"]={"weight":w,"index":i}
        self.node=node
        
        self.node_num_arr=list(map(lambda x:len(x),node))

    def djikstra(self,s=0):
        distance=[float("inf") for _ in range(self.vertex_num)]
        distance[s]=0
        
        
        
        
        visited_vertex={s}
        before_vertex=[float("inf") for _ in range(self.vertex_num)]
        node_index_arr=[float("inf") for _ in range(self.vertex_num)]
        while len(visited_vertex)<self.vertex_num:
            
            will_visit_node=set()
            for now_node_num in visited_vertex:
                for next_node_num in self.node[now_node_num].keys():
                    if next_node_num in visited_vertex:
                        continue
                    will_visit_node.add(next_node_num)
                    next_node=self.node[now_node_num][next_node_num]
                    cal_d=distance[now_node_num]+next_node["weight"]
                    if cal_d<distance[next_node_num]:
                        distance[next_node_num]=cal_d
                        before_vertex[next_node_num]=now_node_num
                        node_index_arr[next_node_num]=next_node["index"]
                    
                    #heapq.heappush(min_distance_heap,distance[next_node_num])
            
            add_vertex=[float("inf"),float("inf")]
            for i in will_visit_node:
                if distance[i]<add_vertex[1]:
                    add_vertex[0]=i
                    add_vertex[1]=distance[i]
            visited_vertex.add(add_vertex[0])
        return node_index_arr
        





n,m=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(m)]
G=Graph(n,m,a,start_zero=False)  
ans=[True for _ in range(m)]
for i in range(n):
    tmp=G.djikstra(i)
    for j in tmp:
        if j!=float("inf"):
            ans[j]=False

print(sum(ans))

            


Verdicts: Wrong Answer

Wrong Answer

Accepted