不搞什么萌新之类的了
c++11代码,WA2,似乎是精度的问题
#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct edge
{
int v,to,w;
}e[N<<1];
int n,m,head[N<<1],cnt,ot[N];
bool in[N];
void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].to=head[u];
head[u]=cnt;
}
queue<tuple<int,int,int>>q;//0-pos 1-length 2-out times
double ans;
int main()
{
scanf("%d%d",&n,&m);
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
ot[u]++;
in[v]=1;
}
//for(int i=head[1];i;i=e[i].to){printf("%d\n",i);system("pause");}puts("stop");
for(int i=1;i<=n;i++)if(!in[i])q.push(make_tuple(i,0,1));
while(!q.empty())
{
tuple<int,int,int>res=q.front();
q.pop();
//printf("%d\n",get<0>(res));system("pause");
if(get<0>(res)==n)
{
ans+=get<1>(res)*1.0/get<2>(res);
continue;
}
for(int i=head[get<0>(res)];i;i=e[i].to)
q.push(make_tuple(e[i].v,get<1>(res)+e[i].w,get<2>(res)*ot[get<0>(res)]));
}
printf("%.2lf\n",ans);
return 0;
}
禁止无意义回复