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: Runtime Error

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

# print(N, M, ABC)

max_len = 0
for abc in ABC:
    max_len += abc[2]

def sub(a, b, d, d_min, ABC, path):
    # print('sub', a, b, d, d_min, ABC, path)
    for abc in ABC:
        # print('sub', abc)
        if abc[0] == a:
            n_a = abc[1]
            tmp_d = d + abc[2]
            if tmp_d > d_min:
                # print('exceed', d, d_min)
                continue
            if n_a == b:
                path.append(n_a)
                # print('found', tmp_d, path)
                return tmp_d
            tmp = [x for x in path]
            tmp.append(n_a)
            tmp_d = sub(n_a, b, tmp_d, d_min, ABC, tmp)
            if tmp_d > d_min:
                # print('exceed2', tmp_d, d_min)
                continue
        if abc[1] == a:
            n_a = abc[0]
            tmp_d = d + abc[2]
            if tmp_d > d_min:
                # print('exceed', tmp_d, d_min)
                continue
            if n_a == b:
                path.append(n_a)
                # print('found', tmp_d, path)
                return tmp_d
            tmp = [x for x in path]
            tmp.append(n_a)
            tmp_d = sub(n_a, b, tmp_d, d_min, ABC, tmp)
            if tmp_d > d_min:
                # print('exceed2', tmp_d, d_min)
                continue
    # print('not found')
    path = []
    return max_len

def shortest(a, b, ABC):
    d_min = max_len
    ans = []
    for abc in ABC:
        # print('shortest', a, b, abc)
        if abc[0] == a:
            n_a = abc[1]
            d = abc[2]
            path = [a, n_a]
            if n_a == b and d <= d_min:
                d_min = d
                ans = [path]
                continue
            d = sub(n_a, b, d, d_min, ABC, path)
            if d <= d_min:
                # print('shortest, found', d, path)
                d_min = d
                ans = [path]
            if d == d_min:
                ans.append(path)
        if abc[1] == a:
            n_a = abc[0]
            d = abc[2]
            path = [a, n_a]
            if n_a == b and d <= d_min:
                d_min = d
                ans = [path]
                continue
            d = sub(n_a, b, d, d_min, ABC, path)
            if d < d_min:
                # print('shortest, found', d, path)
                d_min = d
                ans = [path]
            if d == d_min:
                ans.append(path)
    return ans

# print(shortest(1, 2, ABC))
# print(shortest(1, 3, ABC))
# print(shortest(2, 3, ABC))

s_paths = set()

for i in range(N):
    for j in range(i + 1, N):
        paths = shortest(i + 1, j + 1, ABC)
        # print(i, j, paths)
        for path in paths:
            # print(path)
            for k in range(len(path) - 1):
                l = min(path[k], path[k + 1])
                r = max(path[k], path[k + 1])
                s_paths.add((l, r))

print(len(ABC) - len(s_paths))

Submission status: Runtime Error

Solution code:
import copy

def warshall_floyd(V, E):
    INF = 10 ** 9
    d = [[[INF, []] for j in range(V + 1)] for i in range(V + 1)]
    for i, j, c in E:
        d[i][j] = [c, []]
        d[j][i] = [c, []]
    for k in range(1, V + 1):
        for i in range(1, V):
            for j in range(i, V + 1):
                dk = d[i][k][0] + d[k][j][0]
                if d[i][j][0] > dk:
                    root = copy.copy(d[i][k][1]) + [k] + copy.copy(d[k][j][1])
                    d[i][j] = [dk, root]
                    d[j][i] = [dk, root]
    return d

n, m = map(int, input().split())
E = [[None for j in range(n + 1)] for i in range(n + 1)]
E_list = []
for i in range(m):
    a, b, c = map(int, input().split())
    E_list.append([a, b, c])
    E[a][b] = 0
    E[b][a] = 0
