【CERC2017】Gambling Guide

题面

https://www.luogu.org/problem/P4745

题解

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#define ri register int
#define N 300500
using namespace std;

double cost[N],d[N],f[N];
int b[N];
vector<int> to[N];
int n,m,vis[N];

struct node {
  double sum,b;
  int x;
  bool operator < (const node &rhs) const {
    return sum/b+d[x]/b > rhs.sum/rhs.b+d[rhs.x]/rhs.b;
  }
};
priority_queue<node> q;

void dij() {
  while (!q.empty()) q.pop();
  cost[n]=0; vis[n]=1;
  for (ri i=0;i<to[n].size();i++) {
    int v=to[n][i];
    b[v]=1;
    q.push((node){0,1,v});
  }
  while (!q.empty()) {
    node t=q.top(); int u=t.x; q.pop();
    if (vis[u]) continue;
    vis[u]=1;
    cost[u]=t.sum/t.b+d[u]/t.b;
    for (ri i=0;i<to[u].size();i++) if (!vis[to[u][i]]) {
      f[to[u][i]]+=cost[u];
      q.push((node){f[to[u][i]],(double)(++b[to[u][i]]),to[u][i]});
    }
  }
  return;
}

int main(){
  int x,y;
  scanf("%d %d",&n,&m);
  for (ri i=1;i<=m;i++) {
    scanf("%d %d",&x,&y);
    to[x].push_back(y); to[y].push_back(x);
  }
  for (ri i=1;i<=n;i++) d[i]=to[i].size();
  dij();
  printf("%.10lf",cost[1]);
}