結果
問題 | No.468 役に立つ競技プログラミング実践編 |
ユーザー |
|
提出日時 | 2016-12-18 07:49:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 897 ms / 2,000 ms |
コード長 | 953 bytes |
コンパイル時間 | 225 ms |
コンパイル使用メモリ | 82,148 KB |
実行使用メモリ | 165,664 KB |
最終ジャッジ日時 | 2024-12-14 07:50:21 |
合計ジャッジ時間 | 12,513 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 31 |
other | AC * 6 |
ソースコード
n, m = map(int, input().split()) r = [[] for _ in range(n)] s = [[] for _ in range(n)] t1 = [[0, 0] for _ in range(n)] t2 = [[0, 16000000] for _ in range(n)] for _ in range(m): a, b, c = map(int, input().split()) r[a].append([b, c]) s[b].append([a, c]) tmp1 = set() tmp1.add(0) while len(tmp1) > 0: tmp2 = set() for a in tmp1: for b, c in r[a]: t1[b][1] = max(t1[b][1], t1[a][1] + c) t1[b][0] += 1 if t1[b][0] == len(s[b]): tmp2.add(b) tmp1 = tmp2 t2[n - 1][1] = t1[n - 1][1] tmp1 = set() tmp1.add(n - 1) while len(tmp1) > 0: tmp2 = set() for b in tmp1: for a, c in s[b]: t2[a][1] = min(t2[a][1], t2[b][1] - c) t2[a][0] += 1 if t2[a][0] == len(r[a]): tmp2.add(a) tmp1 = tmp2 p = 0 for i in range(n): if t1[i][1] != t2[i][1]: p += 1 print('{0} {1}/{2}'.format(t1[n - 1][1], p, n))