結果
問題 |
No.19 ステージの選択
|
ユーザー |
|
提出日時 | 2020-12-10 12:55:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 42 ms / 5,000 ms |
コード長 | 621 bytes |
コンパイル時間 | 297 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 54,272 KB |
最終ジャッジ日時 | 2024-09-19 20:30:29 |
合計ジャッジ時間 | 2,405 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
import sys input = sys.stdin.readline from collections import * def bfs(s, g): q = deque([s]) dist = [-1]*N dist[s] = 0 while q: v = q.popleft() for nv in G[v]: if dist[nv]==-1: dist[nv] = dist[v]+1 q.append(nv) return dist[g]!=-1 N = int(input()) ans = 0.0 decr = [] for i in range(N): L, S = map(int, input().split()) ans += L decr.append((L/2, S-1, i)) decr.sort(reverse=True) G = [[] for _ in range(N)] for d, i, j in decr: if not bfs(i, j): ans -= d G[j].append(i) print(ans)