The Destination of the Green Frog#
The Destination of the Green Frog with WA
Problem#
Problem Background#
With the launch of the new version of Baidu Space, the blog pet Green Frog has completed its mission and is now looking for a new home.
Problem Description#
Given a directed acyclic graph with a starting point of 1 and an ending point of N, each edge has a length, and it is possible to reach all points from the starting point, and all points can also reach the ending point. The green frog starts from the starting point and moves towards the ending point. When reaching each vertex, if there are K paths leaving that point, the green frog can choose any one of the paths to leave that point, and the probability of choosing each path is 1/K. Now the green frog wants to know the expected total length of the paths it takes from the starting point to the ending point.
Input and Output Format#
Input Format:#
The first line: two integers N M, representing N points and M edges in the graph The second line to the 1+M line: three integers a b c per line, representing a directed edge from a to b with a length of c
Output Format:#
The expected value of the total length of the paths from the starting point to the ending point, rounded to two decimal places.
Input and Output Examples#
Input Example #1:#
4 4
1 2 1
1 3 2
2 3 3
3 4 4
Output Example #1:#
7.00
Explanation#
For 20% of the data, N<=100
For 40% of the data, N<=1000
For 60% of the data, N<=10000
For 100% of the data, N<=100000, M<=2*N
Analysis#
Use DFS to enumerate each path.
Calculate the probability at each intersection.
Multiply the probability by the path length when reaching the ending point.
(The masters use topological sorting, I'm too weak and only know DFS)
For the topological sorting method, refer to:
dyx's blog
perisino's blog
Code#
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005*2;
struct tu{
private:
struct ed{//Use linked list to store the graph
int to,nex,w;
} e[MAXN];
int head[MAXN],newp;
public:
tu(void){//Initialize
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
}
void insert(int p1,int p2,int w){//Insert, insert at the front
++newp;
e[newp].to=p2;
e[newp].nex=head[p1];
e[newp].w=w;
head[p1]=newp;
}
double solve(int s,int e){
return dfs(s,0,1,e);
}
double dfs(int p,int tot,double gl,int end){//Current point, current length, current probability, ending point
double ret=0;
int cnt=0;
if(p==end){
//Exit condition, return probability * total length of the path
return tot*gl;
}
for(int i=head[p];i!=0;i=e[i].nex){
++cnt;
}//Count the possibilities
for(int i=head[p];i;i=e[i].nex){
ret+=dfs(e[i].to,tot+e[i].w,gl/cnt/* gl*(1/cnt) */,end);
}
return ret;//ret is the expected probability from the current point to the ending point
}
};
tu a;
int main(void){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int p1,p2,w;
scanf("%d%d%d",&p1,&p2,&w);
a.insert(p1,p2,w);
}
printf("%.2lf",a.solve(1,n));
return 0;
}