結果
問題 |
No.2712 Play more!
|
ユーザー |
|
提出日時 | 2024-04-13 14:18:53 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 958 bytes |
コンパイル時間 | 368 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 216,064 KB |
最終ジャッジ日時 | 2024-10-03 00:07:47 |
合計ジャッジ時間 | 4,612 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 TLE * 1 -- * 24 |
ソースコード
from collections import defaultdict,deque N,M=map(int,input().split()) A=list(map(int,input().split())) G=[[] for _ in range(N)] cost=defaultdict(int) for _ in range(M): a,b,c=map(int,input().split()) a-=1;b-=1 G[a].append(b) cost[(a,b)]=c kouho=[] loop=set() Q=deque() Q.append((0,[])) while Q: d,r=Q.popleft() r.append(d) if d==N-1: kouho.append(r) continue s=set(r) for n in G[d]: if n in s: tmp=r[r.index(n):]+[n] sat=0 for i in range(len(tmp)-1): sat+=A[tmp[i]]-cost[(tmp[i],tmp[i+1])] sat+=tmp[-1] if sat>0: loop|=set(tmp) else: Q.append((n,r[:])) ans=0 for k in kouho: for i in k: if i in loop: print("inf") exit() sat=0 for i in range(len(k)-1): sat+=A[k[i]]-cost[(k[i],k[i+1])] sat+=A[-1] ans=max(ans,sat) print(ans)