結果
| 問題 |
No.1069 電柱 / Pole (Hard)
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:03:55 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,889 bytes |
| コンパイル時間 | 212 ms |
| コンパイル使用メモリ | 82,884 KB |
| 実行使用メモリ | 89,284 KB |
| 最終ジャッジ日時 | 2025-05-14 13:05:48 |
| 合計ジャッジ時間 | 10,696 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 78 WA * 1 |
ソースコード
import math
import heapq
import sys
# Use sys.stdin.readline for potentially faster input reading
input = sys.stdin.readline
def solve():
# Read N (number of poles), M (number of wire candidates), K (number of shortest paths required)
N, M, K = map(int, input().split())
# Read X (start pole index), Y (end pole index)
X, Y = map(int, input().split())
# Adjust indices to be 0-based for list access
X -= 1
Y -= 1
# Read coordinates for each pole
coords = []
for i in range(N):
coords.append(list(map(int, input().split())))
# Build adjacency list representation of the graph
# adj dictionary maps a pole index u to a list of tuples (v, distance),
# where v is a neighbor and distance is the Euclidean distance between u and v.
adj = {}
for _ in range(M):
# Read the two poles connected by a wire candidate
u, v = map(int, input().split())
u -= 1 # Adjust to 0-based index
v -= 1 # Adjust to 0-based index
# Get coordinates of poles u and v
p1 = coords[u]
p2 = coords[v]
# Calculate Euclidean distance using math.dist for better precision and clarity
dist = math.dist(p1, p2)
# Add the edge to the adjacency list for both directions since the connection is bidirectional
if u not in adj: adj[u] = []
if v not in adj: adj[v] = []
adj[u].append((v, dist))
adj[v].append((u, dist))
# State storage using a list of dictionaries. Each dictionary represents a state in the search.
# The index in this list acts as a unique state ID.
# Each state: {'cost': float (g), 'node': int (u), 'parent_idx': int}
# 'cost' is the actual path cost from X to 'node'.
# 'parent_idx' points to the state ID from which this state was reached, allowing path reconstruction.
states = []
# Add the initial state: starting at node X with cost 0.0 and no parent (-1).
initial_state = {'cost': 0.0, 'node': X, 'parent_idx': -1}
states.append(initial_state)
state_id_counter = 1 # Counter for assigning unique IDs to new states
# Heuristic function h(u): estimates the cost from node u to the target Y.
# Using Euclidean distance (straight-line distance) as it is admissible for shortest path problems on a 2D plane.
# Admissible means h(u) never overestimates the actual shortest path cost from u to Y.
def heuristic(u):
# math.dist calculates the Euclidean distance between two points.
return math.dist(coords[u], coords[Y])
# Priority queue (min-heap) for A* search. Stores tuples:
# (f_cost, path_cost_g, current_node_u, state_id)
# f_cost = path_cost_g + heuristic(current_node_u). The priority queue orders states by f_cost.
pq = []
# Calculate the initial f_cost for the starting node X (g=0.0).
initial_f_cost = 0.0 + heuristic(X)
# Push the initial state onto the priority queue.
heapq.heappush(pq, (initial_f_cost, 0.0, X, 0))
# Dictionary to keep track of how many times a path ending at node 'u' has been finalized (popped from PQ).
# This is used for pruning the search based on K: we only need the K shortest paths.
dist_count = {} # node -> count. Initialized lazily.
results = [] # List to store the costs (g values) of paths found that reach the target Y.
# Main A* search loop: continues as long as the priority queue is not empty
# and we have not yet found K paths to the target Y.
while pq and len(results) < K:
# Pop the state with the lowest estimated total cost (f_cost) from the priority queue.
f, g, u, state_idx = heapq.heappop(pq)
# Goal Check: If the current node u is the target Y.
if u == Y:
results.append(g) # Store the actual path cost g.
# Found one path to Y. Continue the search as we need up to K paths.
continue
# K-Pruning: Check how many paths ending at node u have already been finalized.
current_count = dist_count.get(u, 0) # Get current count, default 0 if not seen before.
if current_count >= K:
# If K paths reaching/passing through node u have already been processed and finalized,
# we can skip exploring further from this state. This significantly reduces the search space,
# especially crucial for small K values.
continue
# Increment the count of finalized paths for node u.
dist_count[u] = current_count + 1
# Path Reconstruction for Simplicity Check:
# Reconstruct the path nodes from the start node X to the current node u
# by following the parent pointers stored in the states list.
# This is necessary to check if adding a neighbor would create a cycle (violate path simplicity).
visited_nodes = set()
curr_state_idx = state_idx
path_reconstruction_valid = True # Safety flag for reconstruction process.
# Iteratively trace back parent pointers until the initial state (parent_idx = -1) is reached.
while curr_state_idx != -1:
# Basic bounds check for robustness, ensuring state index is valid.
if curr_state_idx < 0 or curr_state_idx >= len(states):
path_reconstruction_valid = False
# Optionally log an error or handle this unexpected situation.
# print(f"Error: Invalid state index {curr_state_idx} during path reconstruction.")
break
state = states[curr_state_idx] # Get the state information using its ID.
node_in_path = state['node'] # Get the node associated with this state.
# Add the node to the set of visited nodes for the current path being reconstructed.
visited_nodes.add(node_in_path)
# Move up to the parent state using the stored parent index.
curr_state_idx = state['parent_idx']
# If path reconstruction failed (e.g., due to invalid index), skip processing this state.
if not path_reconstruction_valid: continue
# The visited_nodes set now contains all unique nodes on the simple path from X to u for this state.
# Explore Neighbors: Iterate through neighbors v of the current node u.
if u not in adj: # Check if node u has any outgoing edges defined in adj list.
continue # If no neighbors, nothing to explore from here.
for v, weight in adj[u]: # For each neighbor v connected by an edge with cost 'weight'.
# Path Simplicity Check: Ensure the neighbor 'v' has NOT been visited already on the current path.
# This check prevents cycles and ensures that the paths found are simple.
if v not in visited_nodes:
# Calculate the new path cost (g_new) by adding the edge weight.
g_new = g + weight
# Calculate the heuristic estimate for the neighbor node v.
h_new = heuristic(v)
# Calculate the new estimated total cost (f_new = g_new + h_new).
f_new = g_new + h_new
# Create a new state dictionary representing reaching node 'v' via 'u' from path state `state_idx`.
new_state = {'cost': g_new, 'node': v, 'parent_idx': state_idx}
# Append this new state to the global `states` list.
states.append(new_state)
# Assign the new state its unique ID using the counter.
new_state_idx = state_id_counter
# Increment the counter for the next state ID.
state_id_counter += 1
# Push the new state's information (f_new, g_new, v, new_state_idx) onto the priority queue.
heapq.heappush(pq, (f_new, g_new, v, new_state_idx))
# After the A* search loop finishes:
# Format the output results.
final_results = []
# Sort the found path costs in non-decreasing order.
results.sort()
printed_count = 0
# Select the top K path costs from the sorted results list.
for i in range(len(results)):
if printed_count < K:
# Format the cost to exactly 6 decimal places as required.
final_results.append(f"{results[i]:.6f}")
printed_count += 1
else:
# Stop once K results have been prepared.
break
# If fewer than K paths were found, fill the remaining slots in the output with "-1".
while printed_count < K:
final_results.append("-1")
printed_count += 1
# Print each result string on a new line.
print('\n'.join(final_results))
# Execute the main solve function to run the algorithm.
solve()