考虑dp
设$d[x]$为到达$x$号点时的期望长度
因为会随机选一个点，所以到达$x$号点的期望长度为所有能到x号点的点的期望长度乘以到达x号点的边长度
这就告诉我们需要拓扑排序
首先边反向(这样不用处理根本到不了终点的点，而且可以避免计算错误)
(当然反向是比正向快多了)(我正向TLE了)
然后直接在拓扑序上面搞就行
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=100005;
int n,m,h[N],en,nxt[N];
double d[N],p[N];
queue<int> Q;
inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
struct Edge{int b,v,next;}e[N<<1];
inline void AddEdge(const int &sa,const int &sb,const int &sc){e[++en].b=sb;nxt[sb]++;e[en].v=sc;e[en].next=h[sa];h[sa]=en;}
inline void bfs(){
for(register int i=1;i<=n;i++)p[i]=1.0/nxt[i];
Q.push(n);
while(!Q.empty()){
int u=Q.front();Q.pop();
for(register int i=h[u];i;i=e[i].next){
int v=e[i].b;
d[v]+=p[v]*(d[u]+e[i].v);
if(!--nxt[v])Q.push(v);
}
}
}
int main(){
freopen("3036.in","r",stdin);
freopen("3036.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=m;i++){
int u,v,w;
Read(u);Read(v);Read(w);
AddEdge(v,u,w);
}
bfs();
printf("%.2lf\n",d[1]);
return 0;
}
评论 (0)
