محدودیت زمان: ۱ ثانیه محدودیت حافظه: ۲۵۶ مگابایت منبع: آزمون عملی دوره ۲۴ المپیاد…
- User
محدودیت زمان: ۱ ثانیه محدودیت حافظه: ۲۵۶ مگابایت منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر زمستان سردی است و بارش سنگین برف، باعث مسدود شدن راهها شده است. آقای مهندس برای یک پروژهی کاری به شهر 1 رفته و قصد دارد به خانهاش که در شهر شمارهی n n قرار دارد بازگردد. او در هر روز میتواند در شهری که هست بماند و یا یکی از جادههای غیرمسدود متصل به آن شهر را طی کند. آقای مهندس اطلاعات بسیار مفیدی از سازمان هواشناسی کسب کرده و احتمال مسدود بودن هر جاده را میداند. دقت کنید که مسدود بودن یک جاده در یک روز، مستقل از مسدود بودن یا نبودن آن، در روزهای قبلاش است. برای نمونه، اگر احتمال مسدود بودن یک جاده را p p بگیریم، احتمال این که جاده دو روز متوالی مسدود باشد، p 2 p 2 و احتمال اینکه در هیچکدام از دو روز بسته نباشد، ( p − 1 ) 2 (p−1) 2 است. عبور از هر جاده دقیقا یک روز طول میکشد.
حال اگر آقای مهندس قصد داشته باشد در کمترین زمان به خانهاش برسد و برای رسیدن به این هدف کاملا هوشمندانه عمل کند، امیدریاضی تعداد روزهایی که طول میکشد تا او به خانه بازگردد، چقدر است.
ورودی در سطر اول ورودی دو عدد طبیعی n n، تعداد شهرها، و m m، تعداد جادهها، آمده است.
هر کدام از m m سطر بعدی شامل سه عدد طبیعی u u و v v و p p است که به معنای وجود یک جادهی دوطرفه با احتمال مسدود بودن p / 1000 p/1000 بین دو شهر u u و v v است.
تضمین میشود که گراف شهرهای دادهشده همبند است.
بین هر دو شهر حداکثر یک جاده وجود دارد و هیچ شهری به خودش جاده ندارد.
احتمال مسدود بودن تمامی جادهها کمتر از ۱ است.
2 ≤ n ≤ 100
000 2≤n≤100 000 1 ≤ m ≤ 100
000 1≤m≤100 000 1 ≤ u , v ≤ n 1≤u,v≤n u ≠ v u =v 0 ≤ p ≤ 1
000 0≤p≤1 000
خروجی در تنها سطر خروجی امیدریاضی تعداد روزهایی که آقای مهندس در راه است را با دقیقن ۳ رقم اعشار چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۵ گراف شهرها درخت است. ۲ ۵۵ n ≤ 1
500 n≤1 500 و حداکثر چهار جاده به هر شهر وصل است ۳ ۱۵ n ≤ 300 n≤300 ۴ ۲۵ بدون محدودیت اضافی مثال ورودی نمونه ۱ 4 4 1 2 500 1 3 500 2 4 625 3 4 500 Plain text خروجی نمونه ۱ 3.556 Plain text ورودی نمونه ۲ 2 1 1 2 999 Plain text خروجی نمونه ۲ 1000.000 c++
- Assistant
To solve this problem, we need to calculate the expected number of days Mr. Engineer will take to reach his home in city ( n ) from city ( 1 ), considering the probabilities of each road being blocked. The problem involves probabilities and optimizing the path to minimize the expected time, which makes it a challenging task.
Approach Overview
-
Modeling the Problem:
- Each city represents a state in a Markov Decision Process (MDP).
- The goal is to find the expected number of days ( E[i] ) required to reach city ( n ) from any city ( i ).
- From any city ( i ), Mr. Engineer can either stay or attempt to traverse one of the available roads.
-
Key Equations:
- The expected time ( E[i] ) for each city ( i ) (except ( n )), is given by:
[
E[i] = 1 + \sum_{s=1}^{k} \left[ q_s \times \prod_{t=1}^{s-1} (1 - q_t) \times E[j_s] \right]
]
where:
- ( k ) is the number of roads from city ( i ).
- ( q_s ) is the probability that the ( s )-th road is available (sorted in ascending order of ( E[j] )).
- ( j_s ) is the city connected by the ( s )-th road.
- The expected time ( E[i] ) for each city ( i ) (except ( n )), is given by:
[
E[i] = 1 + \sum_{s=1}^{k} \left[ q_s \times \prod_{t=1}^{s-1} (1 - q_t) \times E[j_s] \right]
]
where:
-
Iterative Solution:
- Initialize ( E[n] = 0 ) because no days are needed if Mr. Engineer is already at his home.
- Initialize all other ( E[i] ) to a high value (e.g., infinity).
- Use a queue to iteratively update the expected days for each city based on the roads' availability.
- Continually update ( E[i] ) until no further updates are needed (i.e., the values converge).
-
Implementation Considerations:
- Sorting the roads for each city based on the current expected values.
- Efficiently managing updates using a queue to ensure that only affected cities are recalculated.
- Handling floating-point precision carefully to ensure accurate results.
Final Implementation
Below is the C++ implementation based on the above approach. It efficiently computes the expected number of days using iterative updates and ensures that all dependencies are correctly handled.
#include <bits/stdc++.h> using namespace std; // Structure to represent a road struct Road { int j; // connected city double q; // probability the road is available }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; // Roads from each city vector<vector<Road>> roads(n+1); // Reverse adjacency list: for each city j, list of cities i connected to j vector<vector<int>> reverse_adj(n+1); for(int i=0;i<m;i++){ int u, v, p; cin >> u >> v >> p; double q = 1.0 - (double)p / 1000.0; roads[u].push_back(Road{v, q}); roads[v].push_back(Road{u, q}); reverse_adj[v].push_back(u); reverse_adj[u].push_back(v); } // Initialize E[i]: expected days to reach n from i // Set E[n] = 0, others to a large value vector<double> E(n+1, 1e18); E[n] = 0.0; // Initialize sorted roads for each city, sorted by current E[j] // Initially, all E[j] =1e18 except E[n]=0 // So roads to n will be first vector<vector<Road>> sorted_roads(n+1); for(int u=1; u<=n; u++){ sorted_roads[u] = roads[u]; sort(sorted_roads[u].begin(), sorted_roads[u].end(), [&](const Road &a, const Road &b) -> bool{ return E[a.j] < E[b.j]; }); } // Queue for BFS-like updates queue<int> q; // Initially, enqueue all cities connected to n for(auto &road: roads[n]){ int i = road.j; if(i != n){ q.push(i); } } // To prevent multiple enqueues vector<bool> in_queue_flag(n+1, false); for(auto &road: roads[n]){ int i = road.j; if(i != n){ in_queue_flag[i] = true; } } // Iterative updates while(!q.empty()){ int i = q.front(); q.pop(); in_queue_flag[i] = false; // Sort roads of i in ascending order of E[j] sort(sorted_roads[i].begin(), sorted_roads[i].end(), [&](const Road &a, const Road &b) -> bool{ return E[a.j] < E[b.j]; }); // Compute sum = sum_s [ q_s * product_{t=1}^{s-1} (1 - q_t ) * E[j_s} } ] double sum = 0.0; double P_not = 1.0; for(auto &road: sorted_roads[i]){ sum += road.q * P_not * E[road.j]; P_not *= (1.0 - road.q); // Early termination if P_not becomes negligible if(P_not < 1e-12) break; } double new_E = 1.0 + sum; // If E[i] needs to be updated if(new_E + 1e-9 < E[i]){ E[i] = new_E; // Enqueue all cities connected to i for(auto &road: roads[i]){ int j = road.j; if(j != i && !in_queue_flag[j]){ q.push(j); in_queue_flag[j] = true; } } } } // Output the expected days from city 1 with 3 decimal places // Ensure that E[1] is finite // As per problem statement, it's guaranteed that not all roads are blocked always printf("%.3lf\n", E[1]); }Explanation of the Code
-
Input Parsing:
- The code begins by reading the number of cities ( n ) and the number of roads ( m ).
- It then reads each road's information, including the connected cities ( u ), ( v ), and the probability ( p ) that the road is blocked. From ( p ), it calculates ( q ), the probability that the road is not blocked.
-
Graph Representation:
- The roads are stored in an adjacency list for each city.
- A reverse adjacency list is also maintained to keep track of cities connected to each city. This helps in efficiently updating the expected days.
-
Initialization:
- The expected days ( E[i] ) are initialized to a very high value for all cities except city ( n ), which is set to ( 0 ) since it's the destination.
- Roads for each city are sorted in ascending order of ( E[j] ), which initially places roads leading directly to ( n ) first.
-
Iterative Updates:
- The algorithm uses a queue to iteratively update the expected days ( E[i] ) for each city based on the current state of the graph.
- For each city in the queue, it recalculates ( E[i] ) using the key equation mentioned above.
- If ( E[i] ) is updated to a smaller value, all connected cities are enqueued for potential further updates.
-
Termination and Output:
- The process continues until no more updates are necessary, ensuring that all ( E[i] ) values have converged.
- Finally, the expected number of days from city ( 1 ) is printed with three decimal places as required.
Conclusion
This approach effectively models and solves the problem using an iterative method to compute the expected number of days required to reach the destination. The key lies in correctly updating the expected values while efficiently managing the dependencies between cities.
-