結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-22 22:40:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 504 ms / 2,500 ms |
コード長 | 2,225 bytes |
コンパイル時間 | 433 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 143,232 KB |
最終ジャッジ日時 | 2024-12-29 09:10:02 |
合計ジャッジ時間 | 14,740 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
"""N~2N回目の間に頂点Nの更新があった場合はOUTO(N)くらいで何とかする必要が…Nからさかのぼり、行けない点を全部消すあとはトポロジカルソートをして数え上げればよい"""import sysfrom sys import stdinfrom collections import dequeN,M = map(int,stdin.readline().split())mod = 10**9+7lis = [ [] for i in range(N+1) ]rlis = [ [] for i in range(N+1) ]inNum = [0] * (N+1)for i in range(M):u,v,l,a = map(int,stdin.readline().split())lis[u].append((v,l,a))rlis[v].append((u,l,a))exist = [0] * (N+1)exist[N] = 1q = deque([N])while q:v = q.popleft()for nex,tmp1,tmp2 in rlis[v]:if 0 == exist[nex]:exist[nex] = 1q.append(nex)if not exist[0]:print (0)sys.exit()q = deque([0])exist[0] = 2while q:v = q.popleft()for nex,tmp1,tmp2 in lis[v]:if 1 == exist[nex]:exist[nex] = 2q.append(nex)for v in range(N+1):if exist[v] == 2:for nex,tmp1,tmp2 in lis[v]:inNum[nex] += 1if inNum[0] != 0:print ("INF")sys.exit()ansA = [0 for i in range(N+1)]ansA[0] = 1q = deque([0])while q:v = q.popleft()if v == N:breakfor nex,l,a in lis[v]:if exist[nex] != 2:continueansA[nex] += ansA[v] * aansA[nex] %= modinNum[nex] -= 1if inNum[nex] == 0:q.append(nex)else:print ("INF")sys.exit()inNum = [0] * (N+1)for v in range(N+1):if exist[v] == 2:for nex,tmp1,tmp2 in rlis[v]:inNum[nex] += 1ansB = [0 for i in range(N+1)]ansB[N] = 1q = deque([N])while q:v = q.popleft()for nex,l,a in rlis[v]:if exist[nex] != 2:continueansB[nex] += ansB[v] * aansB[nex] %= modinNum[nex] -= 1if inNum[nex] == 0:q.append(nex)ans = 0for v in range(N+1):if 2 == exist[v]:for nex,l,a in lis[v]:if 2 == exist[nex]:ans += ansA[v] * a * ansB[nex] * lans %= mod#print (ansA,ansB)print (ans)