Link

放上鄙人丑陋的代码：

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int s = 0,f = 1;char c = getchar();
	while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
	while (isdigit(c)){s = (s << 3) + (s << 1) + (c ^ 48);c = getchar();}
	return s*f;
}
const int N = 105;
const int M = 1305;
int head[N],cnt;
struct node{
	int v,w,next;
}tree[M<<1];
int n,m,k;
struct place{
	int c;
	long double h1,h2;
}a[N];
void add(int u,int v,int w){
	tree[++cnt].next = head[u];
	tree[cnt].v = v;tree[cnt].w = w;
	head[u] = cnt;
}
struct dp{
	long double h1,h2;
}f[N][505],ans;
dp operator + (const dp &a,const dp &b){
	return (dp){a.h1 + b.h1,a.h2 + b.h2};
}
int check[N][505];
dp dfs(int u,int time){
	if (check[u][time])
	    return f[u][time];
	f[u][time] = {0,0};
	long double sum = 0;
	time -= a[u].c;
	for (int i=head[u];i;i=tree[i].next){
		int v = tree[i].v;
		if (tree[i].w + a[v].c <= time)
		    sum++,f[u][time] = f[u][time] + dfs(v,time - tree[i].w);
	}
	if (sum != 0)f[u][time].h1 = f[u][time].h1 / sum * 1.0;
	if (sum != 0)f[u][time].h2 = f[u][time].h2 / sum * 1.0;
	f[u][time].h1 += a[u].h1;
	f[u][time].h2 += a[u].h2;
	check[u][time] = 1;
	return f[u][time];
}
int main()
{
    n = read(); m = read(); k = read();
    for (int i=1;i<=n;i++){
        scanf("%d%Lf%Lf",&a[i].c,&a[i].h1,&a[i].h2);
	}
	for (int i=1,u,v,w;i<=m;i++){
		u = read(); v = read(); w = read();
		add(u,v,w);
		add(v,u,w);
	}
	memset(check,0,sizeof(check));
	ans = {0,0};
	long double pr = 0;
	for (int i=1;i<=n;i++){
		if (k >= a[i].c)ans = ans + dfs(i,k),pr++;
	}
	printf("%.5Lf %.5Lf\n",ans.h1 / pr * 1.0,ans.h2 / pr * 1.0);
	return 0;
}