[테스트 케이스 모음] 백준 10473 : 인간대포 ( 파이썬 python )

1. 문제

https://www.acmicpc.net/problem/10473

10473번: 인간 대포

 

 

 

2. 풀이

점과 점 사이에 걸리는 시간을 값으로 하는 array를 만들어서 dijkstra한다.

점들은 시작점, 캐넌들, 도착점이며

거리는 시작점, 도착점: 걸어가는 거리, 캐넌들: 50m는 그냥 가고 나머지는 걸어가는 시간 + 2초 값을 넣어준다.

 

그림에서 막 꺾이고 이래서 겁을 좀 먹었는데 거리를 간단하게 생각하면 쉬운 문제이다.

 

 

 

3. 구현

import sys
import heapq
import math

# sys.stdin = open('generated098.in')

sr,sc=map(float, sys.stdin.readline().split())
dr,dc=map(float, sys.stdin.readline().split())
n = int(sys.stdin.readline())

def distance(curR,curC,nextR,nextC):
  return ((curR-nextR)**2+(curC-nextC)**2)**0.5

def dijk(node, gph):

  dist=[math.inf for _ in range(len(canon))]
  edges=[]
  
  dist[node]=0
  heapq.heappush(edges, (dist[node], node)) # cost, pos
  
  while edges:
    cost,pos = heapq.heappop(edges)
    if dist[pos]<cost:
      continue
    for p, c in enumerate(gph[pos]):
      # print(pos,p,c)
      c +=cost
      if dist[p]>c:
        dist[p]=c
        heapq.heappush(edges, (c,p))
  return dist

canon=[]
canon.append((sr,sc))

while n:
  n-=1
  cr, cc = map(float, sys.stdin.readline().split())
  canon.append((cr,cc))
canon.append((dr,dc))

time =[ [] for _ in range(len(canon))]
for i in range(len(canon)):
  for j in range(len(canon)):
    if i==0 or i==len(canon)-1:
      time[i].append(distance(canon[i][0], canon[i][1], canon[j][0], canon[j][1])/5) # 걸어가는 시간
    else:
      time[i].append(abs(distance(canon[i][0], canon[i][1], canon[j][0], canon[j][1])-50)/5+2) # 대포 한 번 + 걸어가기 

# print(time)
res = dijk(0,time)
print(res[len(canon)-1])

 

 

 

4. 테스트케이스

공식 시험에 있는 TC 몇가지.

465.47 137.85
268.90 324.76
96
213.05 207.57
56.99 273.10
2.20 460.41
84.09 280.92
492.54 117.89
376.95 481.74
50.35 222.44
33.69 160.80
8.78 148.83
468.71 164.39
353.48 17.05
57.74 6.35
208.53 262.45
442.60 261.26
472.52 179.52
208.20 156.90
14.53 138.70
90.01 272.55
209.02 491.55
468.01 399.93
52.26 319.82
205.81 118.50
91.43 118.63
380.34 291.69
468.47 67.92
107.49 90.52
322.99 44.48
29.14 263.52
430.23 295.11
386.31 289.13
329.56 437.37
349.58 356.61
474.21 104.23
339.79 338.46
37.74 226.15
352.70 343.37
496.62 137.00
84.52 39.44
424.93 240.33
189.91 259.47
433.95 469.48
42.16 36.61
326.97 349.59
66.49 488.85
49.96 189.70
323.85 475.72
345.14 307.25
374.73 123.35
203.96 33.08
452.61 62.50
447.73 424.84
308.08 380.06
218.69 83.86
466.73 354.18
230.71 47.19
69.43 462.45
458.16 295.62
38.47 23.91
336.12 120.66
456.51 83.56
409.02 373.97
347.29 485.93
69.93 277.88
345.38 260.99
29.16 86.84
453.56 484.38
411.24 202.85
361.99 421.03
269.33 110.08
39.78 150.31
209.24 263.36
263.48 306.48
62.24 31.15
20.24 112.66
437.62 11.28
35.83 248.91
417.16 182.97
152.15 177.06
415.37 94.04
62.21 68.58
110.81 315.69
380.22 336.48
172.08 223.91
296.93 48.20
63.23 170.28
330.11 218.23
212.19 272.10
210.58 202.50
386.62 437.85
28.48 132.88
282.54 172.70
44.64 322.38
231.64 225.32
485.84 46.11
41.69 100.13
433.68 416.12

답: 26.381178

 

 

245.96 350.63
460.84 366.44
10
55.38 291.17
164.54 486.58
24.72 34.54
27.41 151.50
281.62 109.76
167.17 115.65
290.08 455.40
341.41 80.09
62.28 195.77
340.74 372.22

답: 35.489382

 

108.63 316.94
381.41 324.50
96
213.44 274.98
110.76 45.36
444.58 493.63
386.22 276.65
191.62 64.24
106.31 223.29
345.10 67.49
357.23 430.50
364.17 107.41
320.84 381.85
315.25 488.91
168.21 71.95
223.50 323.86
193.56 133.71
203.59 171.83
433.02 323.44
496.45 312.57
438.31 157.14
13.42 3.09
384.99 16.10
161.74 406.76
461.71 5.87
230.12 89.69
475.81 433.22
165.99 273.08
156.22 135.18
417.41 463.87
217.66 198.62
199.13 248.63
233.78 220.93
249.10 80.94
439.21 336.83
116.94 472.79
188.24 207.18
93.78 144.98
114.80 444.54
346.64 420.35
395.88 2.51
262.25 188.29
138.96 456.68
492.22 164.91
80.76 251.52
364.18 313.61
315.41 59.67
411.63 274.55
366.93 9.41
93.33 66.97
112.59 379.44
247.32 284.84
269.85 323.67
477.74 414.25
254.72 125.87
39.01 88.57
98.87 194.74
441.63 19.66
427.29 412.89
379.10 8.75
43.21 245.82
35.54 359.65
156.30 448.51
76.33 459.58
108.32 69.58
411.75 235.11
3.63 431.85
161.93 489.32
421.48 385.11
110.95 289.57
383.13 278.60
414.86 50.21
310.41 139.68
145.34 207.33
48.40 499.16
390.03 178.66
299.14 184.76
234.08 237.99
390.50 94.71
313.03 110.54
308.54 188.79
20.66 271.66
301.26 234.24
383.03 124.84
125.23 234.19
56.31 459.43
146.03 374.13
21.11 253.18
205.61 196.93
243.52 305.85
422.41 447.00
296.59 367.38
136.25 391.33
109.28 188.73
482.52 178.68
22.08 170.19
407.29 345.65
298.02 366.09
425.97 250.86

답: 29.057976

 

19.17 244.40
183.88 467.66
31
159.83 311.68
395.93 318.34
261.29 487.08
328.71 113.51
297.80 95.70
438.84 108.87
251.66 70.17
278.03 387.35
208.43 115.39
315.08 121.20
52.26 314.41
247.43 117.42
434.86 210.09
470.06 260.34
33.52 334.46
267.35 398.83
146.57 431.94
122.53 294.80
142.54 195.31
63.02 157.20
108.15 245.82
446.25 79.26
77.38 479.83
468.54 244.74
352.77 62.59
479.40 356.51
436.67 150.76
262.81 38.82
450.96 270.76
132.06 457.12
302.26 142.09

답: 39.955801