思路：

我们先求一遍floyd，将各点的最短距离求出，然后将点按si的升序排序。dp[i][k]表示第i个点在第j时间所获得的最大效益，那么

dp[i][k]=max(dp[ i ][ k ]  ,  dp[ j ][ k-p[ i ].c-dis[ i ][ j ] ]+p[ i ].s);     dis[i][j]为i与j的最短路径。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define inf 1<<28using namespace std;struct Point{    int c,s,num;    int operator <(const Point &temp) const    {        return s
          
           p[j].s) for(k=t;k>=p[i].c+dis[p[i].num][p[j].num]&&k>=0;k--) { if(dp[j][k-p[i].c-dis[p[i].num][p[j].num]]!=-1) dp[i][k]=max(dp[i][k],dp[j][k-p[i].c-dis[p[i].num][p[j].num]]+p[i].s); } } } for(i=1;i<=n;i++) { if(p[i].num==E) break; } int ans=0; for(j=0;j<=n;j++) { for(k=0;k<=t;k++) { if(k+dis[p[j].num][E]>t) break; ans=max(ans,dp[j][k]); } } printf("Case #%d:\n%d\n",++Case,ans); } return 0;}