感觉 书上写的 如果状态转移复杂了 不好对付
有等可能的挺在原地 或者是 掉到之前某个点 计算就必须 单独分开 而不能 直接 每次for ++ 了
按照 直接理解重写了分 同事 2019 南昌网络赛 D 题 也是 差不多的思路
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
int head[maxn], cnt;
int to[maxn], nxt[maxn];
int from[maxn], pre[maxn], come[maxn], val[maxn], tot;
int out[maxn], deg[maxn];
double dis[maxn];
void cometo(int a, int b, int c) {
come[++ tot] = b, val[tot] = c;
pre[tot] = from[a], from[a] = tot;
}
void ade(int a, int b) {
to[++ cnt] = b;
nxt[cnt] = head[a], head[a] = cnt;
}
double redis(int u) {
if(u == n) return 0;
double res = 0;
for(int i = from[u]; i; i = pre[i]) {
res += (dis[come[i]] + 1.0 * val[i]) / deg[u];
}
return res;
}
void topsort() {
queue<int> que;
que.push(n);
while(!que.empty()) {
int x = que.front(); que.pop();
dis[x] = redis(x);
for(int i = head[x]; i; i = nxt[i]) {
out[to[i]] --;
if(out[to[i]] == 0) que.push(to[i]);
}
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1, a, b, c; i <= m; ++ i) {
scanf("%d %d %d", &a, &b, &c);
cometo(a, b, c), ade(b, a);
deg[a] ++, out[a] ++;
}
topsort();
printf("%.2lf\n", dis[1]);
return 0;
}
这函数名……我还以为是什么别的语言。