結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
|
提出日時 | 2025-01-25 12:42:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 793 ms / 2,000 ms |
コード長 | 1,316 bytes |
コンパイル時間 | 852 ms |
コンパイル使用メモリ | 82,348 KB |
実行使用メモリ | 117,040 KB |
最終ジャッジ日時 | 2025-01-25 22:17:30 |
合計ジャッジ時間 | 18,694 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
import sys# sys.setrecursionlimit(10 ** 6)# import pypyjit# pypyjit.set_param('max_unroll_recursion=-1')from collections import defaultdict as ddfrom heapq import *S = inputR = rangeP = printdef I(): return int(S())def M(): return map(int, S().split())def L(): return list(M())def O(): return list(map(int, open(0).read().split()))def yn(b): print("Yes" if b else "No")biga = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"smaa = "abcdefghijklmnopqrstuvwxyz"ctoi = lambda c: ord(c) - ord('a')ctoi2 = lambda c: ord(c) - ord('A')itoc = lambda i: chr(ord('a') + i)itoc2 = lambda i: chr(ord('A') + i)inf = 10 ** 18mod = 998244353dxy4 = [(-1, 0), (0, -1), (1, 0), (0, 1)]dxy8 = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]def acc(a):b = [0]for i in a:b.append(b[-1] + i)return bdef gin(N, M):g = [[] for _ in range(N)]for _ in range(M):u, v = map(int, input().split())u -= 1v -= 1g[u].append(v)g[v].append(u)return gn,m,p,y=M()g=[[]for _ in R(n)]for _ in R(m):a,b,c=M();a-=1;b-=1;g[a].append((b,c));g[b].append((a,c))d=[inf]*n;ok=[False]*n;q=[(0,0)];d[0]=0while q:di,u=heappop(q)if ok[u]:continueok[u]=Truefor v,c in g[u]:if di+c<d[v]:d[v]=di+cheappush(q,(d[v],v))ans=0for _ in R(p):D,e=M();D-=1ans=max(ans,(y-d[D])//e)P(ans)