結果
問題 |
No.3013 ハチマキ買い星人
|
ユーザー |
|
提出日時 | 2025-02-02 15:36:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,090 ms / 2,000 ms |
コード長 | 2,263 bytes |
コンパイル時間 | 443 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 143,744 KB |
最終ジャッジ日時 | 2025-02-02 15:37:29 |
合計ジャッジ時間 | 26,186 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
#!/usr/bin/env python3 from ast import Call, parse, unparse, walk from heapq import heappop, heappush from inspect import currentframe, getsourcelines from sys import maxsize, stdin _tokens = (y for x in stdin for y in x.split()) def read(): return next(_tokens) def iread(): return int(next(_tokens)) def dprint(*args, pretty=True): def _inner(v): def _format_3d(v): return '\n' + '\n'.join(['\n'.join([' '.join([str(z) for z in y]) for y in x]) + '\n' for x in v]).rstrip('\n') def _format_2d(v): return '\n' + '\n'.join([' '.join([str(y) for y in x]) for x in v]) def _dim(v): return (1 + min(_dim(x) for x in v) if v else 1) if isinstance(v, (list, tuple)) else 1 if isinstance(v, str) and len(v) > 1 else 0 dim = _dim(v) if pretty else -1 return _format_3d(v) if dim == 3 else _format_2d(v) if dim == 2 else str(v) frame = currentframe().f_back source_lines, start_line = getsourcelines(frame) tree = parse(source_lines[frame.f_lineno - max(1, start_line)].strip()) call_node = next(node for node in walk(tree) if isinstance(node, Call) and node.func.id == 'dprint') arg_names = [unparse(arg) for arg in call_node.args] print(', '.join([f'\033[4;35m{name}:\033[0m {_inner(value)}' for name, value in zip(arg_names, args)])) def main(): n, m, p, y = iread(), iread(), iread(), iread() abc = [(iread() - 1, iread() - 1, iread()) for _ in range(m)] de = [(iread() - 1, iread()) for _ in range(p)] to = [[] for _ in range(n)] for a, b, c in abc: to[a].append((b, c)) to[b].append((a, c)) hq = [] def push(x): heappush(hq, x) def pop(): return heappop(hq) INF = maxsize dist = [INF for _ in range(n)] dist[0] = 0 push((0, 0)) while hq: v, i = pop() if dist[i] != v: continue for j, c in to[i]: nv = v + c if dist[j] <= nv: continue dist[j] = nv push((nv, j)) # dprint(dist) ans = 0 for d, e in de: if dist[d] == INF: continue v = y - dist[d] if v <= 0: continue u = v // e ans = max(ans, u) print(ans) if __name__ == '__main__': main()