d = warshall_floyd(n, E_list)
ans = m
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        k = i
        for r in d[i][j][1]:
            if E[r][k] == 0:
                ans -= 1
            E[r][k] += 1
            E[k][r] += 1
            k = r
        if E[j][k] == 0:
            ans -= 1
        E[j][k] += 1
        E[k][j] += 1
print(ans)

Submission status: Runtime Error

Solution code:
def main():
	N, M = map(int, input().split())
	points = [[] for _ in range(N+1)]
	for i in range(1, M+1):
		a, b, c = map(int, input().split())
		points[a].append([b, c, i])
		points[b].append([a, c, i])
	use = set()
	def dijksta(start):
		is_visited = [False]*(N+1)
		is_visited[0] = True
		is_visited[start] = True
		stack = list(points[start])
		while stack:
			stack.sort(key=lambda x: x[1])
			use_edge = stack.pop()
			cur = use_edge[0]
			dist = use_edge[1]
			use.add(use_edge[2])
			is_visited[cur] = True
			if all(is_visited):
				break
			add_stack = list(points[cur])
			removes = []
			for i, pair in enumerate(add_stack):
				if is_visited[pair[0]]:
					removes.append(i)
					continue
				add_stack[i][1] += dist
			removes.reverse()
			for i in removes:
				add_stack.pop(i)
			stack.extend(add_stack)
	for i in range(1, M+1):
		dijksta(i)
	ans = M - len(use)
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
	N, M = map(int, input().split())
	points = [[] for _ in range(N+1)]
	for i in range(1, M+1):
		a, b, c = map(int, input().split())
		points[a].append([b, c, i])
		points[b].append([a, c, i])
	use = set()
	def dijksta(start):
		is_visited = [False]*(N+1)
		is_visited[0] = True
		is_visited[start] = True
		stack = list(points[start])
		edge = 0
		while stack:
			edge += 1
			stack.sort(key=lambda x: x[1])
			use_edge = stack.pop()
			cur = use_edge[0]
			dist = use_edge[1]
			use.add(use_edge[2])
			is_visited[cur] = True
			if all(is_visited):
				return edge
			add_stack = list(points[cur])
			removes = []
			for i, pair in enumerate(add_stack):
				if is_visited[pair[0]]:
					removes.append(i)
					continue
				add_stack[i][1] += dist
			removes.reverse()
			for i in removes:
				add_stack.pop(i)
			stack.extend(add_stack)
	for i in range(1, M+1):
		dijksta(i)
	ans = M - len(use)
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
	N, M = map(int, input().split())
	points = [[] for _ in range(N+1)]
	for i in range(1, M+1):
		a, b, c = map(int, input().split())
		points[a].append([b, c, i])
		points[b].append([a, c, i])
	is_visited = [False]*(N+1)
	is_visited[0] = True
	use = set()
	def dijksta(start):
		is_visited[start] = True
		stack = list(points[start])
		edge = 0
		while stack:
			edge += 1
			stack.sort(key=lambda x: x[1])
			use_edge = stack.pop()
			cur = use_edge[0]
			dist = use_edge[1]
			use.add(use_edge[2])
			is_visited[cur] = True
			if all(is_visited):
				return edge
			add_stack = list(points[cur])
			removes = []
			for i, pair in enumerate(add_stack):
				if is_visited[pair[0]]:
					removes.append(i)
					continue
				add_stack[i][1] += dist
			removes.reverse()
			for i in removes:
				add_stack.pop(i)
			stack.extend(add_stack)
	for i in range(1, M+1):
		dijksta(i)
	ans = M - len(use)
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

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

MAX = 10**10
dist = np.zeros((N,N))
dist += MAX

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

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

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

ans = 0
for i in range(M):
    if dist[a[i], b[i]] < c[i]:
        ans += 1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

MAX = 10**10
dist = [[MAX for j in range(N)] for i in range(N)]

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

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

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

ans = 0
for i in range(M):
    if dist[a[i]][b[i]] < c[i]:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

n, m = map(int, input().split())
a = [None] * n
b = [None] * n
c = [None] * n


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

