fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl '\n'
  5. typedef long long LL;
  6. typedef pair<int, int> PII;
  7. typedef pair<LL, LL> PLL;
  8. #define rep(i, l, r) for(int i = l; i <= (r); i ++ )
  9. #define per(i, r, l) for(int i = r; i >= (l); i -- )
  10. #define reps(i, l, r, d) for(int i = l; i <= (r); i += d)
  11. #define pers(i, r, l, d) for(int i = r; i >= (l); i -= d)
  12.  
  13. constexpr int N = 610;
  14. constexpr int P = 1e9 + 7;
  15.  
  16. int n, m;
  17. vector<int> adj[N];
  18. double e_1_i[N], e_i_n[N], p_1_i[N];
  19.  
  20. void solve()
  21. {
  22.     cin >> n >> m;
  23.     while(m -- ) {
  24.         int u, v; cin >> u >> v;
  25.         adj[u].push_back(v);
  26.     }
  27.     per(u, n, 1) {
  28.         for(int v : adj[u]) {
  29.             e_i_n[u] += (1 + e_i_n[v]) / adj[u].size();
  30.         }
  31.     }
  32.     p_1_i[1] = 1;
  33.     rep(u, 1, n) {
  34.         for(int v : adj[u]) {
  35.             p_1_i[v] += p_1_i[u] / adj[u].size();
  36.             e_1_i[v] += (p_1_i[u] + e_1_i[u]) / adj[u].size();
  37.         }
  38.     }
  39.     rep(u, 1, n) {
  40.         cout << u << ' ' << e_1_i[u] << ' ' << e_i_n[u] << endl;
  41.     }
  42.     double ans = e_i_n[1];
  43.     // cerr << ans;
  44.     rep(u, 1, n) {
  45.         if(adj[u].size() == 1) continue;
  46.         double sum = 0;
  47.         for(int v : adj[u]) {
  48.             sum += e_1_i[u] / adj[u].size() + p_1_i[u] / adj[u].size() + p_1_i[u] * e_i_n[v] / adj[u].size();
  49.         }
  50.         // if(u == 1) cerr << sum << endl;
  51.         for(int v : adj[u]) {
  52.             double tmp = sum;
  53.             tmp -= e_1_i[u] / adj[u].size() + p_1_i[u] / adj[u].size() + p_1_i[u] * e_i_n[v] / adj[u].size();
  54.             tmp *= adj[u].size() / (adj[u].size() - 1.0);
  55.             // if(v == 2) cerr << tmp << endl;
  56.             ans = min(ans, e_i_n[1] - sum + tmp);
  57.         }
  58.     }
  59.     cout << fixed << setprecision(20) << ans << endl;
  60. }
  61.  
  62. int main()
  63. {
  64.     ios::sync_with_stdio(0); cin.tie(0);
  65.  
  66.     solve();
  67.  
  68.  
  69.     return 0;
  70. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
4 6
1 4
2 3
1 3
1 2
3 4
2 4
stdout
copy 
1 0 1.83333
2 0.333333 1.5
3 0.666667 1
4 1.83333 0
1.50000000000000022204
https://ideone.com/gCkuj3
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!