#565335 (PyPy3) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	uni_python
提出日時	2020-10-10 00:04:24
言語	PyPy3 (7.3.15)
結果	AC
実行時間	790 ms / 2,000 ms
コード長	5,039 bytes
コンパイル時間	465 ms
コンパイル使用メモリ	86,956 KB
実行使用メモリ	153,880 KB
最終ジャッジ日時	2023-09-27 20:19:20
合計ジャッジ時間	48,951 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	158 ms 79,560 KB
testcase_01	AC	157 ms 79,388 KB
testcase_02	AC	154 ms 79,156 KB
testcase_03	AC	158 ms 79,324 KB
testcase_04	AC	157 ms 79,468 KB
testcase_05	AC	156 ms 79,412 KB
testcase_06	AC	158 ms 79,396 KB
testcase_07	AC	163 ms 79,384 KB
testcase_08	AC	163 ms 79,412 KB
testcase_09	AC	162 ms 79,312 KB
testcase_10	AC	159 ms 79,408 KB
testcase_11	AC	163 ms 79,488 KB
testcase_12	AC	167 ms 79,316 KB
testcase_13	AC	169 ms 80,120 KB
testcase_14	AC	175 ms 79,936 KB
testcase_15	AC	166 ms 79,500 KB
testcase_16	AC	165 ms 79,420 KB
testcase_17	AC	170 ms 79,480 KB
testcase_18	AC	169 ms 79,564 KB
testcase_19	AC	165 ms 79,320 KB
testcase_20	AC	165 ms 79,944 KB
testcase_21	AC	165 ms 79,416 KB
testcase_22	AC	164 ms 79,372 KB
testcase_23	AC	170 ms 79,444 KB
testcase_24	AC	168 ms 80,168 KB
testcase_25	AC	159 ms 79,204 KB
testcase_26	AC	163 ms 79,904 KB
testcase_27	AC	165 ms 80,012 KB
testcase_28	AC	165 ms 79,916 KB
testcase_29	AC	161 ms 79,388 KB
testcase_30	AC	159 ms 79,284 KB
testcase_31	AC	165 ms 79,820 KB
testcase_32	AC	161 ms 79,128 KB
testcase_33	AC	162 ms 79,980 KB
testcase_34	AC	162 ms 79,916 KB
testcase_35	AC	161 ms 79,908 KB
testcase_36	AC	165 ms 80,040 KB
testcase_37	AC	163 ms 80,076 KB
testcase_38	AC	161 ms 80,056 KB
testcase_39	AC	160 ms 79,336 KB
testcase_40	AC	162 ms 79,748 KB
testcase_41	AC	170 ms 80,192 KB
testcase_42	AC	161 ms 79,416 KB
testcase_43	AC	207 ms 81,260 KB
testcase_44	AC	166 ms 79,736 KB
testcase_45	AC	169 ms 80,240 KB
testcase_46	AC	197 ms 81,812 KB
testcase_47	AC	172 ms 80,116 KB
testcase_48	AC	186 ms 80,960 KB
testcase_49	AC	162 ms 79,924 KB
testcase_50	AC	206 ms 82,380 KB
testcase_51	AC	200 ms 81,808 KB
testcase_52	AC	205 ms 82,672 KB
testcase_53	AC	192 ms 81,176 KB
testcase_54	AC	198 ms 82,240 KB
testcase_55	AC	193 ms 82,424 KB
testcase_56	AC	159 ms 79,368 KB
testcase_57	AC	189 ms 81,076 KB
testcase_58	AC	187 ms 81,716 KB
testcase_59	AC	155 ms 80,040 KB
testcase_60	AC	166 ms 80,028 KB
testcase_61	AC	194 ms 82,112 KB
testcase_62	AC	163 ms 80,108 KB
testcase_63	AC	310 ms 88,708 KB
testcase_64	AC	255 ms 85,488 KB
testcase_65	AC	297 ms 88,876 KB
testcase_66	AC	291 ms 88,940 KB
testcase_67	AC	250 ms 86,260 KB
testcase_68	AC	294 ms 89,152 KB
testcase_69	AC	311 ms 88,640 KB
testcase_70	AC	254 ms 84,092 KB
testcase_71	AC	251 ms 86,248 KB
testcase_72	AC	303 ms 89,140 KB
testcase_73	AC	259 ms 86,444 KB
testcase_74	AC	307 ms 88,052 KB
testcase_75	AC	282 ms 88,156 KB
testcase_76	AC	216 ms 83,636 KB
testcase_77	AC	292 ms 87,492 KB
testcase_78	AC	316 ms 86,916 KB
testcase_79	AC	305 ms 87,140 KB
testcase_80	AC	312 ms 87,548 KB
testcase_81	AC	303 ms 87,312 KB
testcase_82	AC	300 ms 87,412 KB
testcase_83	AC	720 ms 140,024 KB
testcase_84	AC	712 ms 135,692 KB
testcase_85	AC	532 ms 118,048 KB
testcase_86	AC	645 ms 132,532 KB
testcase_87	AC	677 ms 133,160 KB
testcase_88	AC	330 ms 90,488 KB
testcase_89	AC	728 ms 140,120 KB
testcase_90	AC	569 ms 121,416 KB
testcase_91	AC	490 ms 109,552 KB
testcase_92	AC	387 ms 98,716 KB
testcase_93	AC	642 ms 126,860 KB
testcase_94	AC	601 ms 123,044 KB
testcase_95	AC	593 ms 123,188 KB
testcase_96	AC	682 ms 133,964 KB
testcase_97	AC	463 ms 107,932 KB
testcase_98	AC	698 ms 134,648 KB
testcase_99	AC	575 ms 114,852 KB
testcase_100	AC	790 ms 144,440 KB
testcase_101	AC	372 ms 97,572 KB
testcase_102	AC	315 ms 89,472 KB
testcase_103	AC	371 ms 98,468 KB
testcase_104	AC	424 ms 104,292 KB
testcase_105	AC	601 ms 126,796 KB
testcase_106	AC	449 ms 109,708 KB
testcase_107	AC	726 ms 140,136 KB
testcase_108	AC	724 ms 138,568 KB
testcase_109	AC	615 ms 125,576 KB
testcase_110	AC	581 ms 121,976 KB
testcase_111	AC	615 ms 128,388 KB
testcase_112	AC	404 ms 103,688 KB
testcase_113	AC	565 ms 123,696 KB
testcase_114	AC	452 ms 108,948 KB
testcase_115	AC	325 ms 89,916 KB
testcase_116	AC	490 ms 111,324 KB
testcase_117	AC	411 ms 104,504 KB
testcase_118	AC	668 ms 133,448 KB
testcase_119	AC	513 ms 114,584 KB
testcase_120	AC	662 ms 131,232 KB
testcase_121	AC	379 ms 100,448 KB
testcase_122	AC	475 ms 110,660 KB
testcase_123	AC	153 ms 79,172 KB
testcase_124	AC	674 ms 153,100 KB
testcase_125	AC	693 ms 153,880 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
input=sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
木+1本で，閉路が一つあるのでその周状がダメ
"""
def main():

    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        """
        
        #最短のpathをたす
        
        
        class Edge():
            #重み付き有向辺
            
            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost
        
        def __init__(self, V):
            #引数Vは頂点数
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数
        
        #proparty - 辺の数
        def E(self):
            return self._E
        
        #proparty - 頂点数
        def V(self):
            return self._V
        
        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1
            
        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2
            
        def shortest_path(self,s,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            
            que = [] #priority queue
            d = [float("inf")] * self.V()
            prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
            
            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)
                
                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue
                    
                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新
                        prev[e.to] = v
                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加
            
            #sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)
                        
            return d,path
    ########################

    mod=10**9+7
    N=I()
    adj=[[]for _ in range(N)]
    A=[]
    B=[]
    from collections import defaultdict
    dd = defaultdict(int)
    for i in range(N):
        a,b=MI()
        a-=1
        b-=1
        A.append(a)
        B.append(b)
        adj[a].append(b)
        adj[b].append(a)
        
        if a>b:
            a,b=b,a
            
        dd[(a,b)]=i+1
        
    import queue
    q=queue.Queue()
    q.put((0,-1))
    used=[0]*N
    edge=[-1,-1]
    
    while not q.empty():
        v,p=q.get()
        for nv in adj[v]:
            if nv!=p:
                if used[nv]:
                    edge=[v,nv]
                else:
                    used[nv]=1
                    q.put((nv,v))
    
    #これを抜けば木になって，lca閉路出せば終了，ダイクストラでいいや
    st=edge[0]
    en=edge[1]
    
    if st>en:
        st,en=en,st
    
    adj[st].remove(en)
    adj[en].remove(st)
    
    djk=Dijkstra(N)
    for v in range(N):
        for nv in adj[v]:
            djk.add(v,nv,1)
            
    d,path=djk.shortest_path(st,en)
    
    ans=[dd[(st,en)]]
    
    for i in range(len(path)-1):
        now=path[i]
        nxt=path[i+1]
        if now>nxt:
            now,nxt=nxt,now
        ans.append(dd[(now,nxt)])
    
    ans.sort()
    print(len(ans))
    print(' '.join(map(str, ans)))
    # print(st+1,en+1)
    

    
    
    


main()

yukicoder

結果

テストケース

ソースコード