题意：n个点m条边的无向图，点和边都有权值。 反复从0点出发，求获得【大于点总权值一半】的边的【边权和】。
因为只有100个点，所以直接floyd求最短路，然后一次01背包，DP[i]表示消耗i的油能摧毁的最多的电力。
PS。。此题输入有重边，WA过。
#include#include #include using namespace std; #define INF 0x3f3f3f3f int n,m,a,b,c; int mp[105][105]; int dp[10005]; int v[105]; int pow[105]; int main() { int cas; scanf("%d",&cas); while(cas--) { int sum=0; int ans=0; scanf("%d%d",&n,&m); memset(mp,0x3f,sizeof(mp)); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); mp[a][b]=mp[b][a]=min(mp[a][b],c); } for(int k=0;k<=n;k++) for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) mp[i][j]=min(mp[i][k]+mp[k][j],mp[i][j]); for(int i=1;i<=n;i++) { scanf("%d",&pow[i]); ans+=pow[i]; if(mp[0][i]!=INF) sum+=mp[0][i]; } ans=ans/2; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { if(mp[0][i]!=INF) for(int k=sum;k>=mp[0][i];k--) { dp[k]=max(dp[k],dp[k-mp[0][i]]+pow[i]); } } int ok=0; for(int i=1;i<=sum;i++) if(dp[i]>ans) {printf("%d\n",i);ok=1;break;} if(!ok) puts("impossible"); } return 0; }