結果

問題 No.1364 [Renaming] Road to Cherry from Zelkova
ユーザー 👑 Kazun
提出日時 2021-01-20 04:51:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,813 bytes
コンパイル時間 351 ms
コンパイル使用メモリ 81,784 KB
実行使用メモリ 224,344 KB
最終ジャッジ日時 2024-12-25 15:17:00
合計ジャッジ時間 30,017 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 44 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class Digraph:
"""[].
"""
#
def __init__(self,vertex=[]):
self.vertex=set(vertex)
self.edge_number=0
self.vertex_number=len(vertex)
self.adjacent_out={v:set() for v in vertex} #(v)
self.adjacent_in={v:set() for v in vertex} #(v)
#
def add_vertex(self,*adder):
for v in adder:
if v not in self.vertex:
self.adjacent_in[v]=set()
self.adjacent_out[v]=set()
self.vertex_number+=1
self.vertex.add(v)
#
def add_edge(self,From,To):
for v in [From,To]:
if v not in self.vertex:
self.add_vertex(v)
if To not in self.adjacent_in[From]:
self.edge_number+=1
self.adjacent_out[From].add(To)
self.adjacent_in[To].add(From)
#
def remove_edge(self,From,To):
for v in [From,To]:
if v not in self.vertex:
self.add_vertex(v)
if To in self.adjacent_out[From]:
self.adjacent_out[From].remove(To)
self.adjacent_in[To].remove(From)
self.edge_number-=1
#
def remove_vertex(self,*vertexes):
for v in vertexes:
if v in self.vertex:
self.vertex_number-=1
for u in self.adjacent_out[v]:
self.adjacent_in[u].remove(v)
self.edge_number-=1
del self.adjacent_out[v]
for u in self.adjacent_in[v]:
self.adjacent_out[u].remove(v)
self.edge_number-=1
del self.adjacent_in[v]
#Walk
def add_walk(self,*walk):
N=len(walk)
for k in range(N-1):
self.add_edge(walk[k],walk[k+1])
#Cycle
def add_cycle(self,*cycle):
self.add_walk(*cycle)
self.add_edge(cycle[-1],cycle[0])
#
def __vertex_swap(self,p,q):
self.vertex.sort()
#
def vertex_exist(self,v):
return v in self.vertex
#
def edge_exist(self,From,To):
if not(self.vertex_exist(From) and self.vertex_exist(To)):
return False
return To in self.adjacent_out[From]
#
def neighbohood(self,v):
if not self.vertex_exist(v):
return []
return list(self.adjacent[v])
#
def out_degree(self,v):
if not self.vertex_exist(v):
return 0
return len(self.adjacent_out[v])
#
def in_degree(self,v):
if not self.vertex_exist(v):
return 0
return len(self.adjacent_in[v])
#
def degree(self,v):
if not self.vertex_exist(v):
return 0
return self.out_degree(v)-self.in_degree(v)
#
def vertex_count(self):
return len(self.vertex)
#
def edge_count(self):
return self.edge_number
#v
def connected_component(self,v):
pass
#
def Strongly_Connected_Component_Decomposition(D,Mode=0):
"""D
Mode:
0(Defalt)---
1 ---
2 ---0,1
※0.
"""
Group={v:0 for v in D.adjacent_out}
Order=[]
for v in D.adjacent_out:
if Group[v]:continue
S=[v]
Group[v]=-1
while S:
u=S.pop()
for w in D.adjacent_out[u]:
if Group[w]:continue
Group[w]=-1
S.append(u)
S.append(w)
break
else:
Order.append(u)
k=0
for v in Order[::-1]:
if Group[v]!=-1:
continue
S=[v]
Group[v]=k
while S:
u=S.pop()
for w in D.adjacent_in[u]:
if Group[w]!=-1:
continue
Group[w]=k
S.append(w)
k+=1
if Mode==0 or Mode==2:
T=[[] for _ in range(k)]
for v in D.adjacent_out:
T[Group[v]].append(v)
if Mode==0:
return T
elif Mode==1:
return Group
else:
return (Group,T)
#================================================
def f(p,z):
a,w=p
x,y=z
return [(x*a)%Mod,a*y+x*w]
#================================================
import sys
from collections import defaultdict
input=sys.stdin.readline
N,M=map(int,input().split())
Mod=10**9+7
D=Digraph(range(N+1))
E=[defaultdict(lambda :[0,0]) for _ in range(N+1)]
for _ in range(M):
u,v,w,a=map(int,input().split())
D.add_edge(u,v)
b,l=E[u][v]
E[u][v]=[b+a,(l+a*w)%Mod]
G,T=Strongly_Connected_Component_Decomposition(D,2)
inf=float("inf")
Flag=[0]*(N+1)
Flag[0]=1
DP=[[0,0] for _ in range(N+1)]
DP[0]=[1,0]
for U in T:
if len(U)>=2:
F=0
for v in U:
F|=Flag[v]
if F:
for v in U:
DP[v]=[inf,inf]
for u in U:
x,y=DP[u]
for v in E[u]:
Flag[v]|=Flag[u]
if x==inf:
DP[v]=[inf,inf]
else:
a,w=E[u][v]
DP[v][0]+=x*a
DP[v][1]+=y*a+x*w
DP[v][0]%=Mod
DP[v][1]%=Mod
print(DP[N][1] if DP[N][1]<inf else "INF")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0