Description
给定一张n个点，m条双向边的无向图。
你要从1号点走到n号点。当你位于x点时，你需要花1元钱，等概率随机地买到与x相邻的一个点的票，只有通过票才能走到其它点。
每当完成一次交易时，你可以选择直接使用那张票，也可以选择扔掉那张票然后再花1元钱随机买另一张票。注意你可以无限次扔票。
请使用最佳的策略，使得期望花的钱数最少。
Input
第一行包含两个正整数n,m(1<=n,m<=300000)，表示点数和边数。
接下来m行，每行两个正整数u,v(1<=u,v<=n)，表示一条双向边。
输入数据保证无重边、无自环，且1号点一定可以走到n号点。
Output
输出一行一个实数，即最少的期望花费，当绝对或者相对误差不超过10^{-6}时视为正确。
Sample Input
5 8
1 2
1 3
1 4
2 3
2 4
3 5
5 4
2 5
1 2
1 3
1 4
2 3
2 4
3 5
5 4
2 5
Sample Output
4.1111111111
Solution
最优策略的话，一个点只会走向到终点期望步数比他小的点，用最短路来更新$DP$就可以了。
反正我也说不太明白，感性理解一下吧。
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define N (300009)
#define pi pair<double,int>
using namespace std; struct Edge{int to,next;}edge[N<<];
int n,m,u,v,deg[N],c[N],vis[N];
int head[N],num_edge;
double s[N],f[N];
priority_queue<pi,vector<pi>,greater<pi> >q; void add(int u,int v)
{
deg[v]++;
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
} int main()
{
scanf("%d%d",&n,&m);
for (int i=; i<=m; ++i)
scanf("%d%d",&u,&v), add(u,v), add(v,u);
q.push(pi(,n));
while (!q.empty())
{
int x=q.top().second; q.pop();
if (vis[x]) continue; vis[x]=;
for (int i=head[x]; i; i=edge[i].next)
{
int y=edge[i].to;
if (vis[y]) continue;
c[y]++; s[y]+=f[x]; f[y]=(s[y]+deg[y])/c[y];
q.push(pi(f[y],y));
}
}
printf("%.10lf\n",f[]);
}