一个在邻国的铁路系统是由nn个城市（编号从11到nn），和mm条连接两个不同城市的双向铁路组成的。铁路票只能在安装在每个城市的自动售票机购买。不幸的是，黑客们已经篡改了这些售票机，现在它们有下面的规则： 当aa市的售票机有一个硬币投入时，机器会发一张从aa市到随机一个邻市的单程票。更精确地来说，目的地城市是被统一的、随机的从所有由出发城市为起点的铁路的终点中选取的。
一个研究计算机科学的学生需要从城市11（她生活在那里）到城市nn（那里正举行一个编程比赛）。她知道机器是怎么工作的（但当然她不能预测随机的目的地）并且有一份铁路系统的地图。在每一个城市，当她买了一张票时，她可以选择立即使用它后到达目的地，或者是丢掉它并买一张新票。她可以无限制的购买的票。当她一到达n城市，旅行就会结束。
在做了一些计算之后，她制定了一个拥有以下的目标的旅行计划：
- 旅行最终到达终点的概率为1
- 预期花在旅行上的硬币越少越好
找到这个预期的她要花在旅途上的硬币数
额。怎么让期望概率为1：
这个我最先想的是：以n为起点跑一次最短路，每次转移更近的节点。
但这并不完全正确
因为：这个最短路距离并不是实际的花费
所以应当转移：期望距离
这个时候需要用Dijkstra转移
设为期望步数他按照刚刚的理论可以跟新所有大于他的状态
答案为
用堆贪心转移就好了
#includeusing namespace std;const int N=1e6+10;inline void read(int &x){ x=0; char ch=getchar(); int f=1; while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } x*=f;}struct Front_star{ int u,v,nxt;}e[N<<1];int cnt=0;int first[N];void add(int u,int v){ ++cnt; e[cnt].u=u; e[cnt].v=v; e[cnt].nxt=first[u]; first[u]=cnt;}struct Node{ double len; int u;};priority_queue Q;bool operator < (Node A,Node B){ return A.len>B.len;}double F[N];double s[N];int d[N];int vis[N];int c[N];int n,m;int main(){// freopen("test.in","r",stdin); read(n); read(m); for(int i=1;i<=m;++i){ int u,v; read(u); read(v); add(u,v); add(v,u); d[u]++; d[v]++; } Q.push((Node){0,n}); while(!Q.empty()){ Node Now=Q.top(); Q.pop(); int u=Now.u; if(vis[u])continue; vis[u]=1; for(int i=first[u];i;i=e[i].nxt){ int v=e[i].v; if(vis[v])continue; c[v]++; s[v]+=F[u]; F[v]=(s[v]+d[v])/((double)c[v]); Q.push((Node){F[v],v}); } } printf("%.8lf",F[1]);}