緑豆蛙の帰宿#
緑豆 WA の帰宿
問題#
問題背景#
新しいバージョンの Baidu スペースのリリースに伴い、ブログのペットである緑豆蛙は使命を果たし、新しい帰宿を探すために旅立ちました。
問題の説明#
有向非巡回グラフが与えられます。始点は 1 で終点は N であり、各辺には長さがあり、始点からすべての点に到達でき、すべての点から終点に到達できます。緑豆蛙は始点から出発し、終点に向かいます。各頂点に到達すると、その点から出発する K 本の道がある場合、緑豆蛙はその点から任意の道を選び、各道に進む確率は 1/K です。今、緑豆蛙は始点から終点までの経路の総距離の期待値を知りたいです。
入出力形式#
入力形式：#
1 行目：2 つの整数 N M が与えられます。これはグラフに N 個の点と M 本の辺があることを示します。2 行目から 1+M 行目：各行に 3 つの整数 a b c が与えられます。これは a から b への長さ c の有向辺があることを示します。
出力形式：#
始点から終点までの経路の総距離の期待値を、小数点以下 2 桁で四捨五入して出力してください。
入出力例#
入力例 #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;
}