[BOJ] 15264 : Gambling Guide

#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;
}