結果
| 問題 |
No.1442 I-wate Shortest Path Problem
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:01:03 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,260 bytes |
| コンパイル時間 | 1,728 ms |
| コンパイル使用メモリ | 117,648 KB |
| 実行使用メモリ | 7,840 KB |
| 最終ジャッジ日時 | 2025-05-14 13:02:51 |
| 合計ジャッジ時間 | 8,267 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | TLE * 1 -- * 24 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <tuple> // Not strictly needed now, but good practice if tuples were used
#include <vector> // Included again, harmless
#include <functional> // Potentially needed for std::hash if switching to unordered_map
using namespace std;
// Define long long type for potentially large costs
typedef long long ll;
// Define a large constant to represent infinity
const ll INF = 1e18;
// State representation: pair<int, int>
// first element: node ID.
// Positive values (1 to N) represent cities.
// Negative values (-1 to -K) represent auxiliary nodes for airlines (0 to K-1 respectively).
// second element: bitmask representing the subset of airline companies whose fees have been paid.
using State = pair<int, int>;
// Using std::map to store distances. The key is the State, value is the minimum distance found so far.
// Map is used instead of a large array to save memory, assuming the reachable state space is sparse.
map<State, ll> dist;
// Priority queue for Dijkstra's algorithm. Stores pairs of {distance, State}.
// Uses std::greater to make it a min-priority queue.
priority_queue<pair<ll, State>, vector<pair<ll, State>>, greater<pair<ll, State>>> pq;
int main() {
// Use fast I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of cities
unsigned int K; // Number of airline companies. Use unsigned int for safer bit shifts.
cin >> N >> K;
// Adjacency list for the railway network. Stores pairs of {neighbor_city, cost}.
vector<vector<pair<int, int>>> adj(N + 1);
for (int i = 0; i < N - 1; ++i) {
int u, v, c; // Cities u, v connected by railway with cost c
cin >> u >> v >> c;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
// Store airline information
vector<vector<int>> airline_cities(K); // airline_cities[i] stores list of cities served by airline i (0-indexed)
vector<int> airline_costs(K); // airline_costs[i] stores the cost P_i for airline i
vector<vector<int>> city_to_airlines(N + 1); // city_to_airlines[c] stores list of airline indices (0..K-1) having an airport in city c
for (unsigned int i = 0; i < K; ++i) { // Loop through airlines 0 to K-1
int m; // Number of cities served by airline i
cin >> m >> airline_costs[i]; // Read M_i and P_i
airline_cities[i].resize(m);
for (int j = 0; j < m; ++j) {
cin >> airline_cities[i][j]; // Read city ID
// Store mapping from city ID back to airline index
// Check if city ID is valid (between 1 and N)
if (airline_cities[i][j] >= 1 && airline_cities[i][j] <= N) {
city_to_airlines[airline_cities[i][j]].push_back(i);
}
}
}
int Q; // Number of queries
cin >> Q;
// Process each query
for (int q = 0; q < Q; ++q) {
int start_node, end_node; // Start and end cities for the query
cin >> start_node >> end_node;
// Clear data structures for the new query
dist.clear();
// Clear priority queue. Standard way is to pop elements until empty.
while (!pq.empty()) pq.pop();
// Initialize Dijkstra's algorithm
State initial_state = {start_node, 0}; // Start at city `start_node` with no airlines paid (mask 0)
dist[initial_state] = 0; // Distance to initial state is 0
pq.push({0, initial_state}); // Push initial state into priority queue
// Run Dijkstra's algorithm
while (!pq.empty()) {
// Extract state with minimum distance
// C++17 structured binding: `auto [d, current_state] = ...`
ll d;
State current_state;
tie(d, current_state) = pq.top(); // alternative for C++11/14
// auto [d, current_state] = pq.top(); // C++17
pq.pop();
int u = current_state.first; // Current node ID (city or aux)
int mask = current_state.second; // Current mask
// Check if we found a shorter path to this state already. If so, skip processing.
// Use find() then check iterator and value. Using operator[] directly on map could insert default element.
auto it = dist.find(current_state);
// This check is essential for correctness and efficiency.
// If state isn't in dist map or the stored distance is already smaller, skip.
if (it == dist.end() || it->second < d) {
continue;
}
// Process transitions based on node type (city or auxiliary)
if (u > 0) { // Current node is a city (ID > 0)
// 1. Railway transitions: Move to adjacent city v with cost c
for (auto& edge : adj[u]) {
int v = edge.first;
int cost = edge.second;
State next_state = {v, mask}; // Destination city v, same airline mask
ll new_dist = d + cost; // New total distance
// Update distance if this path is shorter
auto next_it = dist.find(next_state);
if (next_it == dist.end() || new_dist < next_it->second) {
dist[next_state] = new_dist;
pq.push({new_dist, next_state});
}
}
// 2. Airline initiation transitions: Pay for an airline if not already paid
for (int airline_idx : city_to_airlines[u]) {
// Check if the airline_idx bit is NOT set in the mask
if (!((mask >> airline_idx) & 1)) {
int p = airline_costs[airline_idx]; // Cost to pay for this airline
// New state: same city u, updated mask with airline_idx bit set
State next_state = {u, mask | (1 << airline_idx)};
ll new_dist = d + p; // New total distance includes airline fee
// Update distance if this path is shorter
auto next_it = dist.find(next_state);
if (next_it == dist.end() || new_dist < next_it->second) {
dist[next_state] = new_dist;
pq.push({new_dist, next_state});
}
}
}
// 3. Transition to auxiliary node: If airline is paid, move to its aux node (cost 0)
for (int airline_idx : city_to_airlines[u]) {
// Check if the airline_idx bit IS set in the mask
if (((mask >> airline_idx) & 1)) {
// Map airline index `airline_idx` (0..K-1) to negative ID `-(airline_idx + 1)` (-1..-K)
State aux_state = {-(airline_idx + 1), mask};
ll new_dist = d; // Cost 0 transition
// Update distance if this path is shorter
auto next_it = dist.find(aux_state);
if (next_it == dist.end() || new_dist < next_it->second) {
dist[aux_state] = new_dist;
pq.push({new_dist, aux_state});
}
}
}
}
else { // Current node is an auxiliary node (ID < 0)
int airline_idx = -u - 1; // Retrieve 0-based airline index from negative ID
ll current_dist = d; // Distance to the auxiliary node
// Transition from auxiliary node back to all cities served by this airline (cost 0)
for (int v : airline_cities[airline_idx]) {
State city_state = {v, mask}; // Target city v, same mask
ll new_dist = current_dist; // Cost 0 transition
// Update distance if this path is shorter
auto next_it = dist.find(city_state);
if (next_it == dist.end() || new_dist < next_it->second) {
dist[city_state] = new_dist;
pq.push({new_dist, city_state});
}
}
}
}
// After Dijkstra finishes, find the minimum cost to reach the destination city `end_node`
// across all possible final airline masks.
ll final_min_cost = INF;
// Iterate through all possible masks from 0 to 2^K - 1
for (unsigned int final_mask = 0; final_mask < (1u << K); ++final_mask) {
State final_state = {end_node, (int)final_mask}; // State at destination city with this mask
auto it = dist.find(final_state); // Check if this state was reached
if (it != dist.end()) {
final_min_cost = min(final_min_cost, it->second); // Update minimum cost if smaller
}
}
// Output the minimum cost for the query
cout << final_min_cost << "\n";
}
return 0;
}