結果
問題 | No.848 なかよし旅行 |
ユーザー | 6soukiti29 |
提出日時 | 2019-07-07 12:15:06 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 270 ms / 2,000 ms |
コード長 | 2,656 bytes |
コンパイル時間 | 3,658 ms |
コンパイル使用メモリ | 71,160 KB |
実行使用メモリ | 37,176 KB |
最終ジャッジ日時 | 2023-08-07 19:48:23 |
合計ジャッジ時間 | 7,932 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 248 ms
37,160 KB |
testcase_01 | AC | 18 ms
35,672 KB |
testcase_02 | AC | 18 ms
35,600 KB |
testcase_03 | AC | 17 ms
35,704 KB |
testcase_04 | AC | 17 ms
35,828 KB |
testcase_05 | AC | 17 ms
35,692 KB |
testcase_06 | AC | 18 ms
35,640 KB |
testcase_07 | AC | 18 ms
35,680 KB |
testcase_08 | AC | 22 ms
35,636 KB |
testcase_09 | AC | 23 ms
35,708 KB |
testcase_10 | AC | 22 ms
35,664 KB |
testcase_11 | AC | 106 ms
36,200 KB |
testcase_12 | AC | 132 ms
36,408 KB |
testcase_13 | AC | 169 ms
36,524 KB |
testcase_14 | AC | 83 ms
35,796 KB |
testcase_15 | AC | 158 ms
36,500 KB |
testcase_16 | AC | 256 ms
37,176 KB |
testcase_17 | AC | 172 ms
36,776 KB |
testcase_18 | AC | 100 ms
36,196 KB |
testcase_19 | AC | 94 ms
36,072 KB |
testcase_20 | AC | 75 ms
35,712 KB |
testcase_21 | AC | 203 ms
36,820 KB |
testcase_22 | AC | 191 ms
37,148 KB |
testcase_23 | AC | 102 ms
35,848 KB |
testcase_24 | AC | 17 ms
35,644 KB |
testcase_25 | AC | 270 ms
36,692 KB |
testcase_26 | AC | 18 ms
35,680 KB |
testcase_27 | AC | 18 ms
35,660 KB |
testcase_28 | AC | 17 ms
35,796 KB |
testcase_29 | AC | 18 ms
35,652 KB |
コンパイルメッセージ
/home/judge/data/code/Main.nim(23, 25) Warning: Number of spaces around '<=' is not consistent [Spacing] /home/judge/data/code/Main.nim(1, 26) Warning: imported and not used: 'math' [UnusedImport]
ソースコード
import sequtils,strutils,math type priorityQue[I:static[int];T:tuple] = array[I + 1,T] item = tuple[cost: int,ID : int] var hyou : array[2001, array[2001, int]] proc push[T](A:var priorityQue; b: T;)= const key = 0 A[0][0] += 1 A[A[0][0]] = b # A[0][0]はsize、最大のIndex var index = A[0][0] while index > 1 and A[index][key] > A[index div 2][key]: (A[index],A[index div 2]) = (A[index div 2],A[index]) index = index div 2 proc pop(A: var priorityQue):item = const key = 0 result = A[1] A[1] = A[A[0][0]] var a : item A[A[0][0]] = a A[0][0] -= 1 var index = 1 while index * 2 <= A[0][0]: if index * 2 + 1<= A[0][0]: if A[index][key] < A[index * 2][key] and A[index * 2 + 1][key] <= A[index * 2][key]: (A[index],A[index * 2]) = (A[index * 2],A[index]) index = index * 2 elif A[index][key] < A[index * 2 + 1][key]: (A[index],A[index * 2 + 1]) = (A[index * 2 + 1],A[index]) index = index * 2 + 1 else: break elif index * 2 <= A[0][0]: if A[index][key] < A[index * 2][key]: (A[index],A[index * 2]) = (A[index * 2],A[index]) break else: break proc size(A : priorityQue):int= return A[0][0] var pq : priorityQue[201000, item] proc dijikstra(i : int) : seq[int]= var res = newSeq[int](2001) #N_maxに書き換える for i in 0..2000: res[i] = int.high pq.push((0, i)) while pq.size > 0 : var a = pq.pop if res[a.ID] != int.high: continue res[a.ID] = - a.cost for np, c in hyou[a.ID]: #表がN * N の時 if c < int.high and res[np] == int.high: pq.push((a.cost - c, np)) #[for edge in hyou[a.ID]: #表が隣接表示 hyou = array[tuple[to, cost : int]] if res[edge.to] == int.high: pq.push((a.cost - edge.cost, edge.to))]# return res var N,M,P,Q,T : int a,b,c : int (N, M, P, Q, T) = stdin.readline.split.map(parseInt) for i in 0..2000: for j in 0..2000: hyou[i][j] = int.high for i in 1..M: (a, b, c) = stdin.readline.split.map(parseInt) hyou[a][b] = c hyou[b][a] = c var cos1 = dijikstra(1) cosQ = dijikstra(Q) cosP = dijikstra(P) ans = -1 for i in 1..N: for j in 1..N: if cos1[i] + max(cosQ[i] + cosQ[j], cosP[i] + cosP[j]) + cos1[j] <= T: ans = max(ans, T - max(cosQ[i] + cosQ[j], cosP[i] + cosP[j])) if cos1[P] + cos1[Q] + cosP[Q] <= T: ans = T echo ans