1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 100007 5 using namespace std; 6 struct edge 7 { 8 int to, next; 9 double w; 10 }e[2 * N]; 11 int n, m, ls[N], tot, cd[N], rd[N]; 12 double dis[N]; 13 14 void add(int x, int y, double z) 15 { 16 e[++tot].to = y; 17 e[tot].w = z; 18 e[tot].next = ls[x]; 19 ls[x] = tot; 20 } 21 22 void dfs(int x, double s, double tot) 23 { 24 if (x == n) 25 { 26 dis[n] += tot * s; 27 return; 28 } 29 s *= (1.0 / (double)cd[x]); 30 for (int i = ls[x]; i; i = e[i].next) 31 { 32 tot += e[i].w; 33 dfs(e[i].to, s, tot); 34 tot -= e[i].w; 35 } 36 } 37 38 int main() 39 { 40 scanf("%d%d", &n, &m); 41 int x, y; 42 double z; 43 for (int i = 1; i <= m; i++) 44 { 45 scanf("%d%d", &x, &y); 46 scanf("%lf", &z); 47 cd[x]++; 48 add(x, y, z); 49 } 50 dfs(1, 1.0, 0); 51 printf("%.2f", dis[n]); 52 }
如对本文有疑问, 点击进行留言回复!!
Harmony Pairs 2020牛客暑期多校训练营(第六场)
Codeforces Round #659 (Div. 2) 题解
清华大学《数据结构与算法》笔记(从02-D3-1到02-D4-5)
洛谷:P2585 [ZJOI2006]三色二叉树(树dp,提高+/省选-)
贪吃蛇C/C++面向过程源码分析(双缓冲区 | 248行代码)
网友评论