綠豆蛙的歸宿#
綠豆 WA 的歸宿
題目#
題目背景#
隨著新版百度空間的上線，Blog 寵物綠豆蛙完成了它的使命，去尋找它新的歸宿。
題目描述#
給出一個有向無環圖，起點為 1 終點為 N，每條邊都有一個長度，並且從起點出發能夠到達所有的點，所有的點也都能夠到達終點。綠豆蛙從起點出發，走向終點。 到達每一個頂點時，如果有 K 條離開該點的道路，綠豆蛙可以選擇任意一條道路離開該點，並且走向每條路的概率為 1/K 。 現在綠豆蛙想知道，從起點走到終點的所經過的路徑總長度期望是多少？
輸入輸出格式#
輸入格式：#
第一行：兩個整數 N M，代表圖中有 N 個點、M 條邊 第二行到第 1+M 行：每行 3 個整數 a b c，代表從 a 到 b 有一條長度為 c 的有向邊
輸出格式：#
從起點到終點路徑總長度的期望值，四捨五入保留兩位小數。
輸入輸出樣例#
輸入樣例 #1：#
4 4
1 2 1
1 3 2
2 3 3
3 4 4
輸出樣例 #1：#
7.00
說明#
對於 20% 的數據 N<=100
對於 40% 的數據 N<=1000
對於 60% 的數據 N<=10000
對於 100% 的數據 N<=100000，M<=2*N
分析#
用 DFS 枚舉每條路徑。
在每個路口算概率
達到終點用概率 * 路徑長度
（大佬都用拓撲排序，我太弱了只會 DFS）
拓撲排序方法參見：
dyx 大佬的博客
perisino 大佬的博客
代碼#
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005*2;
struct tu{
private:
struct ed{//采用鏈式前向星存圖
int to,nex,w;
} e[MAXN];
int head[MAXN],newp;
public:
tu(void){//初始化
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
}
void insert(int p1,int p2,int w){//插入，前插
++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){//當前點，目前長度，目前概率，結束點
double ret=0;
int cnt=0;
if(p==end){
//出口條件，返回概率*路徑總長
return tot*gl;
}
for(int i=head[p];i!=0;i=e[i].nex){
++cnt;
}//統計可能性
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即為從當前點到終點的期望概率
}
};
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;
}