| 1 | double min_mean_cycle(vector<vector<pair<int,double>>> adj){ |
| 2 | int n = size(adj); double mn = INFINITY; |
| 3 | vector<vector<double> > arr(n+1, vector<double>(n, mn)); |
| 4 | arr[0][0] = 0; |
| 5 | rep(k,1,n+1) rep(j,0,n) iter(it,adj[j]) |
| 6 | arr[k][it->first] = min(arr[k][it->first], |
| 7 | it->second + arr[k-1][j]); |
| 8 | rep(k,0,n) { |
| 9 | double mx = -INFINITY; |
| 10 | rep(i,0,n) mx = max(mx, (arr[n][i]-arr[k][i])/(n-k)); |
| 11 | mn = min(mn, mx); } |
| 12 | return mn; } |
| 13 | // vim: cc=60 ts=2 sts=2 sw=2: |