<题目链接>
题目大意：
给出一个0～n组成的图，1～n的点上分布着值为pow的电站，给出图的m条边以及距离，从0出发到n个点中的x个点的行走距离和最小(因为是每炸一个点派出一辆坦克)，且x个点的pow之和必须超过总的pow和的一半。
解题分析：
由于本题数据范围很小，只有100，所以我们能够用floyed算出0到任意一点的最短距离，然后将所有0可达的点看成物品，0到它们的最短距离看成体积，这样将所有可达物品最短距离之和看成背包容量，这些可达点的pow看成价值，然后再用01背包。dp[i]表示在总共走i距离的情况下，所能获得的最大价值。所以，在用01背包计算dp[1~sumvol]的所有值后，我们就可以遍历总共走过的距离i，当dp[i]恰好大于总价值一半的时候，此时的i就是总共的最短距离。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; #define ll long long
const int INF=0x3f3f3f3f;
int n,m;
int mpa[][];
int val[],vol[];
const int maxn=+;
int dp[maxn]; void floyed(){ //floyed计算0到各点的最短路
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
for(int k=;k<=n;k++){
if(mpa[j][k]>mpa[j][i]+mpa[i][k]){
mpa[j][k]=mpa[j][i]+mpa[i][k];
}
}
}
}
} int main(){
int t;scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m); for(int i=;i<=n;i++){ //mpa[][]数组初始化
for(int j=;j<=n;j++){
if(i==j)mpa[i][j]=;
else mpa[i][j]=INF;
}
} for(int i=;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c<mpa[a][b]){ //去重边
mpa[a][b]=mpa[b][a]=c;
}
}
int sumval=; //所有点的总价值
for(int i=;i<=n;i++){
scanf("%d",&val[i]);
sumval+=val[i];
} floyed();
int sumvol=; //0到所有可达点的最短距离之和，作为01背包的容量
for(int i=;i<=n;i++){
if(mpa[][i]!=INF)sumvol+=mpa[][i];
vol[i]=mpa[][i]; //把这段距离看成物品的体积
} memset(dp,,sizeof(dp));
for(int i=;i<=n;i++){
for(int j=sumvol;j>=vol[i];j--){
dp[j]=max(dp[j],dp[j-vol[i]]+val[i]); //dp[j]表示在总距离为j的情况下所能得到的最大价值
}
}
int ans=-INF;
for(int i=;i<=sumvol;i++){
if(dp[i]>(sumval/)){ //当dp[i]的值大于sum/2时，此时的i就是符合条件的最短距离
ans=i;
break;
}
}
if(ans==-INF)printf("impossible\n");
else printf("%d\n",ans);
}
return ;
}
2018-09-04