結果
| 問題 |
No.1301 Strange Graph Shortest Path
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:17:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,466 bytes |
| コンパイル時間 | 1,174 ms |
| コンパイル使用メモリ | 93,104 KB |
| 実行使用メモリ | 16,176 KB |
| 最終ジャッジ日時 | 2025-05-14 13:18:32 |
| 合計ジャッジ時間 | 8,338 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 WA * 5 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <vector> // Required for vector<bool>
using namespace std;
// Use long long for potentially large path costs as edge weights can be up to 10^9
// and path length up to N-1 edges. Max cost could be around 10^5 * 10^9 = 10^14.
typedef long long ll;
// Define a constant for infinity, large enough for path costs.
// Max possible path cost is roughly N * max(d_i), sum could be twice that.
// 2 * 10^5 * 10^9 = 2 * 10^14. Needs to be larger than that.
const ll INF = 4e18;
// Structure to represent an edge in the graph
struct Edge {
int to; // Destination vertex of the edge
ll cost_c; // Initial cost (cost for the first traversal)
ll cost_d; // Changed cost (cost for the second traversal)
int id; // Unique identifier for the edge (index from 0 to M-1)
};
// Structure for states in Dijkstra's priority queue
struct State {
ll dist; // Current shortest distance found to this vertex from the source
int u; // Vertex identifier
// Overload greater-than operator for min-priority queue functionality
// The priority queue will prioritize states with smaller distances.
bool operator>(const State& other) const {
return dist > other.dist;
}
};
// Global variables for graph representation and Dijkstra state
vector<vector<Edge>> adj; // Adjacency list representation of the graph
vector<ll> dist; // Stores shortest distances from the source vertex in Dijkstra
vector<int> parent_edge; // Stores the ID of the edge used to reach a vertex on the shortest path tree
vector<int> parent_node; // Stores the predecessor vertex on the shortest path tree
vector<bool> used_in_first_path; // Tracks which edges (by ID) were part of the first shortest path (1 to N)
// Dijkstra's algorithm implementation
// Parameters:
// start_node: The source vertex for this Dijkstra run
// N: Total number of vertices in the graph (used for initializing vectors)
// M: Total number of edges (used for sizing used_in_first_path vector)
// first_run: Boolean flag. If true, this is the first Dijkstra run (1->N), using initial costs c_i.
// If false, this is the second run (N->1), using potentially updated costs d_i for edges used in the first run.
void dijkstra(int start_node, int N, int M, bool first_run) {
// Initialize distances to infinity for all vertices
dist.assign(N + 1, INF);
// Initialize parent edge IDs and parent nodes to -1 (indicating no parent yet)
parent_edge.assign(N + 1, -1);
parent_node.assign(N + 1, -1);
dist[start_node] = 0; // Distance from the source vertex to itself is 0
// Min-priority queue to manage vertices to visit, ordered by distance
priority_queue<State, vector<State>, greater<State>> pq;
pq.push({0, start_node}); // Push the starting state onto the queue
while (!pq.empty()) {
State current = pq.top(); // Get the state (vertex) with the smallest distance
pq.pop();
ll d = current.dist; // Current shortest distance to vertex u
int u = current.u; // Current vertex u
// Optimization: If we've already found a shorter path to u, this state is outdated, skip it.
if (d > dist[u]) {
continue;
}
// Iterate through all edges outgoing from the current vertex u
for (const auto& edge : adj[u]) {
int v = edge.to; // Neighbor vertex
ll current_cost; // The cost of traversing this edge (u, v)
// Determine the cost of the edge based on the run type (first or second)
if (first_run) {
// In the first run (path 1 -> N), always use the initial cost c_i
current_cost = edge.cost_c;
} else {
// In the second run (path N -> 1), check if this edge was used in the first path
// Check bounds edge.id < used_in_first_path.size() is implicitly handled since edge.id is 0..M-1
if (used_in_first_path[edge.id]) {
// If the edge was used in the first path, its cost is now d_i
current_cost = edge.cost_d;
} else {
// If the edge was not used in the first path, its cost remains c_i
current_cost = edge.cost_c;
}
}
// Relaxation step: If path through u offers a shorter distance to v
// Check dist[u] != INF to avoid potential overflow issues with INF + cost, although technically not needed if start_node is reachable.
if (dist[u] != INF && dist[u] + current_cost < dist[v]) {
dist[v] = dist[u] + current_cost; // Update the shortest distance to v
parent_node[v] = u; // Set u as the parent of v in the shortest path tree
parent_edge[v] = edge.id; // Record the ID of the edge used to reach v
pq.push({dist[v], v}); // Push the updated state (distance and vertex v) to the priority queue
}
}
}
}
int main() {
// Use fast I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of vertices
int M; // Number of edges
cin >> N >> M;
adj.resize(N + 1); // Resize adjacency list to hold N+1 vertices (using 1-based indexing)
// Read M edges from input and build the graph
for (int i = 0; i < M; ++i) {
int u, v; // Vertices connected by the edge
ll c, d; // Initial cost c, updated cost d
cin >> u >> v >> c >> d;
// Add the edge to the adjacency list for both endpoints since graph is undirected
// Store the edge ID 'i' with the edge data.
adj[u].push_back({v, c, d, i});
adj[v].push_back({u, c, d, i});
}
// Initialize the vector tracking used edges. Size M for M edges with IDs 0..M-1. All initialized to false.
used_in_first_path.assign(M, false);
// --- First Dijkstra Run: 1 to N ---
// Compute the shortest path from vertex 1 to vertex N using initial edge costs (c_i).
dijkstra(1, N, M, true);
ll cost1 = dist[N]; // Store the cost of this shortest path 1 -> N.
// Check reachability. The problem guarantees the graph is connected, so N should always be reachable from 1 if N >= 1.
if (cost1 == INF) {
// This case indicates N is unreachable. Based on problem constraints, this shouldn't happen.
// Outputting -1 or appropriate error message might be necessary in a general case.
cout << -1 << endl;
return 0;
}
// --- Backtrack to Mark Edges Used in First Path ---
// Trace the path back from N to 1 using the parent pointers stored during Dijkstra.
// Mark the edges that belong to this shortest path 1 -> N.
int curr = N;
// Loop continues as long as we haven't reached vertex 1 and the current node has a valid parent.
// The check parent_node[curr] != -1 handles the case where N=1 or if somehow the path is broken.
while (curr != 1 && parent_node[curr] != -1) {
int edge_id = parent_edge[curr]; // Get the ID of the edge used to reach `curr` from its parent.
if (edge_id != -1) { // Check if the edge ID is valid.
used_in_first_path[edge_id] = true; // Mark this edge as used.
curr = parent_node[curr]; // Move to the parent node to continue backtracking.
} else {
// This case should not happen if N is reachable from 1 and N != 1.
break;
}
}
// --- Second Dijkstra Run: N to 1 ---
// Compute the shortest path from vertex N back to vertex 1.
// The edge costs used in this run depend on whether they were part of the first path (1 -> N).
// If an edge was used, its cost is d_i; otherwise, it's c_i.
dijkstra(N, N, M, false);
ll cost2 = dist[1]; // Store the cost of this shortest path N -> 1.
// Check reachability for the return path. Again, guaranteed by connectivity.
if (cost2 == INF) {
// Similar to the first path, if 1 is unreachable from N, output -1. Should not happen here.
cout << -1 << endl;
return 0;
}
// --- Output Result ---
// The total minimum cost for the round trip 1 -> N -> 1 is the sum of the costs
// calculated from the two Dijkstra runs.
cout << cost1 + cost2 << endl;
return 0;
}