2018-ACetic_ACid/AugTrain-07/G

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <bits/stdc++.h>
#ifdef LOCAL
#define debug 1
#else
#define debug 0
#endif

const int maxn = 300010;
typedef long long ll;
using namespace std;
vector<int> G[maxn];
bool vis[maxn];
double d[maxn];
int cnt[maxn];
const double INF = 1e20, eps = 1e-8;

const int BN=1<<24;
inline char getc()
{
    static char buffer[BN];
    static size_t bi=BN, bn;
    if(bi==BN) bn=fread(buffer,sizeof(char),BN,stdin), bi=0;
    if(bi==bn) return EOF;
    return buffer[bi++];
}

void geti(int& n)
{
    char ch;
    while(~(ch=getc()) && (ch<'0' || ch>'9'));
    if(ch==EOF) exit(0);
    n=ch-'0';
    while(~(ch=getc()) && ch>='0' && ch<='9') n=(n<<1)+(n<<3)+ch-'0';
}

bool update(int v,int u)
{
    double d0;
    if(cnt[v]==0) d0=d[u]+G[v].size();
    else d0=d[v]*cnt[v]+d[u];
    d0/=cnt[v]+1;
    if(d0 < d[v]) {
        d[v]=d0;
        ++cnt[v];
        return true;
    }
    return false;
}

typedef pair<double,int> pii;

struct cmp {
    bool operator()(const pii& a,const pii& b) {
        if(fabs(a.first-b.first) > eps) return a.first > b.first;
        return G[a.second].size() > G[b.second].size();
    }
};

void dijkstra(int s)
{
    for (int i = 1; i < maxn; i++)
    {
        d[i] = INF;
    }

    d[s]=0;
    priority_queue<pii,vector<pii>,cmp > pq;
    pq.emplace(0,s);
    while (!pq.empty())
    {
        pii p=pq.top(); pq.pop();
        if(d[p.second] < p.first) continue;
        int u = p.second;
        vis[u] = true;
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            if(vis[v]) continue;
            if(update(v,u)) pq.emplace(d[v],v);
        }
    }
    return;
}
int main()
{
    int n, m;
    geti(n); geti(m);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        geti(x); geti(y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end(),
        [](int x,int y) { return G[x].size() < G[y].size(); } );
    dijkstra(n);
    //for(int i=1;i<=n;i++) printf("d[%d]=%f\n",i,d[i]);
    printf("%.15lf\n", d[1]);   
}
}}}

#include <bits/stdc++.h>
#ifdef LOCAL
#define debug 1
#else
#define debug 0
#endif
const int maxn = 300010;
typedef long long ll;
using namespace std;
vector<int> G[maxn];
bool vis[maxn];
double d[maxn];
int cnt[maxn];
const double INF = 1e20, eps = 1e-8;
const int BN=1<<24;
inline char getc()
{
    static char buffer[BN];
    static size_t bi=BN, bn;
    if(bi==BN) bn=fread(buffer,sizeof(char),BN,stdin), bi=0;
    if(bi==bn) return EOF;
    return buffer[bi++];
}
void geti(int& n)
{
    char ch;
    while(~(ch=getc()) && (ch<'0' || ch>'9'));
    if(ch==EOF) exit(0);
    n=ch-'0';
    while(~(ch=getc()) && ch>='0' && ch<='9') n=(n<<1)+(n<<3)+ch-'0';
}
bool update(int v,int u)
{
    double d0;
    if(cnt[v]==0) d0=d[u]+G[v].size();
    else d0=d[v]*cnt[v]+d[u];
    d0/=cnt[v]+1;
    if(d0 < d[v]) {
        d[v]=d0;
        ++cnt[v];
        return true;
    }
    return false;
}
typedef pair<double,int> pii;
struct cmp {
    bool operator()(const pii& a,const pii& b) {
        if(fabs(a.first-b.first) > eps) return a.first > b.first;
        return G[a.second].size() > G[b.second].size();
    }
};
void dijkstra(int s)
{
    for (int i = 1; i < maxn; i++)
    {
        d[i] = INF;
    }
    d[s]=0;
    priority_queue<pii,vector<pii>,cmp > pq;
    pq.emplace(0,s);
    while (!pq.empty())
    {
        pii p=pq.top(); pq.pop();
        if(d[p.second] < p.first) continue;
        int u = p.second;
        vis[u] = true;
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            if(vis[v]) continue;
            if(update(v,u)) pq.emplace(d[v],v);
        }
    }
    return;
}
int main()
{
    int n, m;
    geti(n); geti(m);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        geti(x); geti(y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end(),
        [](int x,int y) { return G[x].size() < G[y].size(); } );
    dijkstra(n);
    //for(int i=1;i<=n;i++) printf("d[%d]=%f\n",i,d[i]);
    printf("%.15lf\n", d[1]);   
}