結果
| 問題 |
No.1775 Love Triangle 2
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:10:00 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 8,431 bytes |
| コンパイル時間 | 1,064 ms |
| コンパイル使用メモリ | 109,988 KB |
| 実行使用メモリ | 766,460 KB |
| 最終ジャッジ日時 | 2025-05-14 13:11:27 |
| 合計ジャッジ時間 | 10,969 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 4 MLE * 1 -- * 85 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <tuple> // Not strictly necessary but good practice for pair/tuple usage
#include <string> // Potentially needed for bitset operations, though usually not directly
#include <unordered_map> // Use unordered_map for potential speedup
#include <functional> // Required for std::hash
// Constants and Type Definitions
const int MAXN_VAL = 100; // Maximum number of students
const int MAXN_IDX = MAXN_VAL + 1; // Array size needed for 1-based indexing up to 100
const int MAX_BITS = MAXN_VAL; // The number of bits needed for the bitset Mask
using Mask = std::bitset<MAX_BITS>; // Use std::bitset to represent the set of visited students
// Global variables
std::vector<int> non_adj[MAXN_IDX]; // Adjacency list for the complement graph (stores non-friends)
bool is_friend[MAXN_IDX][MAXN_IDX]; // Matrix to check friendship status quickly
int N; // Number of students
int X, Y, Z; // The three special students who must be included
// Custom hash function structure for std::pair<int, Mask>
// This is required to use std::pair<int, Mask> as a key in std::unordered_map
template <class T1, class T2>
struct pair_hash {
std::size_t operator() (const std::pair<T1, T2>& p) const {
// Get hash value for the first element (int)
auto hash1 = std::hash<T1>{}(p.first);
// Get hash value for the second element (Mask/std::bitset)
// std::hash<std::bitset<N>> is provided by the standard library since C++11
auto hash2 = std::hash<Mask>{}(p.second);
// Combine the two hash values.
// Using a method similar to boost::hash_combine to reduce collisions.
// It involves XORing and bit shifts with a large prime number constant (golden ratio conjugate).
size_t seed = 0; // Initialize seed for combining
// Combine hash1 into seed
seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// Combine hash2 into seed
seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
// A simpler alternative combination method (might have more collisions):
// return hash1 ^ (hash2 << 1);
}
};
// Use std::unordered_map to store the shortest path length found so far for each state (vertex, mask).
// The key is std::pair<int, Mask>, the value is int (path length).
// Use the custom hash function `pair_hash` defined above.
std::unordered_map<std::pair<int, Mask>, int, pair_hash<int, Mask>> dist;
int main() {
// Use fast I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int M; // Number of friend pairs
std::cin >> N >> M; // Read number of students and friend pairs
std::cin >> X >> Y >> Z; // Read the IDs of the three special students
// Read friend pairs and populate the is_friend matrix
// Initialize is_friend to false (global bool arrays are default initialized to false)
for (int i = 0; i < M; ++i) {
int u, v;
std::cin >> u >> v;
is_friend[u][v] = true;
is_friend[v][u] = true; // Friendship is symmetric
}
// Build the non-adjacency list (edges of the complement graph)
// An edge (i, j) exists if i and j are different students and are not friends
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
if (i != j && !is_friend[i][j]) {
non_adj[i].push_back(j);
}
}
}
// Initialize the BFS queue
// The queue stores pairs of (current vertex, visited mask)
std::queue<std::pair<int, Mask>> q;
// Create the initial mask containing only student X
// We use 0-based indexing for bitset positions: student k corresponds to bit k-1
Mask initial_mask_x;
initial_mask_x[X-1] = 1;
// Initialize BFS starting from neighbors of X which are not friends with X
// These form the first step of paths starting from X
for (int neighbor : non_adj[X]) {
// Create the mask for the path X -> neighbor
Mask first_step_mask = initial_mask_x;
first_step_mask[neighbor-1] = 1; // Mark neighbor as visited (using 0-based index)
// The state is defined by the endpoint vertex (neighbor) and the set of visited vertices (mask)
std::pair<int, Mask> state = {neighbor, first_step_mask};
// Store the length of the path (number of vertices) to reach this state
// The path X -> neighbor involves 2 vertices.
dist[state] = 2;
q.push(state); // Add the initial states to the queue
}
int min_len_found = -1; // Stores the minimum cycle length found, initialized to -1 (meaning not found yet)
// Start the Breadth-First Search
while (!q.empty()) {
// Get the current state from the front of the queue
auto current_state = q.front();
q.pop();
int u = current_state.first; // Current vertex at the end of the path
Mask current_mask = current_state.second; // Mask representing visited vertices in the path
// Retrieve the length of the path leading to this state from the distance map
// This lookup should be safe as the state must exist in the map if it's in the queue
int current_len = dist[current_state];
// Check if we can complete a cycle by moving from the current vertex u back to the start vertex X
// This is allowed only if u and X are not friends
if (!is_friend[u][X]) {
// If the path back to X is allowed, check if the required students Y and Z are included in the path
// Use 0-based indexing for bitset checks
if (current_mask[Y-1] && current_mask[Z-1]) {
// If Y and Z are included, we have found a valid cycle including X, Y, Z
min_len_found = current_len; // Record the length of this cycle
// Since BFS explores paths layer by layer (by length), the first valid cycle found is guaranteed
// to be one with the minimum possible length. We can stop the search.
break;
}
}
// Optimization: If we have already found a valid cycle, we can prune the search space.
// Any path currently being explored that has a length greater than or equal to the minimum found cycle length
// cannot lead to a shorter cycle.
if (min_len_found != -1 && current_len >= min_len_found) {
continue; // Skip exploring further from this state
}
// Explore neighbors 'v' of the current vertex 'u' in the non-adjacency graph
for (int v : non_adj[u]) {
// Check if neighbor 'v' has already been visited in the current path
// Use 0-based indexing for bitset check
if (current_mask[v-1]) {
continue; // If v is already in the mask, skip it to avoid cycles within the path itself
}
// If v has not been visited, create the next state by extending the path
Mask next_mask = current_mask; // Copy the current mask
next_mask[v-1] = 1; // Add v to the visited set (using 0-based index)
std::pair<int, Mask> next_state = {v, next_mask}; // Define the new state: endpoint v, updated mask
// Check if this state {v, next_mask} has been visited before using `find()` on the distance map.
// `find()` returns an iterator to the element if found, or `dist.end()` if not found.
if (dist.find(next_state) == dist.end()) {
// If the state has not been visited before:
dist[next_state] = current_len + 1; // Record the path length (current length + 1)
q.push(next_state); // Add the new state to the queue for exploration
}
// Note: In a standard BFS on unweighted graphs like this one, the first time a state is reached
// is guaranteed to be via a shortest path (in terms of number of vertices/edges).
// Therefore, we do not need to update the distance or re-queue the state if it's encountered again later.
}
}
// After the BFS completes (either found shortest cycle or queue is empty), output the result.
std::cout << min_len_found << std::endl;
return 0; // Indicate successful execution
}