結果
問題 | No.95 Alice and Graph |
ユーザー | nebukuro09 |
提出日時 | 2018-06-14 15:27:10 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 3,308 ms / 5,000 ms |
コード長 | 1,682 bytes |
コンパイル時間 | 743 ms |
コンパイル使用メモリ | 116,032 KB |
実行使用メモリ | 44,708 KB |
最終ジャッジ日時 | 2024-06-13 01:13:57 |
合計ジャッジ時間 | 11,633 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,031 ms
41,684 KB |
testcase_01 | AC | 148 ms
13,516 KB |
testcase_02 | AC | 140 ms
13,868 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 1,638 ms
43,856 KB |
testcase_05 | AC | 1,202 ms
40,104 KB |
testcase_06 | AC | 1,463 ms
24,196 KB |
testcase_07 | AC | 139 ms
14,184 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 1 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,944 KB |
testcase_11 | AC | 3 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 3,308 ms
44,708 KB |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; immutable int INF = 1 << 29; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto K = s[2]; auto G = new int[][](N); auto D = new int[][](N, N); foreach (_; 0..M) { s = readln.split.map!(to!int); G[s[0]-1] ~= s[1]-1; G[s[1]-1] ~= s[0]-1; } foreach (i; 0..N) foreach (j; 0..N) D[i][j] = i == j ? 0 : INF; foreach (i; 0..N) foreach (j; G[i]) D[i][j] = 1; foreach (i; 0..N) foreach (j; 0..N) foreach (k; 0..N) D[j][k] = min(D[j][k], D[j][i] + D[i][k]); bool can_travel(const int[] nodes) { int n = nodes.length.to!int; auto dp = new int[][](1<<n, n); foreach (i; 0..(1<<n)) fill(dp[i], INF); dp[1][0] = 0; foreach (mask; 1..(1<<n)) foreach (i; 0..n) if ((1 << i) & mask) foreach (j; 0..n) if (!((1 << j) & mask)) dp[mask|(1<<j)][j] = min(dp[mask|(1<<j)][j], dp[mask][i] + D[nodes[i]][nodes[j]]); return dp[(1<<n)-1].reduce!min <= K; } int[] S = [0]; foreach_reverse (i; 1..N) { S ~= i; if (!can_travel(S)) S.popBack; if (S.length == K+1) break; } ulong ans = 0; foreach (n; S) ans += (1UL << n) - 1; ans.writeln; }