wf = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    wf[i][i] = 0
for i in range(m):
    wf[a[i]][b[i]] = wf[b[i]][a[i]] = c[i]

for k, i, j in itertools.product(range(n), repeat=3):
    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

ans = 0
for x in range(m):
    used = False
    for i, j in itertools.product(range(n), repeat=2):
        if wf[i][a[x]] + c[x] + wf[b[x]][j] == wf[i][j] or wf[i][b[x]] + c[x] + wf[a[x]][j] == wf[i][j]:
            used = True
    
    if not used:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
class Dijkstra: # 最短経路問題
    def __init__(self, route_map, start_point, goal_point=None):
        self.route_map = route_map #
        self.start_point = start_point # スタート位置
        self.goal_point = goal_point

    def execute(self):
        import heapq
        num_of_city = len(self.route_map) # ノード数
        dist = [float("inf") for _ in range(num_of_city)] # startからの距離を格納する
        prev = [float("inf") for _ in range(num_of_city)] # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる

        dist[self.start_point] = 0 # スタート位置までのコストは0
        heap_q = [] # 優先度つきキュー
        heapq.heappush(heap_q, (0, self.start_point)) # タプル(0,スタート位置)をheap_qに追加
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q) # 直前にheap_qに入れたタプルから取り出す(src＝ソース)

            if dist[src] < prev_cost: # もし、スタート位置からsrcまでの距離がprev_costより小さいなら問題ないのでok
                continue

            for dest, cost in self.route_map[src].items(): # destはsrcから行ける頂点(目的地)
                if cost != float("inf") and dist[dest] > dist[src] + cost: # もし、destに有限のコストで行けて、srcからdestに行くのがスタートからの現状の最短距離になるなら、
                    dist[dest] = dist[src] + cost # 更新する
                    heapq.heappush(heap_q, (dist[dest], dest)) # 更新したのでheap_qに入れておく。次のノードに移動した時に取り出して無駄な変更がないか確認する
                    prev[dest] = src
        if self.goal_point is not None: # ゴールまでの最短経路を返す
            return self.get_path(self.goal_point, prev)
        else: # スタートから各頂点までの最短距離を格納したリストを返す
            return dist

    def get_path(self, goal, prev):  # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる
        global edge_num
        global used_edge
        path = [goal]
        dest = goal
        
        while prev[dest] != float("inf"): # prev[start]はfloat("inf")になり、停止する
            used_edge[edge_num[prev[dest]][dest]] += 1
            path.append(prev[dest]) # 後ろから戻っていく
            dest = prev[dest]

        return list(reversed(path)) # 逆から辿ったので順を元に戻す

import sys
input = sys.stdin.readline


N,M = map(int,input().split())
route_map = [dict() for _ in range(N)]
edge_num = [dict() for _ in range(N)]
for i in range(M): # M == エッジの数
    u, v, cost = map(int, input().split()) # cost は 辺　u -> v の重み(距離,コスト)
    u, v = u - 1, v - 1
    route_map[u][v] = cost # route_mapの第u番目のdictに{v:cost}が入る
    route_map[v][u] = cost # route_mapの第v番目のdictに{u:cost}が入る
    edge_num[u][v] = i # redge_numの第u番目のdictに{v:i}が入る
    edge_num[v][u] = i # redge_numの第v番目のdictに{u:i}が入る


