#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,068 ms
コンパイル使用メモリ	76,836 KB
実行使用メモリ	87,144 KB
最終ジャッジ日時	2024-11-06 12:14:27
合計ジャッジ時間	16,533 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	86 ms 77,848 KB
testcase_01	AC	85 ms 77,940 KB
testcase_02	AC	87 ms 77,688 KB
testcase_03	AC	87 ms 77,876 KB
testcase_04	AC	660 ms 87,144 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	AC	112 ms 79,608 KB
testcase_12	AC	163 ms 81,576 KB
testcase_13	AC	280 ms 82,592 KB
testcase_14	AC	218 ms 82,012 KB
testcase_15	AC	221 ms 82,912 KB
testcase_16	WA	-
testcase_17	AC	179 ms 82,144 KB
testcase_18	AC	234 ms 82,188 KB
testcase_19	AC	265 ms 83,048 KB
testcase_20	AC	155 ms 81,596 KB
testcase_21	AC	238 ms 81,808 KB
testcase_22	AC	179 ms 81,440 KB
testcase_23	AC	335 ms 82,816 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	AC	133 ms 81,668 KB
testcase_30	AC	101 ms 79,516 KB
testcase_31	AC	85 ms 77,956 KB
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	AC	87 ms 77,964 KB
testcase_36	WA	-
testcase_37	AC	174 ms 81,716 KB
testcase_38	AC	184 ms 82,032 KB
testcase_39	WA	-
testcase_40	AC	170 ms 81,056 KB
testcase_41	AC	195 ms 81,744 KB
testcase_42	AC	189 ms 82,148 KB
testcase_43	AC	179 ms 81,356 KB
testcase_44	WA	-
testcase_45	AC	201 ms 82,268 KB
testcase_46	AC	231 ms 82,516 KB
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	AC	152 ms 81,296 KB
testcase_51	WA	-
testcase_52	AC	148 ms 81,436 KB
testcase_53	WA	-
testcase_54	AC	87 ms 77,816 KB
testcase_55	WA	-
testcase_56	AC	85 ms 77,992 KB
testcase_57	AC	101 ms 79,752 KB
testcase_58	AC	88 ms 77,868 KB
testcase_59	WA	-
testcase_60	AC	85 ms 77,864 KB
testcase_61	WA	-
testcase_62	AC	83 ms 77,980 KB
testcase_63	AC	84 ms 77,872 KB
testcase_64	AC	111 ms 79,916 KB
testcase_65	AC	86 ms 77,880 KB
testcase_66	WA	-
testcase_67	AC	84 ms 77,728 KB
testcase_68	WA	-
testcase_69	AC	150 ms 82,224 KB
testcase_70	AC	153 ms 81,932 KB
testcase_71	AC	153 ms 82,092 KB
testcase_72	AC	114 ms 80,040 KB
testcase_73	AC	129 ms 81,688 KB
testcase_74	AC	164 ms 82,604 KB
testcase_75	AC	166 ms 82,492 KB
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	AC	250 ms 82,948 KB
testcase_80	WA	-
testcase_81	AC	217 ms 82,592 KB
testcase_82	AC	205 ms 82,592 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

結果

テストケース

ソースコード