結果

問題 No.1480 Many Complete Graphs
ユーザー qwewe
提出日時 2025-05-14 13:09:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 118 ms / 2,000 ms
コード長 7,005 bytes
コンパイル時間 1,069 ms
コンパイル使用メモリ 85,772 KB
実行使用メモリ 21,676 KB
最終ジャッジ日時 2025-05-14 13:11:03
合計ジャッジ時間 6,168 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // For numeric_limits to get maximum value for long long

using namespace std;

// Use long long for distances and edge weights because they can be large
// (up to N/2 + c_i approx 10^5/2 + 10^9 = 10^9, path length can be N * 10^9 up to 10^14)
typedef long long ll;

// Define infinity carefully to avoid overflow issues when adding weights. 
// Using half of the maximum value of long long is a safe choice.
const ll INF = numeric_limits<ll>::max() / 2; 

// Structure to represent an edge in the adjacency list
struct Edge {
    int to; // Destination vertex index
    ll weight; // Edge weight
};

// Structure for storing state in Dijkstra's priority queue
// Stores the distance to a node and the node index
struct State {
    ll dist; // Distance from source vertex (vertex 1)
    int node; // Vertex index

    // Overload operator> for min-heap behavior in priority_queue
    // The priority queue needs to extract the state with the smallest distance
    bool operator>(const State& other) const {
        return dist > other.dist;
    }
};

int main() {
    // Use fast I/O to potentially speed up reading large inputs
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; // Number of original vertices (1 to N)
    int M; // Number of operations that add edges
    cin >> N >> M;

    // The total number of vertices in our augmented graph will be N original vertices
    // plus 4 auxiliary vertices for each of the M operations.
    int total_vertices = N + 4 * M;
    
    // Adjacency list representation of the graph. Using vector of vectors.
    // Size is total_vertices + 1 to accommodate 1-based indexing for vertices 1 to N
    // and auxiliary vertices N+1 to N+4M.
    vector<vector<Edge>> adj(total_vertices + 1); 

    // Process each operation to construct the graph edges using auxiliary nodes
    for (int i = 1; i <= M; ++i) {
        int k; // Number of vertices involved in this operation's clique
        ll c; // Constant part of edge weight for edges added in this operation
        cin >> k >> c;
        
        vector<int> s(k); // Store vertex indices for the current operation
        for (int j = 0; j < k; ++j) {
            cin >> s[j];
        }

        // Calculate indices for the 4 auxiliary nodes specific to operation i.
        // These nodes help model the clique structure efficiently.
        // We assign indices N+1 onwards for auxiliary nodes.
        // For operation `i`, auxiliary nodes are N+4*(i-1)+1 to N+4*(i-1)+4.
        int P_even_idx = N + 4 * (i - 1) + 1; // Auxiliary node for paths between two even vertices
        int P_odd_idx  = N + 4 * (i - 1) + 2; // Auxiliary node for paths between two odd vertices
        int Q_even_idx = N + 4 * (i - 1) + 3; // Auxiliary node handling paths starting from an even vertex going to an odd vertex
        int Q_odd_idx  = N + 4 * (i - 1) + 4; // Auxiliary node handling paths starting from an odd vertex going to an even vertex

        // Add directed edges involving auxiliary nodes for each vertex v in the clique s
        // An edge (u, v) with weight W is modeled by two directed paths:
        // u -> Aux -> v with total weight W, and v -> Aux -> u with total weight W.
        // The specific Aux node used depends on the parities of u and v.
        for (int v : s) {
            if (v % 2 == 0) { // If vertex v has an even index
                // Add edges for paths between two even vertices via P_even_idx
                // Edge weight calculations use integer division, carefully derived to match ceiling function logic.
                adj[v].push_back({P_even_idx, (ll)v / 2});           // Edge v -> P_even_idx
                adj[P_even_idx].push_back({v, (ll)v / 2 + c});       // Edge P_even_idx -> v

                // Add edges for paths between even and odd vertices via Q_even_idx and Q_odd_idx
                adj[v].push_back({Q_even_idx, (ll)v / 2});           // Edge v -> Q_even_idx (start path from even v)
                adj[Q_odd_idx].push_back({v, (ll)v / 2 + c});       // Edge Q_odd_idx -> v (end path at even v)
            } else { // If vertex v has an odd index
                // Add edges for paths between two odd vertices via P_odd_idx
                adj[v].push_back({P_odd_idx, (ll)(v + 1) / 2});     // Edge v -> P_odd_idx
                adj[P_odd_idx].push_back({v, (ll)(v - 1) / 2 + c}); // Edge P_odd_idx -> v
                
                // Add edges for paths between odd and even vertices via Q_even_idx and Q_odd_idx
                adj[v].push_back({Q_odd_idx, (ll)(v + 1) / 2});     // Edge v -> Q_odd_idx (start path from odd v)
                adj[Q_even_idx].push_back({v, (ll)(v + 1) / 2 + c}); // Edge Q_even_idx -> v (end path at odd v)
            }
        }
    }

    // Dijkstra's algorithm initialization
    // Initialize distance array with infinity for all vertices
    vector<ll> dist(total_vertices + 1, INF); 
    // Create a min-priority queue to store states {distance, node}
    priority_queue<State, vector<State>, greater<State>> pq;

    // Start Dijkstra from vertex 1 (source)
    dist[1] = 0; // Distance from source to itself is 0
    pq.push({0, 1}); // Push the starting state into the priority queue

    // Main loop of Dijkstra's algorithm
    while (!pq.empty()) {
        // Extract the state with the minimum distance from the priority queue
        State current = pq.top(); 
        pq.pop();

        ll d = current.dist; // Current minimum distance found to node u
        int u = current.node; // The node index

        // Optimization: If we have already found a shorter path to u, this state is outdated. Skip.
        if (d > dist[u]) {
            continue; 
        }

        // Iterate through all neighbors v of the current node u
        for (const Edge& edge : adj[u]) {
            int v = edge.to; // Neighbor vertex index
            ll weight = edge.weight; // Weight of the edge (u, v)
            
            // Try to relax the edge (u, v):
            // Check if the path through u to v is shorter than the current known shortest path to v.
            // Ensure dist[u] is not INF to prevent potential overflow issues when adding weight.
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                // Update the minimum distance to v
                dist[v] = dist[u] + weight; 
                // Push the updated state {new distance, v} into the priority queue
                pq.push({dist[v], v}); 
            }
        }
    }

    // After Dijkstra's algorithm finishes, check the computed distance to the target vertex N
    if (dist[N] == INF) { // If vertex N is unreachable from vertex 1, its distance remains INF
        cout << -1 << endl; // Output -1 as required
    } else { // Otherwise, vertex N is reachable
        cout << dist[N] << endl; // Output the minimum path length found
    }

    return 0; // Indicate successful execution
}
0