#1083865 (C++17) No.3018 目隠し宝探し

• 問題: No.3018 目隠し宝探し
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:06:24
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,631 bytes
• コンパイル時間: 844 ms
• コンパイル使用メモリ: 86,600 KB
• 実行使用メモリ: 79,668 KB
• 最終ジャッジ日時: 2025-05-14 13:07:27
• 合計ジャッジ時間: 7,509 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	TLE * 1
other	-- * 21

ソースコード

#include <iostream> // For input/output operations (cin, cout)
#include <vector>   // For using dynamic arrays (std::vector)
#include <iomanip>  // For output formatting (std::fixed, std::setprecision)
#include <numeric>  // For std::fill to efficiently initialize vectors

// Use the standard namespace to avoid writing std:: repeatedly
using namespace std;

int main() {
    // Optimize input/output operations for speed.
    // This is often helpful in competitive programming to avoid Time Limit Exceeded errors.
    ios_base::sync_with_stdio(false); // Disable synchronization with C standard streams
    cin.tie(NULL);                   // Untie cin from cout

    int n; // Number of pages (nodes), indexed from 0 to n-1
    int m; // Number of directional links (edges)

    // Read the number of pages (n) and links (m) from the input
    cin >> n >> m;

    // --- Data Structures Initialization ---

    // 1. Adjacency list to store outgoing links:
    //    `outgoing_links[u]` will be a vector containing pairs `{v, c}`.
    //    This means there is a link from page `u` to page `v` with an integer weight `c`.
    //    The outer vector has size `n`, one entry for each page.
    vector<vector<pair<int, int>>> outgoing_links(n);

    // 2. Vector to store the total outgoing weight for each page:
    //    `total_weight[u]` stores the sum of weights `c` for all links starting *from* page `u`.
    //    Using `double` for this sum prevents potential overflow with many links (though int might be okay here)
    //    and ensures floating-point arithmetic when calculating proportions later.
    //    Initialize all total weights to 0.0.
    vector<double> total_weight(n, 0.0);

    // --- Reading Link Information ---
    // Loop `m` times to read the details of each link
    for (int i = 0; i < m; ++i) {
        int u, v, c; // Variables for source page `u`, destination page `v`, and weight `c`
        cin >> u >> v >> c; // Read the link details: u v c

        // Add the link information (destination page `v` and weight `c`)
        // to the list of outgoing links for the source page `u`.
        outgoing_links[u].push_back({v, c});

        // Add the weight `c` of this link to the total outgoing weight for page `u`.
        // Cast `c` to double to maintain precision in `total_weight`.
        total_weight[u] += static_cast<double>(c);
    }

    // --- Simulation Setup ---

    // Population vectors:
    // `current_pop[i]` holds the population (number of people) on page `i` at the beginning of the current simulation step (turn).
    // Initialize all pages with a starting population of 10.0 as per the problem description.
    vector<double> current_pop(n, 10.0);

    // `next_pop[i]` is a temporary vector used to calculate the population of page `i` for the *next* simulation step.
    // We need this buffer because all population movements within a single turn happen simultaneously based on `current_pop`.
    // Initialize all elements to 0.0; it will accumulate the incoming population for each page during a turn.
    vector<double> next_pop(n, 0.0);

    // Define the number of simulation iterations (turns) required by the problem
    const int ITERATIONS = 100;

    // --- Simulation Loop ---
    // Run the simulation for exactly 100 turns
    for (int iter = 0; iter < ITERATIONS; ++iter) {

        // Before calculating the population distribution for the current turn,
        // reset the `next_pop` vector to all zeros. This is crucial because `next_pop` accumulates
        // the population arriving at each page during this turn.
        // `std::fill` sets all elements in the range [begin(), end()) to 0.0.
        fill(next_pop.begin(), next_pop.end(), 0.0);

        // Iterate through each page `u` (from 0 to n-1). Page `u` is the *source* page
        // from which people will move in this turn.
        for (int u = 0; u < n; ++u) {

            // If the current population on page `u` is effectively zero,
            // there's no one to move, so we can skip the calculations for this page.
            // Using a small threshold (e.g., 1e-12) is good practice for floating-point comparisons.
            // Also, check `total_weight[u]`. If it's zero (which the problem statement guarantees won't happen,
            // as every page has at least one outgoing link), we would have a division-by-zero issue.
            if (current_pop[u] < 1e-12 ) { // No need to check total_weight as per problem constraints
                continue; // Skip to the next source page `u`
            }

            // Get the population currently residing on page `u`.
            double pop_u = current_pop[u];
            // Get the pre-calculated total weight of all links originating from page `u`.
            double total_w = total_weight[u];

            // Now, iterate through all the outgoing links defined for the current source page `u`.
            // `edge` will represent one specific outgoing link, storing `{v, c}`.
            for (const auto& edge : outgoing_links[u]) {
                int v = edge.first;  // `v` is the destination page of this specific link.
                int c = edge.second; // `c` is the integer weight associated with the link u -> v.

                // Calculate the fraction (proportion) of population from page `u`
                // that will move along this specific link (u -> v).
                // This is the link's weight `c` divided by the total outgoing weight `total_w` from page `u`.
                // Cast `c` to double to ensure floating-point division.
                double fraction_moving = static_cast<double>(c) / total_w;

                // Calculate the actual number of people (which can be fractional) moving from `u` to `v`.
                double moved_pop = pop_u * fraction_moving;

                // Add this calculated `moved_pop` amount to the population count for the destination page `v`
                // in the `next_pop` vector. `next_pop[v]` accumulates all population arriving at page `v`
                // from various source pages during this turn.
                next_pop[v] += moved_pop;
            }
        }

        // After iterating through all source pages `u` and calculating all population movements,
        // the `next_pop` vector now holds the complete population distribution for the *start* of the next turn.
        // We update `current_pop` with these new values to prepare for the next iteration of the simulation.
        // The vector assignment operator (`=`) efficiently copies the contents of `next_pop` into `current_pop`.
        current_pop = next_pop;
    }

    // --- Output Results ---

    // Configure the standard output stream (`cout`) for printing floating-point numbers.
    // `fixed` ensures that numbers are printed in fixed-point decimal notation (e.g., 123.45)
    // rather than scientific notation (e.g., 1.2345e+2).
    // `setprecision(8)` sets the number of digits displayed *after* the decimal point to 8.
    // This level of precision is usually sufficient for competitive programming problems
    // involving doubles and easily satisfies the problem's requirement of 0.1 error tolerance.
    cout << fixed << setprecision(8);

    // Iterate through all the pages (from index 0 to n-1).
    for (int i = 0; i < n; ++i) {
        // Print the final calculated population for page `i`, which is stored in `current_pop[i]`.
        cout << current_pop[i] << "\n"; // Print the value followed by a newline character as required.
    }

    // Return 0 to indicate that the program executed successfully.
    return 0;
}