結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 47 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0