結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
![]() |
提出日時 | 2021-01-15 22:26:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,200 ms / 2,000 ms |
コード長 | 680 bytes |
コンパイル時間 | 288 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 81,664 KB |
最終ジャッジ日時 | 2024-11-27 23:12:20 |
合計ジャッジ時間 | 20,575 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
import sysinput = sys.stdin.readlineN, M, T = map(int, input().split())bn = list(map(int, bin(T)[2: ]))ln = len(bn)d = [[[0] * N for _ in range(N)] for _ in range(ln)]for _ in range(M):u, v = map(int, input().split())d[0][u][v] = 1for t in range(ln - 1):for k in range(N):for i in range(N):for j in range(N):d[t + 1][i][j] |= d[t][i][k] & d[t][k][j]dt = [[0] * N for _ in range(N)]dt[0][0] = 1for tt in range(ln):t = ln - tt - 1if bn[tt] == 0: continuetdt = [[0] * N for _ in range(N)]for k in range(N):for i in range(N):for j in range(N):tdt[i][j] |= dt[i][k] & d[t][k][j]dt = tdtprint(sum(dt[0]))