C++14(g++5.4) 解法, 执行用时: 29ms, 内存消耗: 988K, 提交时间: 2020-06-23 19:37:05

#include<bits/stdc++.h>
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N=105;
int n,m,K,x,y,t,tot;
int c[N],h[N][2];
int head[N],ver[N*N],nxt[N*N],edge[N*N];
double dp[500][N];
void add(int x,int y,int z){
	edge[++tot]=z;ver[tot]=y;
	nxt[tot]=head[x];head[x]=tot;
}
double solve(int x){
	double ans=0;
	memset(dp,0,sizeof(dp));
	for(int i=K;i;i--){
		for(int j=1;j<=n;j++){
			int s=0;
			for(int k=head[j];k;k=nxt[k])
				if(i+edge[k]<=K)s++;
			for(int k=head[j];k;k=nxt[k])
				if(i+edge[k]<=K)dp[i][j]+=(dp[i+edge[k]][ver[k]]/s);
			dp[i][j]+=h[j][x];
		}
	}
	for(int i=1;i<=n;i++)ans+=dp[c[i]][i]/n;
	return ans;
}
int main(){
	Fox;
	scanf("%d%d%d",&n,&m,&K);
	for(int i=1;i<=n;i++)scanf("%d%d%d",&c[i],&h[i][0],&h[i][1]);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&t);
		add(x,y,t+c[y]);
		add(y,x,t+c[x]);
	}
	printf("%.5lf %.5lf",solve(0),solve(1));
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 55ms, 内存消耗: 1320K, 提交时间: 2020-04-17 16:38:55

#include<cstdio>
#include<iostream>
using namespace std;

const int N=111;
struct node{int c,h[3];}a[N];
int n,m,k,e[N][N];double ans[3],f[3][N][510];

double dfs(int id,int t,int v){
  if(f[v][id][t])return f[v][id][t];
  double sum=0;int cnt=0;
  for(int i=1;i<=n;i++){
    if(e[id][i]&&t>=e[id][i]+a[i].c){
      cnt++;sum+=dfs(i,t-e[id][i]-a[i].c,v);
    }
  }
  if(cnt>0)sum/=cnt;
  sum+=a[id].h[v];f[v][id][t]=sum;
  return sum;
}

int main(){
  scanf("%d%d%d",&n,&m,&k);
  for(int i=1;i<=n;i++){
    scanf("%d%d%d",&a[i].c,&a[i].h[1],&a[i].h[2]);
  }
  for(int i=1,x,y,z;i<=m;i++){
    scanf("%d%d%d",&x,&y,&z);e[x][y]=e[y][x]=z;
  }
  for(int i=1;i<=2;i++){
    for(int j=1;j<=n;j++){
      if(k>=a[j].c){ans[i]+=dfs(j,k-a[j].c,i);}
    }
  }
  ans[1]/=n;ans[2]/=n;
  printf("%.5f %.5f\n",ans[1],ans[2]);
  return 0;
}