#489153 (PyPy2) No.1069 電柱 / Pole (Hard)

提出ソース

結果

問題	No.1069 電柱 / Pole (Hard)
ユーザー	Alex Wice
提出日時	2020-05-29 23:19:29
言語	PyPy2 (7.3.15)
結果	WA
実行時間	-
コード長	3,418 bytes
コンパイル時間	1,242 ms
コンパイル使用メモリ	76,060 KB
実行使用メモリ	87,124 KB
最終ジャッジ日時	2024-04-24 05:17:41
合計ジャッジ時間	14,706 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	77 ms 77,628 KB
testcase_01	AC	76 ms 77,848 KB
testcase_02	AC	76 ms 77,496 KB
testcase_03	AC	75 ms 77,600 KB
testcase_04	AC	656 ms 87,124 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	AC	105 ms 79,772 KB
testcase_12	AC	152 ms 81,552 KB
testcase_13	AC	252 ms 82,248 KB
testcase_14	AC	199 ms 82,104 KB
testcase_15	AC	198 ms 82,664 KB
testcase_16	WA	-
testcase_17	AC	181 ms 81,756 KB
testcase_18	AC	199 ms 82,180 KB
testcase_19	AC	232 ms 83,172 KB
testcase_20	AC	132 ms 81,480 KB
testcase_21	AC	197 ms 82,568 KB
testcase_22	AC	146 ms 81,416 KB
testcase_23	AC	304 ms 82,680 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	AC	110 ms 81,784 KB
testcase_30	AC	87 ms 79,264 KB
testcase_31	AC	75 ms 77,984 KB
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	AC	74 ms 77,580 KB
testcase_36	WA	-
testcase_37	AC	159 ms 81,708 KB
testcase_38	AC	157 ms 81,640 KB
testcase_39	WA	-
testcase_40	AC	145 ms 81,436 KB
testcase_41	AC	168 ms 81,872 KB
testcase_42	AC	172 ms 82,024 KB
testcase_43	AC	157 ms 81,352 KB
testcase_44	WA	-
testcase_45	AC	175 ms 81,888 KB
testcase_46	AC	193 ms 82,604 KB
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	AC	131 ms 81,444 KB
testcase_51	WA	-
testcase_52	AC	127 ms 81,504 KB
testcase_53	WA	-
testcase_54	AC	77 ms 77,856 KB
testcase_55	WA	-
testcase_56	AC	74 ms 77,868 KB
testcase_57	AC	88 ms 79,804 KB
testcase_58	AC	75 ms 77,956 KB
testcase_59	WA	-
testcase_60	AC	74 ms 77,992 KB
testcase_61	WA	-
testcase_62	AC	73 ms 77,472 KB
testcase_63	AC	74 ms 78,088 KB
testcase_64	AC	95 ms 80,160 KB
testcase_65	AC	75 ms 77,880 KB
testcase_66	WA	-
testcase_67	AC	76 ms 77,860 KB
testcase_68	WA	-
testcase_69	AC	131 ms 81,976 KB
testcase_70	AC	133 ms 82,192 KB
testcase_71	AC	133 ms 81,840 KB
testcase_72	AC	106 ms 80,060 KB
testcase_73	AC	116 ms 81,672 KB
testcase_74	AC	146 ms 82,960 KB
testcase_75	AC	146 ms 82,488 KB
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	AC	222 ms 82,340 KB
testcase_80	WA	-
testcase_81	AC	185 ms 82,716 KB
testcase_82	AC	185 ms 82,340 KB

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

ソースコード

raw source code

FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

####
from collections import defaultdict as ddic
import heapq

def solve(N,M,K,X,Y,A,B):
    # A: powerpole locations
    # B: wires
    # Shortest path X to Y
    X-=1;Y-=1
    graph = [set() for _ in xrange(N)]
    killed = set()
    def get(node):
        return graph[node] if node not in killed else ()
    
    for u, v in B:
        u-=1;v-=1
        graph[u].add(v)
        graph[v].add(u)
    def dist_2d(u, v):
        x1, y1 = A[u]
        x2, y2 = A[v]
        return ((x1-x2)**2 + (y1-y2)**2)**0.5

    INF = float('inf')
    def dijkstra(source, target):
        
        dist = ddic(lambda: INF)
        dist[source] = 0
        parent = {}
        pq = [[0, source]]
        while pq:
            d, node = heapq.heappop(pq)
            if d > dist[node]: continue
            for nei in get(node):
                w = dist_2d(node, nei)
                d2 = d + w
                if d2 < dist[nei]:
                    dist[nei] = d2
                    parent[nei] = node
                    heapq.heappush(pq, [d2, nei])
        path1 = [target]
        while path1[-1] != source:
            try:
                path1.append(parent[path1[-1]])
            except:
                return [None, None]
        path1 = path1[::-1]
        #print("!", dist, source, target)
        return [dist[target], path1]

    paths = [dijkstra(X, Y)]
    # paths[i] = a distance, then actual path
    carried = []
    carried_set = set()
    
    for k in xrange(1, K):
        
        for i in xrange(len(paths[-1][1]) - 1):
            spur = paths[-1][1][i]

            dead_edges = []
            for pathcand in paths:
                if all(pathcand[1][j] == paths[-1][1][j]
                       for j in xrange(i + 1)):
                    u = pathcand[1][i]
                    v = pathcand[1][i + 1]
                    graph[u].discard(v)
                    graph[v].discard(u)
                    dead_edges.append([u, v])

            for j in xrange(i):
                killed.add(paths[-1][1][j])

            spurcost, spurpath = dijkstra(spur, Y)
            if spurcost is None: break
            
            totpath = paths[-1][1][:i] + spurpath
            for j in xrange(i):
                u = paths[-1][1][j]
                v = paths[-1][1][j+1]
                spurcost += dist_2d(u,v)
            pathtuple = tuple(totpath)
            if pathtuple not in carried_set:
                carried_set.add(pathtuple)
                carried.append((spurcost, totpath))

            for j in xrange(i):
                killed.discard(paths[-1][1][j])
            for u,v in dead_edges:
                graph[u].add(v);graph[v].add(u)
                
        carried.sort(reverse=True)
        if not carried:
            break
        paths.append(carried.pop())
        carried_set.discard(tuple(paths[-1][1]))

    for i in xrange(K):
        if i < len(paths):
            print paths[i][0]
        else:
            print -1
    
    
N,M,K = rrm()
X,Y = rrm()
A = [rrm()  for _ in xrange(N)]
B = [rrm() for _ in xrange(M)]
solve(N, M, K, X, Y, A, B)

yukicoder

結果

テストケース

ソースコード