結果
| 問題 |
No.1069 電柱 / Pole (Hard)
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:15:02 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 338 ms / 2,000 ms |
| コード長 | 16,201 bytes |
| コンパイル時間 | 1,888 ms |
| コンパイル使用メモリ | 161,004 KB |
| 実行使用メモリ | 11,520 KB |
| 最終ジャッジ日時 | 2025-05-14 13:16:08 |
| 合計ジャッジ時間 | 5,348 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 79 |
ソースコード
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <iomanip>
#include <set>
#include <map>
#include <limits>
#include <vector>
#include <algorithm> // For reverse, min, max
#include <functional> // For greater template specialization
#include <set> // For std::set
using namespace std;
// Use double for floating point calculations. It provides sufficient precision for this problem.
using Real = double;
const Real INF = numeric_limits<Real>::infinity();
// Epsilon for floating point comparisons. Used to handle potential precision issues.
const Real EPS = 1e-9;
// State structure for Dijkstra's algorithm priority queue
struct State {
Real cost; // Current path cost to this node
int node; // Current node ID
// Comparison operator for min-heap. Priority queue extracts minimum cost state.
bool operator>(const State& other) const {
// If costs are nearly equal, use node ID as a tie-breaker for deterministic behavior.
// This isn't strictly necessary for correctness but can help consistency.
if (abs(cost - other.cost) < EPS) return node > other.node;
// Otherwise, compare costs. Lower cost has higher priority.
return cost > other.cost;
}
};
// Structure representing a path found by the algorithm
struct Path {
Real cost; // Total cost of the path
vector<int> nodes; // Sequence of nodes in the path
// Comparison operator for the priority queue of candidate paths (min-heap).
bool operator>(const Path& other) const {
// If costs are nearly equal, use node sequence lexicographically for tie-breaking.
// This ensures paths with same cost are ordered consistently.
if (abs(cost - other.cost) < EPS) {
return nodes > other.nodes;
}
// Otherwise, compare costs. Lower cost path has higher priority.
return cost > other.cost;
}
// Less than operator overload, useful for sorting or using in containers like std::set.
bool operator<(const Path& other) const {
if (abs(cost - other.cost) > EPS) { // Check difference against epsilon
return cost < other.cost;
}
// If costs are nearly equal, tie-break using node sequence.
return nodes < other.nodes;
}
// Equality operator overload might be useful.
bool operator==(const Path& other) const {
// Check cost equality within epsilon and node sequence equality.
return abs(cost - other.cost) < EPS && nodes == other.nodes;
}
};
// Global variables
int N; // Number of poles (nodes)
vector<pair<Real, Real>> coords; // Coordinates of poles (nodes)
vector<vector<pair<int, Real>>> adj; // Adjacency list representation of the graph: stores pairs {neighbor_node, edge_weight}
/**
* Dijkstra's algorithm implementation.
* Finds the shortest path from start node to end node in the graph.
* Considers dynamically removed nodes and edges specified by the sets.
* This is used within Yen's algorithm to find spur paths.
*
* @param start The starting node ID.
* @param end The target node ID.
* @param removed_nodes A set of node IDs that should be ignored during pathfinding.
* @param removed_edges A set of edges (represented as pairs of node IDs) that should be ignored. Edges are stored canonically {min(u,v), max(u,v)}.
* @return A pair containing the cost of the shortest path and the sequence of nodes in the path. Returns {INF, {}} if no path exists.
*/
pair<Real, vector<int>> dijkstra(int start, int end, const set<int>& removed_nodes, const set<pair<int, int>>& removed_edges) {
// Priority queue for Dijkstra, stores {cost, node} states. Uses min-heap based on cost.
priority_queue<State, vector<State>, greater<State>> pq;
// Distance vector, initialized to infinity for all nodes.
vector<Real> d(N + 1, INF);
// Parent pointer vector, used to reconstruct the path. Initialized to -1.
vector<int> p(N + 1, -1);
// Initialize distance to start node as 0.
d[start] = 0.0;
pq.push({0.0, start});
// Main loop of Dijkstra's algorithm
while (!pq.empty()) {
State current = pq.top();
pq.pop();
int u = current.node;
Real current_cost = current.cost;
// If we pulled a state with cost higher than already known shortest path cost to u, skip it.
// Use epsilon comparison for robustness with floating point numbers.
if (current_cost > d[u] + EPS) {
continue;
}
// Optimization: If we extract the target node, we have found the shortest path to it. Can break early.
if (u == end) {
break;
}
// Explore neighbors of the current node u
for (const auto& edge : adj[u]) {
int v = edge.first; // Neighbor node
Real weight = edge.second; // Edge weight
// Check if the neighbor node v is in the set of removed nodes.
if (removed_nodes.count(v)) {
continue; // Skip this neighbor if it's removed.
}
// Check if the edge (u, v) is in the set of removed edges.
// Use canonical representation {min(u, v), max(u, v)} for the edge lookup.
pair<int, int> current_edge = {min(u, v), max(u, v)};
if (removed_edges.count(current_edge)) {
continue; // Skip this edge if it's removed.
}
// Calculate the cost to reach neighbor v through u.
Real new_cost = current_cost + weight;
// If the new path to v is shorter than the currently known shortest path to v.
// Use epsilon comparison for floating point robustness.
if (new_cost < d[v] - EPS) {
// Update distance to v.
d[v] = new_cost;
// Set u as the parent of v in the shortest path tree.
p[v] = u;
// Push the new state {new_cost, v} to the priority queue.
pq.push({new_cost, v});
}
}
}
// After Dijkstra finishes, check if the end node was reached.
if (d[end] == INF) {
// If distance to end node is still infinity, no path was found.
return {INF, {}};
}
// Reconstruct the shortest path from end node back to start node using parent pointers.
vector<int> path_nodes;
int curr = end;
while (true) {
path_nodes.push_back(curr);
if (curr == start) break; // Stop when we reach the start node.
int parent_node = p[curr]; // Get the parent node.
// Error check: if parent is -1 before reaching start, path reconstruction failed.
if (parent_node == -1) {
return {INF, {}}; // Return indication of failure.
}
curr = parent_node; // Move to the parent node.
}
// The path is reconstructed backwards, so reverse it to get start-to-end order.
reverse(path_nodes.begin(), path_nodes.end());
// Basic validation: Check if the reconstructed path is valid (starts at start, ends at end).
// Handle the special case where start == end.
if (start == end) {
if (abs(d[end] - 0.0) < EPS) return {0.0, {start}}; // Correct path is just [start] with cost 0.
else return {INF, {}}; // Should not happen if start == end and graph is valid.
}
// General validation for start != end.
if (path_nodes.empty() || path_nodes.front() != start || path_nodes.back() != end) {
return {INF, {}}; // Return indication of invalid path.
}
// Return the shortest path cost and the sequence of nodes.
return {d[end], path_nodes};
}
int main() {
// Use fast I/O operations.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int M, K; // M: number of potential connections, K: number of paths to find
cin >> N >> M >> K;
int X, Y; // Start node (power station) X, End node (castle) Y
cin >> X >> Y;
// Read coordinates for each pole (node). Coordinates are 1-indexed.
coords.resize(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> coords[i].first >> coords[i].second;
}
// Read potential connections (edges) and build the adjacency list.
adj.resize(N + 1);
for (int i = 0; i < M; ++i) {
int u, v;
cin >> u >> v;
// Calculate Euclidean distance between poles u and v.
Real weight = sqrt(pow(coords[u].first - coords[v].first, 2) + pow(coords[u].second - coords[v].second, 2));
// Add edge to adjacency list for both directions since connections are bidirectional.
adj[u].push_back({v, weight});
adj[v].push_back({u, weight});
}
// Vector `A` stores the K shortest paths found so far.
vector<Path> A;
// Priority queue `B` stores candidate paths, ordered by cost (min-heap).
priority_queue<Path, vector<Path>, greater<Path>> B;
// Set `found_paths_nodes` stores the node sequences of paths already added to `A`.
// This prevents adding the same path sequence multiple times.
set<vector<int>> found_paths_nodes;
// Find the initial shortest path from X to Y using Dijkstra without any removals.
pair<Real, vector<int>> first_path_info = dijkstra(X, Y, {}, {});
// If a path exists, add it to the candidate priority queue B.
if (first_path_info.first != INF) {
B.push({first_path_info.first, first_path_info.second});
}
// Vector `result_costs` will store the costs of the K shortest paths found.
vector<Real> result_costs;
// Main loop of Yen's K-shortest paths algorithm.
// Continues as long as we need more paths (result_costs.size() < K) and there are candidates in B.
while(result_costs.size() < K && !B.empty()) {
// Extract the path with the minimum cost from the candidate queue B.
Path current_shortest = B.top();
B.pop();
// Check if this path's node sequence has already been found and added to results.
// This check handles cases where Yen's algorithm might generate the same path structure via different spur nodes.
if(found_paths_nodes.count(current_shortest.nodes)) {
continue; // Skip this path if its node sequence is already processed.
}
// This is a new shortest path. Add it to the list A and record its cost.
A.push_back(current_shortest);
result_costs.push_back(current_shortest.cost);
// Mark this path's node sequence as found.
found_paths_nodes.insert(current_shortest.nodes);
// If we have found K paths, terminate the loop.
if (result_costs.size() == K) break;
// Get the node sequence of the path just found (k-th shortest path).
vector<int>& P_k_nodes = current_shortest.nodes;
// Iterate through each node `spur_node` in the path P_k (except the last node).
// Each node `P_k_nodes[i]` serves as a potential "spur node" where a new path can branch off.
for (int i = 0; i < P_k_nodes.size() - 1; ++i) {
int spur_node = P_k_nodes[i]; // The node where the path will deviate.
// The "root path" is the part of P_k from the start node X up to the spur node.
vector<int> root_path_nodes;
Real root_path_cost = 0; // Calculate the cost of the root path.
for(int j=0; j<=i; ++j) {
root_path_nodes.push_back(P_k_nodes[j]);
if(j > 0) {
// Find the weight of the edge between P_k_nodes[j-1] and P_k_nodes[j].
Real edge_w = -1.0; // Initialize with sentinel value.
for(auto& edge : adj[P_k_nodes[j-1]]) {
if(edge.first == P_k_nodes[j]) {
edge_w = edge.second;
break;
}
}
// Basic check: edge weight must be non-negative.
if (edge_w < 0.0) { /* Error: Invalid path or graph data */ }
root_path_cost += edge_w; // Add edge weight to root path cost.
}
}
// Prepare sets of nodes and edges to be temporarily removed for finding the spur path.
// Removed nodes: All nodes in the root path *before* the spur node. This prevents cycles.
set<int> current_removed_nodes;
for (int j = 0; j < i; ++j) {
current_removed_nodes.insert(P_k_nodes[j]);
}
// Removed edges: Edges starting from the spur node that belong to any previously found shortest path (in A)
// which shares the same root path as P_k up to the spur node. This forces the new path to deviate.
set<pair<int, int>> current_removed_edges;
// Iterate through all paths already confirmed shortest (stored in A).
for(const auto& path_info : A) {
const vector<int>& path_nodes = path_info.nodes; // Nodes of a previously found path.
// Check if this path is long enough to potentially share the prefix and have an edge after the spur node.
if (path_nodes.size() > i + 1) {
bool same_prefix = true;
// Compare nodes up to index i (the spur node index).
for(int j=0; j<=i; ++j) {
if (path_nodes[j] != P_k_nodes[j]) {
same_prefix = false; // Prefixes differ.
break;
}
}
// If the prefixes match up to the spur node:
if (same_prefix) {
int u1 = path_nodes[i]; // The spur node (same as P_k_nodes[i]).
int v1 = path_nodes[i+1]; // The node immediately following the spur node in this path.
// Add the edge (u1, v1) to the set of removed edges for the next Dijkstra call.
// Use canonical representation {min(u1, v1), max(u1, v1)} for the edge.
current_removed_edges.insert({min(u1, v1), max(u1, v1)});
}
}
}
// Find the shortest path from the spur node to the target node Y using Dijkstra,
// considering the temporarily removed nodes and edges. This is the "spur path".
pair<Real, vector<int>> spur_path_info = dijkstra(spur_node, Y, current_removed_nodes, current_removed_edges);
// If a valid spur path is found (cost is not INF and path is not empty):
if (spur_path_info.first != INF && !spur_path_info.second.empty()) {
// Construct the complete new path by concatenating the root path and the spur path.
vector<int> total_path_nodes = root_path_nodes;
// Append the spur path nodes, excluding the first node (spur_node itself, already in root_path_nodes).
total_path_nodes.insert(total_path_nodes.end(), spur_path_info.second.begin() + 1, spur_path_info.second.end());
// Calculate the total cost of this new path.
Real total_cost = root_path_cost + spur_path_info.first;
// Add this newly constructed path to the candidate priority queue B,
// but only if its node sequence has not been found previously.
if (!found_paths_nodes.count(total_path_nodes)) {
B.push({total_cost, total_path_nodes});
}
}
}
}
// After the loop finishes, output the costs of the found shortest paths.
cout << fixed << setprecision(10); // Set output precision for floating point numbers.
for (Real cost : result_costs) {
cout << cost << "\n";
}
// If fewer than K paths were found, output -1 for the remaining requested paths.
for (int i = result_costs.size(); i < K; ++i) {
cout << -1 << "\n";
}
return 0;
}