Submission #4623741
Source Code Expand
from collections import defaultdict from heapq import heappop, heappush class Graph(object): def __init__(self): self.graph = defaultdict(list) def __len__(self): return len(self.graph) def add_edge(self, a, b, w): self.graph[a].append((b, w)) def get_nodes(self): return self.graph.keys() class Dijkstra(object): def __init__(self, graph, s): self.g = graph.graph self.dist = defaultdict(lambda: float('inf')) self.dist[s] = 0 self.prev = defaultdict(lambda: None) self.Q = [] heappush(self.Q, (self.dist[s], s)) while self.Q: dist_u, u = heappop(self.Q) if self.dist[u] < dist_u: continue for v, w in self.g[u]: alt = dist_u + w if self.dist[v] > alt: self.dist[v] = alt self.prev[v] = u heappush(self.Q, (alt, v)) def s_d(self, goal): return self.dist[goal] def s_p(self, goal): path = [] node = goal while node is not None: path.append(node) node = self.prev[node] return path[::-1] xs, ys, xg, yg = list(map(int, input().split())) xyr = [] xyr.append([xs, ys, 0]) N = int(input()) for i in range(N): xyr.append(list(map(int, input().split()))) xyr.append([xg, yg, 0]) g_a = Graph() for i in range(N + 1): for j in range(i + 1, N + 2): a, b = i, j R = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5 if R > xyr[i][2] + xyr[j][2]: r = R - xyr[i][2] - xyr[j][2] else: r = 0 g_a.add_edge(a, b, r) g_a.add_edge(b, a, r) d_a = Dijkstra(g_a, 0) print(d_a.s_d(N + 1))
Submission Info
Submission Time | |
---|---|
Task | E - Cosmic Rays |
User | su_565fx |
Language | Python (3.4.3) |
Score | 0 |
Code Size | 1886 Byte |
Status | TLE |
Exec Time | 2112 ms |
Memory | 127832 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 600 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 22 ms | 3316 KB |
0_01.txt | AC | 22 ms | 3316 KB |
0_02.txt | AC | 22 ms | 3316 KB |
1_00.txt | AC | 22 ms | 3316 KB |
1_01.txt | AC | 22 ms | 3316 KB |
1_02.txt | AC | 1886 ms | 101300 KB |
1_03.txt | AC | 1976 ms | 104044 KB |
1_04.txt | AC | 1898 ms | 101240 KB |
1_05.txt | AC | 1947 ms | 104396 KB |
1_06.txt | AC | 1825 ms | 98172 KB |
1_07.txt | AC | 1960 ms | 100304 KB |
1_08.txt | AC | 1949 ms | 103896 KB |
1_09.txt | AC | 1935 ms | 104296 KB |
1_10.txt | AC | 1921 ms | 104000 KB |
1_11.txt | AC | 1890 ms | 101600 KB |
1_12.txt | AC | 1949 ms | 101484 KB |
1_13.txt | AC | 1805 ms | 100020 KB |
1_14.txt | AC | 1970 ms | 105868 KB |
1_15.txt | AC | 1973 ms | 105900 KB |
1_16.txt | AC | 1922 ms | 104976 KB |
1_17.txt | AC | 1947 ms | 104540 KB |
1_18.txt | AC | 1945 ms | 102440 KB |
1_19.txt | AC | 1957 ms | 106684 KB |
1_20.txt | AC | 1927 ms | 101492 KB |
1_21.txt | AC | 1856 ms | 100248 KB |
1_22.txt | AC | 1948 ms | 104476 KB |
1_23.txt | AC | 1947 ms | 106212 KB |
1_24.txt | AC | 1970 ms | 105720 KB |
1_25.txt | AC | 1913 ms | 103180 KB |
1_26.txt | AC | 1927 ms | 104420 KB |
1_27.txt | AC | 1919 ms | 101020 KB |
1_28.txt | AC | 1926 ms | 105180 KB |
1_29.txt | AC | 1943 ms | 105388 KB |
1_30.txt | AC | 1863 ms | 101532 KB |
1_31.txt | AC | 1850 ms | 102764 KB |
1_32.txt | AC | 1945 ms | 105068 KB |
1_33.txt | AC | 1932 ms | 101424 KB |
1_34.txt | AC | 1836 ms | 99312 KB |
1_35.txt | AC | 1989 ms | 103736 KB |
1_36.txt | AC | 1907 ms | 103236 KB |
1_37.txt | AC | 1915 ms | 101928 KB |
1_38.txt | TLE | 2112 ms | 127760 KB |
1_39.txt | TLE | 2111 ms | 127832 KB |
1_40.txt | TLE | 2112 ms | 125260 KB |
1_41.txt | TLE | 2112 ms | 127816 KB |
1_42.txt | AC | 1895 ms | 100860 KB |
1_43.txt | AC | 1867 ms | 106816 KB |
1_44.txt | AC | 1873 ms | 105304 KB |
1_45.txt | AC | 1939 ms | 107624 KB |