Description：

??游乐园被描述成一张n个点，m条边的无向图（无重边，无自环）。每个点代表一个娱乐项目，第i个娱乐项目需要耗费ci分钟的时间，会让小y和妹子的开心度分别增加h1i,h2i，他们俩初始的开心度都是0。每条边代表一条路，第i条边连接编号为xi的两个娱乐项目，从xi走到yi或者从yi走到xi耗费的时间都是ti分钟。小y和妹子预计在游乐园里玩k分钟。最开始的时候，小y和妹子会等概率的随机选择一个娱乐项目开始玩，每玩完一个项目后，小y和妹子会等概率的随机选择一个可以从当前项目直达的且来得及玩的项目作为下一个项目。如果玩完一个项目后周围没有可以直达的且来得及玩的项目，小y和妹子就会提前结束游玩。请你分别计算小y和妹子在游玩结束后开心度的期望。

输入格式：

??输入第一行给出三个空格隔开的整数，分别表示n,m,k;
??接下来的n行，每行三个空格隔开的整数，分别表示ci,h1i,h2i;
??接下来的m行，每行三个空格隔开的整数，分别表示xi,yi,ti;

输出格式

??输出两个用空格隔开的实数，分表表示小y和妹子开心度的期望，精确到小数点后5位。

样例输入:

5 4 60
25 12 83
30 38 90
16 13 70
22 15 63
50 72 18
2 1 7
3 1 7
4 3 1
5 3 10

样例输出:

39.20000 114.40000

数据范围与提示:

0<n<=100,60<=k<=480,10<=ci<=60,0<h1,h2<=100,0<ti<=15。

基本思路：

??这个题比较适合DP，可以考虑记忆化搜索或普通DP。作者这里讲DP打法。
??这道题的两个基本是时间，我们可以将状态数组定义为c[i][j]，第一维表示现在在哪个点，第二维表示已经花费了多少时间。那么状态转移方程就是：

c[to[i][x]][j+t[i][x]+c[to[i][x]]]=c[i][j]/cnt,if(j+t[i][x]+c[to[i][x]]<=k)。

这里有两个注意点：

??1.要保证有充足的时间赶到并有时间玩完通向的那个点，所以要有条件j+t[i][x]+c[to[i][x]]<=k。
??2.要认真读题，每次是从可以来得及赶到的点中随机选一个点，所以，要除以的是满足要求的点的个数(cnt)，而非当前点所通向的总的点的个数(size)。

上代码：

#include<bits/stdc++.h>
#define ll long long
#define rr register
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pp;
const int SIZE=103;
int m,n,k;
int c[SIZE];
double rate[SIZE][483];//到第i个点时花费了j的时间的概率
double h1[SIZE],h2[SIZE];
vector<int> to[SIZE],t[SIZE];
int read();
int main()
{
   n=read();
   m=read();
   k=read();
   for(rr int i=1;i<=n;i++)
   {
      c[i]=read();
      scanf("%lf%lf",&h1[i],&h2[i]);      
   }
   for(rr int i=1;i<=m;i++)
   {
      int x=read();
      int y=read();
      int tt=read();
      to[x].push_back(y);
      to[y].push_back(x);
      t[x].push_back(tt);
      t[y].push_back(tt);    
   }
   double ans1=0,ans2=0;
   for(rr int i=1;i<=n;i++)
     rate[i][c[i]]=1.000/(double)n;
   for(rr int x=0;x<=k;x++)//大的时间是由小的时间推来的
   {
     for(rr int i=1;i<=n;i++)
       ans1+=rate[i][x]*h1[i],ans2+=rate[i][x]*h2[i];
     double cnt=0;
     for(rr int i=1;i<=n;i++)
     {
       cnt=0;
       for(rr int j=0;j<to[i].size();j++)
         if(x+t[i][j]+c[to[i][j]]<=k)
           cnt++;
       for(rr int j=0;j<to[i].size();j++)
         if(x+t[i][j]+c[to[i][j]]<=k)
           rate[to[i][j]][x+t[i][j]+c[to[i][j]]]+=rate[i][x]/cnt;           
     }		
   }
   printf("%.5lf %.5lf\n",ans1,ans2);
}
int read()
{
   rr int x_read=0,y_read=1;
   rr char c_read=getchar();
   while(c_read<‘0‘||c_read>‘9‘)
   {
      if(c_read==‘-‘)
        y_read=-1;
      c_read=getchar();   
   }
   while(c_read<=‘9‘&&c_read>=‘0‘)
   {
      x_read=(x_read<<3)+(x_read<<1)+(c_read^48);
      c_read=getchar();
   }
   return x_read*y_read;
}

??作者犯了两个误区，这里一并讲出来：
??1.一开始的时候循环的顺序我打算放在枚举点的循环里，但这样做有一个很大的弊端，举个例子，比如说1连着2，3，4，我在1的循环里将1的所有的时间状态的值都转移到了，3，4，当我进行到2的循环时，假如满足时间限制，那么2的状态还会更新1，1的新数值是有可能继续被用来更新2，3，4的，但1的循环已过，很明显是不会在被用来更新2，3，4的，因而造成了错误。
??2.题目中讲的是“等概率的随机选择一个可以从当前项目直达的且来得及玩的项目作为下一个项目”,所以应该是用cnt，而非size，在上文已经提过了。
??????????????????????????????????????????????????????????????????????2021.5.26 现役

题解 景区路线规划

原文：https://www.cnblogs.com/Geek-Kay/p/14812855.html