used_edge = [0 for _ in range(M)]
checked_node = [[0 or _ in range(N)] for __ in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        if checked_node[i][j] != 0:
            continue
        dijkstra_result1 = Dijkstra(route_map, i, j).execute()
        dijkstra_result2 = Dijkstra(route_map, N-1-i, N-1-j).execute()
        for k in range(len(dijkstra_result1)-1):
            for l in range(k+1,len(dijkstra_result1)):
                checked_node[dijkstra_result1[k]][dijkstra_result1[l]] += 1
        for k in range(len(dijkstra_result2)-1):
            for l in range(k+1,len(dijkstra_result2)):
                checked_node[dijkstra_result2[k]][dijkstra_result2[l]] += 1

ans = used_edge.count(0)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
import copy

V, M = map(int, input().split())
d = [0] * V
prev = [0] * V

cost = [[INF] * V for i in range(V)]
for i in range(M):
    a, b, c = map(int,  input().split())
    cost[a - 1][b - 1] = c
    cost[b - 1][a - 1] = c
    
def dijkstra_back(s, t):
    for i in range(V):
        prev[i] = s
        d[i] = float('inf')
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
         
        for i in range(V):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                heapq.heappush(h, [d[i], 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

cost2 = copy.deepcopy(cost)
for i in range(V - 1):
    for j in range(i + 1, V):
        g = dijkstra_back(i, j)
        # print(i, j, g)
        for k in range(len(g) - 1):
            cost2[g[k]][g[k + 1]] = INF
            cost2[g[k + 1]][g[k]] = INF
            
cnt = 0
for i in range(V):
    for j in range(V):
        if cost2[i][j] != INF:
            cnt += 1
                     
print(cnt // 2)

Submission status: Runtime Error

Solution code:
def gen_graph(input_list):
    graph = {}

    for item in input_list:
        if not item[0] in graph:
            graph[item[0]] = {}
        if not item[1] in graph:
            graph[item[1]] = {}
        graph[item[0]][item[1]] = item[2]
        graph[item[1]][item[0]] = item[2]

    return graph


def get_lowest_cost_vertex(costs, processed):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


def get_best_routes(graph, start):
    costs = {}
    parents = {}
    processed = []

    costs[start] = 0
    parents[start] = None
    processed.append(start)

    for item in graph[start].keys():
        costs[item] = graph[start][item]
        parents[item] = start

    for item in graph.keys():
        if not (item in costs.keys() or item == start):
            costs[item] = float("inf")
            parents[item] = None

    node = get_lowest_cost_vertex(costs, processed)

    while node is not None:
        cost = costs[node]
        neighbors = graph[node]

        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        node = get_lowest_cost_vertex(costs, processed)

    routes = []
    for item in graph.keys():
        if item != start:
            route = []
            route.append(item)
            parent = parents[item]
            while 1:
                route.append(parent)
                if parent == start:
                    break
                parent = parents[parent]
            route.reverse()
            routes.append(route)
    return routes


def main(vertex_count, input_list):
    graph = gen_graph(input_list)

    routes = []
    for start in range(1, vertex_count+1):
        for route in get_best_routes(graph, start):
            routes.append(route)

    route_strs = []
    for route in routes:
        route_strs.append(''.join(list(map(str, route))))

    side_strs = []
    for item in input_list:
        side_strs.append(str(item[0]) + str(item[1]))
        side_strs.append(str(item[1]) + str(item[0]))

    count = 0
    route_strs_joined = '/'.join(route_strs)

    for side_str in side_strs:
        if route_strs_joined.find(side_str) == -1:
            count += 1

    return count / 2


if __name__ == "__main__":
    vertex_count, sides_count = list(map(int, input().split()))
    input_list = []
    for _ in sides_count:
        vertex_1, vertex_2, distance = list(map(int, input().split()))
        input_list.append((vertex_1, vertex_2, distance))
    print(main(vertex_count, input_list))

Submission status: Runtime Error

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

bools = [False for i in range(n)]

dp =[[[0,[]] for i in range(n)] for i in range(n)]

for i in range(len(abc)):
    a=abc[i][0]
    b=abc[i][1]
    c=abc[i][2]
    a=a-1
    b=b-1
    dp[a][b][0]=dp[a][b][0]+c
    dp[b][a][0]=dp[b][a][0]+c
    dp[a][b][1]=[i]
    dp[b][a][1]=[i]

for i in range(n):
    for j in range(i,n):
        if dp[i][j][0]>0:
            for cand in range(n):
                if dp[i][cand][0]>0:
                    if dp[j][cand][0]>=dp[i][cand][0]+dp[i][j][0]:
                        dp[j][cand][0]=dp[i][cand][0]+dp[i][j][0]
                        dp[j][cand][1]=dp[i][cand][1]+dp[i][j][1]
                    if dp[i][cand][0]>=dp[j][cand][0]+dp[i][j][0]:
                        dp[i][cand][0]=dp[j][cand][0]+dp[i][j][0]
                        dp[i][cand][1]=dp[j][cand][1]+dp[i][j][1]

for i in range(n):
    for j in range(i,n):
        for x in dp[i][j][1]:
            bools[x]=True 

count=0
for i in range(n):
    if bools[i]==False:
        count+=1
print(count)

Submission status: Runtime Error

Solution code:
n,m =map(int,input().split())
inf = 10**15

dist = [[inf for i in range(n)] for i in range(n)]
route = [[ [] for i in range(n)] for i in range(n)]
import copy

for i in range(m):
    ak,bk,ck = map(int,input().split())
    dist[ak-1][bk-1]  =ck
    dist[bk-1][ak-1]  =ck

for i in range(n):
    for k in range(n):
        route[i][k] = [i,k]
        route[k][i] = [k,i]

for a in range(n):
    for b in range(n):
        for c in range(n):
            if dist[b][a]+dist[a][c] < dist[b][c]:
                if route[b][a] == None:
                    route[b][c] = copy.deepcopy(route[a][c])[1:]
                else:
                    route[b][c] = copy.deepcopy(route[b][a]).extend(copy.deepcopy(route[a][c])[1:])
                dist[b][c] =  dist[b][a]+dist[a][c]

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

print(m-ans//2)

Submission status: Runtime Error

Solution code:
n,m =map(int,input().split())
inf = 10**15

dist = [[inf for i in range(n)] for i in range(n)]
route = [[ [] for i in range(n)] for i in range(n)]
import copy

for i in range(m):
    ak,bk,ck = map(int,input().split())
    dist[ak-1][bk-1]  =ck
    dist[bk-1][ak-1]  =ck

for i in range(n):
    for k in range(n):
        route[i][k] = [i,k]
        route[k][i] = [k,i]

for a in range(n):
    for b in range(n):
        for c in range(n):
            if dist[b][a]+dist[a][c] < dist[b][c]:
                route[b][c] = copy.deepcopy(route[b][a]).extend(copy.deepcopy(route[a][c])[1:])
                dist[b][c] =  dist[b][a]+dist[a][c]
ans = 0
for i in range(n):
    for k in range(n):
        if route[i][k]:
            ans += 1

print(m-ans//2)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
abc = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]

#res = [[9999999 for _ in range(n)] for _ in range(n)]

e = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    e[a][b] = [c, i]
    e[b][a] = [c, i]

ans = set()

for i in range(n-1):
    for j in range(i + 1, n):
        temp = [[0, i]]
        res = []
        for k in range(n):
            next = []
            for x in temp:
                if x[1] == j:
                    res.append(x)
                    continue
                for z in e[x[1]].keys():
                    if len(x) == 2:
                        next.append([ x[0] + e[x[1]][z][0], z ] + [ e[x[1]][z][1] ])
                    else:
                        next.append([ x[0] + e[x[1]][z][0], z ] + x[2:] + [ e[x[1]][z][1] ])
            temp = [] + next
        mr = 99999999
        p = 0
        for i in range(len(res)):
            if res[i][0] < mr:
                mr = res[i][0]
                p = i
        #print(set(res[p][2:]))
        ans = ans | set(res[p][2:])

print(m - len(ans))

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def dd(N, abc, ne_table, start_i):
    used_edge = set()
    pivot = start_i

    kouho = {start_i: (0, 0, True)}  # value: (d, path,kakutei)

    for _ in range(N - 1):

        current_dist, path, kaku = kouho[pivot]
        assert kaku
        edges_i = ne_table[pivot]  # エッジリスト取得
        for i in edges_i:
            a, b, weight = abc[i]
            target = a if a != pivot else b

            if target in kouho:
                tmp_d, tmp_path, kakutei = kouho[target]
                if kakutei:
                    continue
                if current_dist + weight < tmp_d:  # 更新
                    kouho[target] = (current_dist + weight, i, False)
                continue
            kouho[target] = (current_dist + weight, i, False)

        min_kouho = min([(k, d, p) for k, (d, p, kakutei) in kouho.items() if not kakutei], key=lambda q: q[1])
        min_kouho_i = min_kouho[0]
        used_edge.add(min_kouho[2])
        kouho[min_kouho_i] = (*kouho[min_kouho_i][:2], True)
        pivot = min_kouho_i
    return used_edge


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

    def pre(a, b, c):
        return a - 1, b - 1, c

    abc = [
        pre(*[int(a) for a in input().split()])
        for _ in range(M)
    ]

    ne_table = defaultdict(lambda: [])
    for i, (a, b, c) in enumerate(abc):
        ne_table[a].append(i)
        ne_table[b].append(i)

    total_used = set()

    for i in range(N):
        used = dd(N, abc, ne_table, i)
        total_used.update(used)

    print(M - len(total_used))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
sx,sy,tx,ty = map(int, input().split())

ans = ""

#UP
ans += "U" * (ty-sy)
ans += "R" * (tx-sx)
ans += "D" * (ty-sy)
ans += "L" * (tx-sx)
ans += "L" + "U"* (ty-sy+1) + "R" * (tx-sx+1) + "D"
ans += "R" + "D" * (ty-sy+1) + "L"*(tx-sx+1) + "U"

print(ans)

Submission status: Runtime Error

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

import numpy as np
dists = np.ones((n + 1, n + 1)) * (10 ** 6)
edges = []
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
    edges.append(a, b, c)
for i in range(1, n + 1):
    dists[i, i] = 0
for i in range(1, 1 + n):
    dists = np.minimum(dists, dists[i: i + 1] + dists[:, i: i + 1])
cnt = 0
for a, b, c in edges:
    if dists[a, b] < c:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque
sx,sy,tx,ty = map(int,input().split())
ans_list = []
(tx,ty) = (tx-sx,ty-sy); (sx,sy) = (0,0)
H,W = ty+3,tx+3
visited = [[0]*(tx+3) for i in range(ty+3)]
d = [[1,0],[0,1],[-1,0],[0,-1]]
(sx,sy) = (sx+1,sy+1); (tx,ty) = (tx+1,ty+1)
def bfs(si,sj,gi,gj):
    tr = [[si,sj]]
    q = deque([[si,sj,tr]])
    while q:
        i,j,tr = q.popleft()
        if (i,j) == (gi,gj):
            return tr
        for di,dj in d:
            ni = i + di; nj = j + dj
            if 0 <= ni <= H-1 and 0 <= nj <= W-1 and visited[ni][nj] == 0:
                visited[ni][nj] = 1
                ntr = tr[:]; ntr.append([ni,nj])
                q.append([ni,nj,ntr])

def change(tr):
    def func(d):
        if d == (1,0):return "U"
        if d == (-1,0):return "D"
        if d == (0,-1):return "L"
        if d == (0,1):return "R"
    for i in range(len(tr)-1):
        (ni,nj) = (tr[i+1][0],tr[i+1][1])
        (i,j) = (tr[i][0],tr[i][1])
        d = (ni-i,nj-j)
        ans_list.append(func(d))

tr = []
for cnt in range(2):
    res = bfs(sy,sx,ty,tx)
    for k in range(1,len(res)):
        i,j = res[k][0],res[k][1]
        rei, rej = ty + sx - i, tx + sy - j
        res.append([rei,rej])
    if cnt == 0:
        tr += res
    else:
        tr += res[1:]
    visited = [[0]*W for i in range(H)]
    for i,j in tr:
        visited[i][j] = 1
    visited[ty][tx] = 0

change(tr)
ans = "".join(ans_list)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
import math

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = {}
    for i in range(N):
        graph[i] = {}
        for j in range(N):
            graph[i][j] = 0
    for edge in edges:
        a, b, c = edge
        graph[a][b] = c
        graph[b][a] = c
    return graph

def Dijkstra(graph, start):
    N = len(graph)
    d = {}
    prev = {}
    for i in range(N):
        prev[i] = None
        if i == start:
            d[i] = 0
        else:
            d[i] = math.inf
    Q = []
    heapq.heappush(Q, (0, start))
    while Q:
        d_u, u = heapq.heappop(Q)
        if d[u] < d_u:#ダブりを回避
            continue
        for i in range(N):
            if graph[u][i]:
                temp = d_u + graph[u][i]
                if d[i] > temp:
                    d[i] = temp
                    prev[i] = u
                    heapq.heappush(Q, (d[i], i))
    return (d, prev)

def saitan(start, goal, d, prev):
    temp = goal
    res = [goal]
    while True:
        res.append(prev[temp])
        if prev[temp] == start:
            break
        else:
            temp = prev[temp]
    return res

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

graph = make_Graph(N, edges)

res = []
for i in range(N):
    d, prev = Dijkstra(graph, i)
    for j in range(N):
        if i != j:
            sait = saitan(i, j, d, prev)
            for k in range(len(sait) - 1):
                res.append(  (min(sait[k], sait[k + 1]) , max(sait[k], sait[k + 1]) ) )

res = set(res)
print(M - len(res))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import dijkstra
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
for i in range(m):
    a,b,t=map(int,input().split())
    dis[a-1][b-1]=t
    dis[b-1][a-1]=t
cost=dijkstra(dis,directed=False,unweighted=False)
cnt=0
for i,j,k in dis:
    if k>costs[i-1][j-1]:
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
#ダイクストラ法
V, E=map(int,input().strip().split(' '))
inf=10**9
cost=[[inf]*V for i in range(V)]
edge=[]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
    edge.append([fr-1,to-1])
    
d=[]
for i in range(V):
    d.append(dijkstra(i))

cand=E
for i in range(E):
    fl=False
    for j in range(V):
        for k in range(V):
            if d[j][edge[i][0]]==cost[edge[i][0]][edge[i][1]]+d[k][edge[i][1]]:
                cand-=1
                fl=True
                break
        if fl:
            break

print(cand)

def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
Islands=[[] for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1].append([b-1,c])
  Islands[b-1].append([a-1,c])
  Edge.append([a-1,b-1])
for m in range(M):
  a=Edge[m][0]
  b=Edge[m][1]
  for i in Islands[a]:
    if i[0]==b:
      c_m=i[1]
  List=[[a,-1]]
  for l in List:
    c=(-1)*(l[-1]+1)
    if l[-2]==b:
      if c_m>c:
        S+=1
        break
    else:        
      for n in Islands[l[-2]]:
        if n[0] in l:
          pass
        else:
          c+=n[1]
          del l[-1]
          List.append(l+[n[0],(-1)*(c+1)])
          
print(S)

Submission status: Runtime Error

Solution code:
# ABC 051 D
INF = 7+10**9
N, M = map(int,input().split())
P = []
D = [[INF for k in range(N)] for l in range(N)]
for k in range(N):
    D[k][k] = 0
for k in range(M):
    a, b, c = map(int,input().split())
    P.append([a-1,b-1,c])
    D[a-1][b-1] = c
    D[b-1][a-1] = c

# Floyd-Warshall
for k in range(M):
    for l in range(M):
        for m in range(M):
            D[l][m] = min(D[l][m], D[l][k]+D[k][m])

ans = M
for p in P:
    a, b, c = p[0], p[1], p[2]
    for k in range(N):
        if D[a][k] + c == D[b][k]:
            ans -= 1
            break 
print(ans)