yukicoder : No.8018 簡易版ページランク

これ★2～2.5でもいい気がする。
https://yukicoder.me/problems/no/8018

問題

N個のページに対し、他ページへの遷移確率が与えられる。
ページランクの計算を100周回した後の各ページのスコアを答えよ。

解法

ページランクの計算式に従い愚直に計算すればよい。

int N,M;
vector<pair<int,int>> V[1010];
int S[1010];
double F[1000],T[1000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) F[i]=10;
	FOR(i,M) {
		cin>>x>>y>>k;
		V[x].push_back({y,k});
		S[x]+=k;
	}
	FOR(i,100) {
		ZERO(T);
		FOR(j,N) {
			if(S[j]==0) {
				T[j]+=F[j];
			}
			else {
				double v=F[j]/S[j];
				FORR2(a,b,V[j]) T[a]+=b*v;
			}
		}
		swap(F,T);
		
	}
	FOR(i,N) _P("%.12lf\n",F[i]);
	
}

まとめ

特に計算量的な難しさもないので、なんで★3にしたのか疑問。