Submission #42043422

---

Source Code Expand

# dijkstra
import heapq
########################################
class dijkstra():
    INF = float("inf")
    def __init__(self, numV):
        self.numV = numV
        self.e = [[] for _ in range(numV)]
    def makeEdge(self, s, t, cost):
        self.e[s].append((t, cost))
        self.e[t].append((s, cost))
    def solve(self, nodeS):
        self.cost = [self.INF] * self.numV # cost
        self.parent = [-1] * self.numV # parent node
        q = [(0, nodeS)]  # 初期ノード(cost 0)
        self.cost[nodeS] = 0
        heapq.heapify(q)
        while len(q) > 0:
            curcost, curnode = heapq.heappop(q)
            if curcost > self.cost[curnode]:
                continue
            for nextnode, edgecost in self.e[curnode]:
                nextcost = curcost + edgecost
                if self.cost[nextnode] > nextcost:
                    self.cost[nextnode] = nextcost
                    self.parent[nextnode] = curnode
                    heapq.heappush(q, (nextcost, nextnode))
########################################
n, d = map(int, input().split())
dat = []
for _ in range(n): dat.append(tuple(map(int, input().split())))
dj = dijkstra(n)
for i in range(n):
    x1, y1 = dat[i]
    for j in range(i+1, n):
        x2, y2 = dat[j]
        if (x1-x2)**2 + (y1-y2)**2 <= (d**2):
            dj.makeEdge(i, j, 1)
cost = dj.solve(0)
for i in range(n): print("Yes" if dj.cost[i] != dj.INF else "No")

Submission Info

Judge Result