Submission #4624430


Source Code Expand

from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0

        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
                    heappush(self.Q, (alt, v))

    def s_d(self, goal):
        return self.dist[goal]



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
        x1 = xyr[i][0]
        y1 = xyr[i][1]
        x2 = xyr[j][0]
        y2 = xyr[j][1]
        R = ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) ** 0.5
        r1 = xyr[i][2]
        r2 = xyr[j][2]
        if R > r1 + r2:
            r = R - r1 - r2
        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 1580 Byte
Status TLE
Exec Time 2114 ms
Memory 127712 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 45
TLE × 4
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 3436 KB
0_01.txt AC 21 ms 3316 KB
0_02.txt AC 21 ms 3316 KB
1_00.txt AC 21 ms 3316 KB
1_01.txt AC 21 ms 3316 KB
1_02.txt AC 1692 ms 101300 KB
1_03.txt AC 1722 ms 104104 KB
1_04.txt AC 1698 ms 101172 KB
1_05.txt AC 1783 ms 104508 KB
1_06.txt AC 1680 ms 98128 KB
1_07.txt AC 1783 ms 100284 KB
1_08.txt AC 1700 ms 103612 KB
1_09.txt AC 1745 ms 104160 KB
1_10.txt AC 1759 ms 103948 KB
1_11.txt AC 1732 ms 101568 KB
1_12.txt AC 1694 ms 101436 KB
1_13.txt AC 1686 ms 100128 KB
1_14.txt AC 1791 ms 105876 KB
1_15.txt AC 1767 ms 105824 KB
1_16.txt AC 1692 ms 104948 KB
1_17.txt AC 1764 ms 104324 KB
1_18.txt AC 1697 ms 102576 KB
1_19.txt AC 1746 ms 105808 KB
1_20.txt AC 1666 ms 101476 KB
1_21.txt AC 1718 ms 100048 KB
1_22.txt AC 1830 ms 104540 KB
1_23.txt AC 1724 ms 104248 KB
1_24.txt AC 1841 ms 105460 KB
1_25.txt AC 1680 ms 103252 KB
1_26.txt AC 1822 ms 104656 KB
1_27.txt AC 1722 ms 100908 KB
1_28.txt AC 1718 ms 105124 KB
1_29.txt AC 1771 ms 105364 KB
1_30.txt AC 1667 ms 101500 KB
1_31.txt AC 1683 ms 102504 KB
1_32.txt AC 1833 ms 105308 KB
1_33.txt AC 1710 ms 101360 KB
1_34.txt AC 1641 ms 99168 KB
1_35.txt AC 1674 ms 103684 KB
1_36.txt AC 1645 ms 103280 KB
1_37.txt AC 1633 ms 101812 KB
1_38.txt TLE 2114 ms 127628 KB
1_39.txt TLE 2114 ms 127712 KB
1_40.txt TLE 2113 ms 125348 KB
1_41.txt TLE 2114 ms 127700 KB
1_42.txt AC 1739 ms 100832 KB
1_43.txt AC 1786 ms 106776 KB
1_44.txt AC 1689 ms 105308 KB
1_45.txt AC 1732 ms 107544 KB