[白俊14431]少数の村

10491 ワード
パイ アルゴリズム#アルゴリズム# 白駿 金貨。 コーディングテスト テキストリンク

1.問題の説明


少数の村

2.問題分析


更新は、現在のノードと次のノードの間の距離が少ない場合にのみ使用できます.多特徴線アルゴリズムと素数判別アルゴリズムを混合して使用する.

3.私の回答

import sys
import heapq

INF = sys.maxsize
x1, y1, x2, y2 = map(int, sys.stdin.readline().rstrip().split())
nodes = []
nodes.append((x1, y1))
nodes.append((x2, y2))
n = int(sys.stdin.readline().rstrip())
for _ in range(n):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    nodes.append((x, y))

def is_prime(dist):
    if dist < 2: return False
    elif dist == 2: return True
    for i in range(2, int(dist**0.5)+1):
        if dist % i == 0: return False
    return True

def Dijkstra():
    distances = [INF for _ in range(n+2)]
    distances[0] = 0
    pq = []
    heapq.heappush(pq, [0, 0])

    while pq:
        cur_cost, cur_node = heapq.heappop(pq)
        cur_x, cur_y = nodes[cur_node]
        if distances[cur_node] < cur_cost: continue

        for next_node in range(n+2):
            next_x, next_y = nodes[next_node]
            next_cost = int(((cur_x-next_x)**2 + (cur_y-next_y)**2)**0.5)
            if is_prime(next_cost) and distances[next_node] > cur_cost + next_cost:
                distances[next_node] = cur_cost + next_cost
                heapq.heappush(pq, [cur_cost + next_cost, next_node])
    return distances[1]

ans = Dijkstra()
if ans == INF: print(-1)
else: print(ans)
オランダ国旗問題は3つの部分leecodeに分かれています
最近NSInvocationの使い方を聞かれたので、NSInvocationの小さな例を書きました