코드 복사/붙여넣기 하는 당신이 아름답습니다.

15264 : Gambling Guide

풀이

1에서 N으로 가는 기댓값을 구해야 하는데 기댓값을 구할 수가 없다!

그러니까 N에서부터 1로, 거꾸로 가면서 구해주자.

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int n_ = 3e5+3;

int n, m, sdeg[n_];
double dp[n_], sdp[n_];
struct abc {
    int idx;
    double val;
    bool operator <(abc a)const {
        return val > a.val;
    }
};
priority_queue<abc> pq;
vector<int> gph[n_];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0, u, v; i < m; i++) {
        scanf("%d %d", &u, &v);
        gph[u].push_back(v);
        gph[v].push_back(u);
    }
    fill(dp, dp+n+1, 1e9);
    dp[n] = 0;
    pq.push({ n,0 });
    while (!pq.empty()) {
        auto now = pq.top();
        pq.pop();
        if (now.val != dp[now.idx]) continue;
        for (int nxt : gph[now.idx]) {
            sdeg[nxt]++;
            sdp[nxt] += dp[now.idx];
            double tmp = (sdp[nxt]+gph[nxt].size())/sdeg[nxt];
            if (dp[nxt] > tmp + 1e-10) {
                dp[nxt] = tmp;
                pq.push({ nxt,tmp });
            }
        }
    }

    return !printf("%.6lf", dp[1]);

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-14 18:04

Read more posts by this author