Problem Description: There are N nodes and M directed roads with weight in an acyclic graph. At each node, there is a probability of 1 / K to go to each next node, where K number of roads that are connected to current node. Starting at 1, calculate the total expectancy distance to go to N.
Input Format:
First line consists of two integers N ≤ 1000000, M ≤ 2N.
The next M lines consist of a,b,c, meaning a road from a to b weight/distance c.
Output Format:
One line with the answer, round the answer up to 0.01 in accuracy.
Sample Input:
1 2 1
1 3 2
2 3 3
3 4 4
Sample Output:
7.00
Solution: Emm, as hzwer said, easy problems are good for health. (JUST DO A DFS, and be careful with memory when doing dfs T_T) .
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1e6 + 10;
vector<pii> G[maxn];
bool vis[maxn]
int N,M;
double f[maxn];
void dfs(int u){
if(vis[u]) return;
vis[u] = 1;
int sz = G[u].size();
for(int i = 0; i < sz; i++){
dfs(G[u][i].first);
f[u] += f[G[u][i].first] + G[u][i].second;
}
if(G[u].size()) f[u] /= (1.0 * sz)
}
int main(){
FAST_IO
cin>>N>>M;
for(int i = 1; i <= M; i++){
int u,v,w;
cin>>u>>v>>w;
G[u].push_back(pii(v,w));
}
dfs(1);
cout<<fixed<<setprecision(1)<<ans<<endl;
return 0;
}