题意：给定一张图，每个点都有一个power值，到每个点都要一定的距离 消耗一定的油量，求从0出发到某些点 使得 油量消耗最少且power值达到一半。

可以floyd或者spfa求出0到各点的距离 dis[ maxm ]。

然后就可以转化为：从dis[]中挑出某些点，使得距离和最小且power值达到某个值。

从01背包中可以发现：从给定的一些物品中挑出一些放入一个背包中，使得不超过背包体积。

这是我们可以把dis当做每个物品的体积，power当做价值。

然后从dp中搜到一个power值满足条件的最小的 i 即可

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn = 105; 6 const int maxm = 1000005; 7 const int inf = 99999999; 8 int mat[ maxn ][ maxn ],power[ maxn ],dis[ maxn ]; 9 int dp[ maxm ];10 int sum,aim;11 //power 相当于价值，dis 相当于体积12 void init( int n ){13     for( int i=0;i<=n;i++ )14         for( int j=0;j<=n;j++ )15             mat[ i ][ j ]=inf;16 }17 void floyd( int n ){18     for( int k=0;k<=n;k++ ){19         for( int i=0;i<=n;i++ ){20             for( int j=0;j<=n;j++ ){21                 if( mat[i][k]!=inf&&mat[k][j]!=inf&&mat[i][j]>mat[i][k]+mat[k][j] ){22                     mat[i][j]=mat[i][k]+mat[k][j];23                 }24             }25         }26     }27     for( int i=1;i<=n;i++ ){28         dis[i]=mat[0][i];29         if( dis[i]!=inf )30             sum+=dis[i];31     }32 }33 int main(){34     int T;35     scanf("%d",&T);36     while( T-- ){37         int n,m;38         scanf("%d%d",&n,&m);39         init( n );40         int a,b,c;41         while( m-- ){42             scanf("%d%d%d",&a,&b,&c);43             mat[ a ][ b ]=mat[ b ][ a ]=min(mat[a][b],c);44         }45         sum=aim=0;46         for( int i=1;i<=n;i++ ){47             scanf("%d",&power[ i ]);48             aim+=power[ i ];49         }50         floyd( n );51         //dp52         //sum/=2;53         memset( dp,0,sizeof( dp ));54         for( int i=1;i<=n;i++ ){55             for( int j=sum;j>=dis[i];j-- ){56                 dp[ j ]= max( dp[ j ],dp[ j-dis[i] ]+power[ i ] );57             }58         }59         int ans=inf;60         for( int i=0;i<=sum;i++ )61             if( dp[i]>=(aim/2+1)&&dp[i]