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; }