HDU3339--In Action(最短路+0-1背包)

先用最短路求出0到i点的最短距离，然后再用0-1背包做。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define INF 999999999 #define M 105 using namespace std; int main() { int map[M][M],p[M],dp[M*M]; int n,m,t,i,j,k,sum,ave; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=0;i<=n;i++) { for(j=0;j<=n;j++) { map[i][j]=INF; } } while(m--) { int u,v,d; scanf("%d%d%d",&u,&v,&d); map[u][v]=map[v][u]=min(map[u][v],d); } sum=0; for(i=1;i<=n;i++) { scanf("%d",&p[i]); sum+=p[i]; } ave=sum/2; for(k=0;k<=n;k++) { for(i=0;i<=n;i++) { for(j=0;j<=n;j++) { map[i][j]=min(map[i][j],map[i][k]+map[k][j]); } } } int temp=0; for(i=1;i<=n;i++) { if(map[0][i]
       
        =map[0][i];j--) { dp[j]=max(dp[j],dp[j-map[0][i]]+p[i]); } } int flag=0; for(i=0;i<=temp;i++) { if(dp[i]>ave) { printf("%d\n",i); flag=1; break; } } if(flag==0) printf("impossible\n"); } return 0; }