Submission #42043871

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# dijkstra
import heapq
########################################
class bellmanFord():
    INF = float("inf")
    def __init__(self, v):
        self.numv = v
        self.distance = [self.INF] * v
        self.e = [[] for _ in range(v)]
    def makeEdge(self, s, t, cost):
        self.e[s].append((t, cost))
        self.e[t].append((s, cost))
    def solve(self, s):
        self.distance[s] = 0
        negativeCycle = False
        for i in range(self.numv):
            for curNode in range(self.numv):
                for nextNode, cost in self.e[curNode]:
                    if self.distance[curNode] == self.INF:
                        continue
                    if self.distance[nextNode] > self.distance[curNode] + cost:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

# dijkstra
import heapq
########################################
class bellmanFord():
    INF = float("inf")
    def __init__(self, v):
        self.numv = v
        self.distance = [self.INF] * v
        self.e = [[] for _ in range(v)]
    def makeEdge(self, s, t, cost):
        self.e[s].append((t, cost))
        self.e[t].append((s, cost))
    def solve(self, s):
        self.distance[s] = 0
        negativeCycle = False
        for i in range(self.numv):
            for curNode in range(self.numv):
                for nextNode, cost in self.e[curNode]:
                    if self.distance[curNode] == self.INF:
                        continue
                    if self.distance[nextNode] > self.distance[curNode] + cost:
                        isUpdate = True
                        self.distance[nextNode] = self.distance[curNode] + cost
                        if i == self.numv - 1:
                            negativeCycle = True
                            break
        if negativeCycle:
            return -1
        return self.distance
########################################
n, d = map(int, input().split())
dat = []
for _ in range(n): dat.append(tuple(map(int, input().split())))
dj = bellmanFord(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 cost[i] != dj.INF else "No")

Submission Info

Judge Result