提出 #9107162

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;

const int N = 606, inF = N;
typedef long double ld;

int n, m;
ld ans = inF;
ld dp[N];
vector<int> nei[N];

ld act(int y) {
	for (int x = y - 1; x >= 0; x--) {
      dp[x] = 0;
		for (int u: nei[x])
			dp[x] += dp[u];
		dp[x] /= nei[x].size();
		dp[x]++;
	}
	return dp[0];
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	while (m--) {
		int u, v;
		cin >> u >> v;
		nei[--u].push_back(--v);
	}
	for (int i = n - 2; ~i; i--) {
		ld sum = 0, maxi = 0;
		for (int u: nei[i]) {
			maxi = max(maxi, dp[u]);
			sum += dp[u];
		}
		if (nei[i].size() > 1) {
			dp[i] = (sum - maxi) / (nei[i].size() - 1) + 1;
			ans = min(ans, act(i));
		}
		dp[i] = sum / nei[i].size() + 1;
	}
	cout << fixed << setprecision(10) << min(ans, dp[0]);
}

提出情報

ジャッジ結果