結果
問題 | No.1207 グラフX |
ユーザー | persimmon-persimmon |
提出日時 | 2021-06-17 10:46:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,175 ms / 2,000 ms |
コード長 | 2,802 bytes |
コンパイル時間 | 1,098 ms |
コンパイル使用メモリ | 86,664 KB |
実行使用メモリ | 201,272 KB |
最終ジャッジ日時 | 2023-08-30 18:53:52 |
合計ジャッジ時間 | 49,515 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,076 ms
201,272 KB |
testcase_01 | AC | 1,075 ms
196,168 KB |
testcase_02 | AC | 1,085 ms
201,048 KB |
testcase_03 | AC | 1,106 ms
200,700 KB |
testcase_04 | AC | 1,053 ms
200,136 KB |
testcase_05 | AC | 1,170 ms
172,052 KB |
testcase_06 | AC | 1,175 ms
171,116 KB |
testcase_07 | AC | 1,172 ms
171,308 KB |
testcase_08 | AC | 905 ms
150,664 KB |
testcase_09 | AC | 993 ms
172,388 KB |
testcase_10 | AC | 1,157 ms
170,280 KB |
testcase_11 | AC | 1,161 ms
172,060 KB |
testcase_12 | AC | 925 ms
161,152 KB |
testcase_13 | AC | 546 ms
107,484 KB |
testcase_14 | AC | 1,117 ms
191,800 KB |
testcase_15 | AC | 968 ms
163,860 KB |
testcase_16 | AC | 537 ms
110,116 KB |
testcase_17 | AC | 800 ms
145,428 KB |
testcase_18 | AC | 699 ms
144,828 KB |
testcase_19 | AC | 723 ms
126,272 KB |
testcase_20 | AC | 1,102 ms
198,448 KB |
testcase_21 | AC | 178 ms
82,432 KB |
testcase_22 | AC | 792 ms
147,512 KB |
testcase_23 | AC | 855 ms
152,408 KB |
testcase_24 | AC | 631 ms
138,420 KB |
testcase_25 | AC | 1,116 ms
197,492 KB |
testcase_26 | AC | 903 ms
167,180 KB |
testcase_27 | AC | 1,062 ms
184,388 KB |
testcase_28 | AC | 999 ms
167,288 KB |
testcase_29 | AC | 1,038 ms
179,728 KB |
testcase_30 | AC | 584 ms
118,820 KB |
testcase_31 | AC | 465 ms
101,780 KB |
testcase_32 | AC | 548 ms
119,916 KB |
testcase_33 | AC | 552 ms
117,188 KB |
testcase_34 | AC | 897 ms
163,888 KB |
testcase_35 | AC | 195 ms
82,320 KB |
testcase_36 | AC | 932 ms
172,348 KB |
testcase_37 | AC | 816 ms
150,628 KB |
testcase_38 | AC | 342 ms
94,020 KB |
testcase_39 | AC | 563 ms
122,368 KB |
testcase_40 | AC | 333 ms
95,068 KB |
testcase_41 | AC | 660 ms
126,484 KB |
testcase_42 | AC | 72 ms
70,932 KB |
testcase_43 | AC | 73 ms
71,232 KB |
testcase_44 | AC | 70 ms
71,164 KB |
testcase_45 | AC | 967 ms
195,672 KB |
testcase_46 | AC | 961 ms
195,088 KB |
testcase_47 | AC | 968 ms
195,192 KB |
testcase_48 | AC | 962 ms
195,144 KB |
ソースコード
""" zi!=zjなので、パスの最短距離はそこに含まれるzの最大値で決まる。 パスに含まれる辺の本数がどれだけ大きくてもzの最大値が他のパスより小さければそのパスが最短になる。 ziの小さい順にグラフに辺を追加していく。unionFind 木ができる。あとはやるだけ。 """ def main0(n,m,x,uvz): mod=10**9+7 from heapq import heappop,heappush g=[[] for _ in range(n)] for u,v,z in uvz: u,v=u-1,v-1 g[u].append([v,pow(x,z)]) g[v].append([u,pow(x,z)]) ans=0 inf=float('inf') for i in range(n-1): seen=[inf]*n todo=[[0,i]] seen[i]=0 while todo: c,v=heappop(todo) if seen[v]<c:continue for nv,nc in g[v]: if seen[nv]>seen[v]+nc: seen[nv]=seen[v]+nc heappush(todo,[seen[nv],nv]) ans+=sum(seen[i+1:]) ans%=mod return ans # UnionFind class UnionFind: def __init__(self,n): self.n=n self.par=[-1]*n # par[i]:i根ならグループiの要素数に-1をかけたもの。i根じゃないならiの親 self.rank=[0]*n # iの根を返す def find(self,i): if self.par[i]<0:return i ii=i while self.par[i]>=0: i=self.par[i] while i!=self.par[ii]: ii,self.par[ii]=self.par[ii],i return i # iとjをunionし、根頂点を返す def union(self,i,j): i,j=self.find(i),self.find(j) if i==j:return i elif self.rank[i]>self.rank[j]: # par[i]:グループiの要素数で判断してもいい self.par[i]+=self.par[j] self.par[j]=i else: self.par[j]+=self.par[i] self.par[i]=j # 深さ(rank)が同じものを併合した場合1を足す if self.rank[i]==self.rank[j]: self.rank[j]+=1 return self.find(i) # iとjが同じグループに属するか判断 def same(self,i,j): return self.find(i)==self.find(j) # ノードiが属する木のサイズを返す def size(self,i): return -self.par[self.find(i)] def main1(n,m,x,uvz): mod=10**9+7 uf=UnionFind(n) ans=0 ki=[[] for _ in range(n)] for u,v,z in uvz: u,v=u-1,v-1 if uf.same(u,v):continue uf.union(u,v) ki[v].append([u,pow(x,z,mod)]) ki[u].append([v,pow(x,z,mod)]) dfs_order=[] par=[None]*n todo=[[0,-1]] while todo: v,p=todo.pop() dfs_order.append(v) for nv,nc in ki[v]: if nv==p:continue todo.append([nv,v]) par[nv]=v,nc dfs_order.reverse() ans=0 dp=[1]*n for v in dfs_order[:-1]: p,c=par[v] ans+=c*dp[v]*(n-dp[v]) ans%=mod dp[p]+=dp[v] return ans if __name__=='__main__': n,m,x=map(int,input().split()) uvz=[list(map(int,input().split())) for _ in range(m)] #ret0=main0(n,m,x,uvz) ret1=main1(n,m,x,uvz) #print(ret0) print(ret1)