結果
問題 | No.95 Alice and Graph |
ユーザー | 6soukiti29 |
提出日時 | 2017-08-18 22:35:41 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 3,861 ms / 5,000 ms |
コード長 | 1,335 bytes |
コンパイル時間 | 3,043 ms |
コンパイル使用メモリ | 69,764 KB |
実行使用メモリ | 21,332 KB |
最終ジャッジ日時 | 2023-09-12 14:53:16 |
合計ジャッジ時間 | 18,193 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,071 ms
21,324 KB |
testcase_01 | AC | 3,861 ms
21,276 KB |
testcase_02 | AC | 3,678 ms
21,260 KB |
testcase_03 | AC | 3 ms
4,380 KB |
testcase_04 | AC | 446 ms
13,248 KB |
testcase_05 | AC | 392 ms
13,288 KB |
testcase_06 | AC | 407 ms
21,332 KB |
testcase_07 | AC | 3,330 ms
21,320 KB |
testcase_08 | AC | 3 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 3 ms
4,376 KB |
testcase_12 | AC | 3 ms
4,376 KB |
testcase_13 | AC | 69 ms
13,120 KB |
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 26) Warning: imported and not used: 'math' [UnusedImport]
ソースコード
import sequtils,strutils,math var N,M,K,u,v : int D : array[1..60, array[1..60, int]] (N, M, K) = stdin.readline.split.map(parseInt) for i in 1..N: for j in 1..N: D[i][j] = 200 for m in 1..M: (u,v) = stdin.readline.split.map(parseInt) D[u][v] = 1 D[v][u] = 1 for k in 1..N: for i in 1..N: for j in 1..N: D[i][j] = min(D[i][j], D[i][k] + D[k][j]) var p : int tezyun = newSeqWith(1, 1) x : int DP : array[(1 shl 20) + 1,array[17,int]] for n in countdown(N, 1): if D[1][n] > K: continue tezyun.add(n) for i in 1..(1 shl tezyun.high): for j in 0..tezyun.high: DP[i * 2 - 1][j] = 10000 DP[1][0] = 0 var k = 1 while k < (1 shl tezyun.len): for p in 0..tezyun.high: if DP[k][p] > K: continue for t in 1..tezyun.high: if (k and (1 shl t)) == 0: DP[k + (1 shl t)][t] = min(DP[k + (1 shl t)][t], DP[k][p] + D[tezyun[t]][tezyun[p]]) k += 2 var flag = false for p in 1..tezyun.high: if DP[(1 shl tezyun.len) - 1][p] <= K: flag = true break if not flag: discard tezyun.pop() var ans : int64 for t in tezyun: ans += (1.int64 shl (t - 1)) - 1 echo ans