[백준] 20870 - Teleportgång (c++)

https://www.acmicpc.net/problem/20870

감상

역시나 파라메트릭이라 어려웠다. 그래도 점점 파라메트릭의 재미를 알아가고 있는 것 같다.

 

문제 요약

무방향 그래프와 시작점,끝점이 주어진다. 1초 동안 이어진 정점으로 이동하거나 랜덤 정점으로 이동할 수 있을 때 끝점까지 이동하는 최소 기대값을 구해라.

 

풀이 (NlogN)

• Parametric Search
• BFS

BFS로 끝점 기준의 거리(모든 정점에서 끝점까지 거리) 를 저장해 두고 랜덤 노드에서 시작점에 도달하는 최소 기대값을 기준으로 파라메트릭을 돌릴 수 있습니다. 랜덤 노드에서 시작점에 도달하는 최소 기대값을 x라고 할 때, 특정 노드에서 끝 점으로 이동하는 기대값은 min(거리,x+1(특정노드>랜덤노드가 1, 랜덤노드>끝노드가 x))이 되기 때문에 이분 탐색문 안에서 모든 정점을 순회하며 끝점으로 이동하는 기대값의 sum을 구하고 sum<x*n이면 작은 쪽으로 아니면 큰 쪽으로 범위를 좁힐 수 있습니다. x를 기대값(평균)으로 정의 했기 때문에 sum<x*n이라면 평균값이 더 작다는 의미가 되기 때문입니다. 소수를 이분 탐색하는 건 탐색 횟수를 충분한 값으로 고정해두고 돌리는 방법을 사용하였습니다.

 

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

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n,m,s,t;cin>>n>>m>>s>>t;
	vector<int> adj[n+1];
	for(int i=0,u,v;i<m;i++)
		cin>>u>>v,adj[u].push_back(v),adj[v].push_back(u);
	
	int d[n+1];fill(d,d+n+1,1e9);
	queue<int> q;
	d[t]=0; q.push(t);
	while(q.size()) {
		int u=q.front();q.pop();
		for(int v:adj[u]) if(d[v]==1e9)
			d[v]=d[u]+1,q.push(v);
	}

	double l=0,r=1e9;
	for(int i=0;i<100;i++) {
		double mid=(l+r)/2;
		double x=0;
		for(int i=1;i<=n;i++) {
			if(d[i]>mid+1) x+=mid+1;
			else x+=d[i];
		}
		if(x<mid*n)
			r=mid;
		else
			l=mid;
	}
	if(d[s]<l+1)cout<<d[s];
	else cout<<fixed<<setprecision(2)<<l+1;
}