結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
class Digraph:"""重み[なし]有向グラフを生成する."""#入力定義def __init__(self,vertex=[]):self.vertex=set(vertex)self.edge_number=0self.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+=1self.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+=1self.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-=1for u in self.adjacent_out[v]:self.adjacent_in[u].remove(v)self.edge_number-=1del self.adjacent_out[v]for u in self.adjacent_in[v]:self.adjacent_out[u].remove(v)self.edge_number-=1del 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 Falsereturn 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 0return len(self.adjacent_out[v])#入次数def in_degree(self,v):if not self.vertex_exist(v):return 0return len(self.adjacent_in[v])#次数def degree(self,v):if not self.vertex_exist(v):return 0return 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]:continueS=[v]Group[v]=-1while S:u=S.pop()for w in D.adjacent_out[u]:if Group[w]:continueGroup[w]=-1S.append(u)S.append(w)breakelse:Order.append(u)k=0for v in Order[::-1]:if Group[v]!=-1:continueS=[v]Group[v]=kwhile S:u=S.pop()for w in D.adjacent_in[u]:if Group[w]!=-1:continueGroup[w]=kS.append(w)k+=1if 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 Telif Mode==1:return Groupelse:return (Group,T)#================================================def f(p,z):a,w=px,y=zreturn [(x*a)%Mod,a*y+x*w]#================================================import sysfrom collections import defaultdictinput=sys.stdin.readlineN,M=map(int,input().split())Mod=10**9+7D=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]=1DP=[[0,0] for _ in range(N+1)]DP[0]=[1,0]for U in T:if len(U)>=2:F=0for 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*aDP[v][1]+=y*a+x*wDP[v][0]%=ModDP[v][1]%=Modprint(DP[N][1] if DP[N][1]<inf else "INF")