个人感觉这个题挺好，用到了 最短路+DP，题意很容易就看出来了，其实就是0-1背包问题，状态转移方程：dp[j] = min(dp[j], dp[j-v[i]] + w[i]), 背包容量V = sum(v[0]+v[1] +...+v[n]}，]其中每点的power为v[i], 0点到i点的最短路为w[i]；然后再在i = [sum/2+1, sum]范围内找min(dp[i])。

　　ps：偶悲剧的把i的范围写成i = [sum/2, sum]了，贡献无数WA。。。郁闷！！！

My Code：

#include 
     
       #include 
      
        #include 
       
         using namespace std; const int N = 105; const int inf = 0x6ffffff; int dis[N][N]; int dp[N*N]; int vis[N]; int low[N]; int v[N]; int Dijkstra(int n) {
    int flag, i, j, min; for(i = 0; i <= n; i++)     {
            low[i] = dis[0][i];         vis[i] = 0;     }     vis[0] = 1; for(i = 0; i < n; i++)     {
            min = inf; flag = -1; for(j = 0; j <= n; j++)         {
    if(min > low[j] && !vis[j])             {
                    min = low[j];                 flag = j;             }         } if(flag == -1) break;         vis[flag] = 1; for(j = 0; j <= n; j++)         {
    if(!vis[j] && dis[flag][j] < inf)             {
    if(low[j] > dis[flag][j] + low[flag])                     low[j] = dis[flag][j] + low[flag];             }         }     } if(flag != -1) return 1; return 0; } int main() {
    //freopen("data.in", "r", stdin); int T;     scanf("%d", &T); while(T--)     {
    int n, m, i, j, a, b, c, sum = 0;         scanf("%d%d", &n, &m); for(i = 0; i <= n; i++) for(j = 0; j <= n; j++) if(i == j)                     dis[i][j] = 0; else                     dis[i][j] = inf; while(m--)         {
                scanf("%d%d%d", &a, &b, &c); if(c < dis[a][b])                 dis[a][b] = dis[b][a] = c;         }         v[0] = 0; for(i = 1; i <= n; i++)         {
                scanf("%d", &v[i]);             sum += v[i];         } if(!Dijkstra(n))         {
                printf("impossible\n"); continue;         } for(i = 1; i <= sum; i++)             dp[i] = inf;         dp[0] = 0; for(i = 0; i <= n; i++) for(j = sum; j >= v[i]; j--) if(dp[j] > dp[j-v[i]]+low[i])                     dp[j] = dp[j-v[i]]+low[i]; int min = inf; for(i = sum/2+1; i <= sum; i++) if(min > dp[i])                 min = dp[i];         printf("%d\n", min);     } return 0; }