結果
問題 | No.19 ステージの選択 |
ユーザー | szkhts |
提出日時 | 2022-11-06 08:47:46 |
言語 | Python3 (3.11.6 + numpy 1.26.0 + scipy 1.11.3) |
結果 |
AC
|
実行時間 | 348 ms / 5,000 ms |
コード長 | 843 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 10,984 KB |
実行使用メモリ | 8,316 KB |
最終ジャッジ日時 | 2023-09-27 05:47:52 |
合計ジャッジ時間 | 3,921 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 15 ms
7,852 KB |
testcase_01 | AC | 16 ms
7,788 KB |
testcase_02 | AC | 16 ms
7,776 KB |
testcase_03 | AC | 17 ms
7,748 KB |
testcase_04 | AC | 345 ms
8,284 KB |
testcase_05 | AC | 105 ms
7,748 KB |
testcase_06 | AC | 141 ms
7,748 KB |
testcase_07 | AC | 232 ms
7,892 KB |
testcase_08 | AC | 265 ms
8,304 KB |
testcase_09 | AC | 348 ms
8,316 KB |
testcase_10 | AC | 18 ms
7,776 KB |
testcase_11 | AC | 16 ms
7,816 KB |
testcase_12 | AC | 16 ms
7,864 KB |
testcase_13 | AC | 15 ms
7,860 KB |
testcase_14 | AC | 22 ms
7,864 KB |
testcase_15 | AC | 34 ms
7,816 KB |
testcase_16 | AC | 98 ms
7,832 KB |
testcase_17 | AC | 27 ms
7,860 KB |
testcase_18 | AC | 250 ms
7,880 KB |
testcase_19 | AC | 44 ms
7,780 KB |
testcase_20 | AC | 19 ms
7,928 KB |
testcase_21 | AC | 77 ms
7,832 KB |
testcase_22 | AC | 39 ms
7,752 KB |
testcase_23 | AC | 71 ms
7,812 KB |
ソースコード
N = int(input()) dist = [[False] * N for _ in range(N)] level = [0] * N stage = [0] * N reg = 0 for i in range(N): l, s = map(int, input().split()) level[i] = l stage[i] = s - 1 dist[i][stage[i]] = True dist[i][i] = True reg += level[i] for k in range(N): for i in range(N): for j in range(N): dist[i][j] = dist[i][j] | (dist[i][k] & dist[k][j]) for i in range(N): flag = True for j in range(i): if dist[i][j] and dist[j][i]: flag = False if not flag: continue for j in range(N): if dist[i][j] and not dist[j][i]: flag = False if not flag: continue mincost = 999 for j in range(i, N): if dist[i][j] and dist[j][i]: mincost = min(mincost, level[j]) reg += mincost print(reg / 2)