hdu3339 In Action(Dijkstra+01背包)

/*
   題意：有 n 個站點（編號1...n），每一個站點都有一個能量值，為了不讓這些能量值連接起來，要用 
   坦克占領這個站點！已知站點的 之間的距離，每個坦克從0點出發到某一個站點，1 unit distance costs 1 unit oil！
   最后占領的所有的站點的能量值之和為總能量值的一半還要多，問最少耗油多少！
    
*/

/*
     思路：不同的坦克會占領不同的站點，耗油最少那就是路程最少，所以我們先將從 0點到其他各點的
     最短距離求出來！也就是d[i]的值！然后我們又知道每一個站點的所具有的能量值！也就是w[i];
     最后求出滿足占領站點的能量比總能量的一半多并且路程最少。。。直接01背包走起！ 
*/ 
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 10005
#define INF 0x3f3f3f3f
using namespace std;

int w[105];

struct EDGE{
   int u, v, nt, dist;
   EDGE(){}
   
   EDGE(int u, int v, int nt, int dist){
      this->u=u;
      this->v=v;
      this->nt=nt;
      this->dist=dist;
   }
};

EDGE edge[N*2];
int first[105];
int cnt;
queue<pair<int, int> >q;
int n, m;
int dp[10005];
int d[105];
int map[105][105];

void addEdge(int u, int v, int dist){
    edge[cnt++]=EDGE(u, v, first[u], dist);
    first[u]=cnt-1;
    edge[cnt++]=EDGE(v, u, first[v], dist);
    first[v]=cnt-1;
}

void Dijkstra(){
   d[0]=0;
   q.push(make_pair(0, 0)); 
   while(!q.empty()){
       pair<int,int> cur=q.front();
       q.pop();
       int u=cur.second;
       if(d[u] != cur.first) continue;
       for(int e=first[u]; e!=-1; e=edge[e].nt){
              int v=edge[e].v, dist=edge[e].dist;
              if(d[v] > d[u] + dist){
                 d[v] = d[u] + dist;
                 q.push(make_pair(d[v], v));
              }
       }
   }
}

int main(){
   int t;
   int sumP, sumD;
   scanf("%d", &t);
   while(t--){
      scanf("%d%d", &n, &m);
      cnt=0;
      memset(d, 0x3f, sizeof(d));
      memset(first, -1, sizeof(first));
      for(int i=0; i<=n; ++i)
         for(int j=0; j<=n; ++j)
            map[i][j]=INF;
      while(m--){
          int u, v, dist;
          scanf("%d%d%d", &u, &v, &dist);
          if(map[u][v]>dist)
              map[u][v]=map[v][u]=dist;
      }
      for(int i=0; i<=n; ++i)
         for(int j=0; j<=i; ++j)
            if(map[i][j]!=INF)
              addEdge(i, j, map[i][j]); 
      Dijkstra();//求出 0點到其他個點的最短的距離！ 
      sumP=sumD=0;
      for(int i=1; i<=n; ++i){
         scanf("%d", &w[i]);
         sumP+=w[i];
         sumD+=d[i];
      }
      memset(dp, 0x3f, sizeof(dp));//初始背包的總價值為無窮大 
      dp[0]=0;
      
      //zeroOnePackage... d[i]相當于價值（也就是耗油量）， w[i]相當于容積（也就是能量值） 
      for(int i=1; i<=n; ++i) 
         for(int j=sumP; j>=w[i]; --j)
            dp[j]=min(dp[j], dp[j-w[i]]+d[i]);
      
      int maxCost=INF;
      for(int i=sumP/2+1; i<=sumP; ++i)//注意是sumP/2+1(因為要比一半多) 
            if(maxCost>dp[i])
               maxCost=dp[i];
      if(maxCost==INF)
         printf("impossible\n");
      else printf("%d\n", maxCost);
   }
   return 0;
}

/*
   思路：dp[i][j]表示到達 i站點， 并且占領的能量值為 j時的耗油最小值！ 
         開始想用的是spfa算法，并且在進行節點之間距離松弛的時候，也將       背包融進來，但是超時啊！
         好桑心..... 
*/

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 10005
#define INF 0x3f3f3f3f
using namespace std;

int w[105];

struct EDGE{
   int u, v, nt, dist;
   EDGE(){}
   
   EDGE(int u, int v, int nt, int dist){
      this->u=u;
      this->v=v;
      this->nt=nt;
      this->dist=dist;
   }
};

EDGE edge[N*2];
int first[105];
int cnt;
queue<pair<int, int> >q;
int vis[105];
int n, m, sum;
int dp[105][10005];
int map[105][105];

void addEdge(int u, int v, int dist){
    edge[cnt++]=EDGE(u, v, first[u], dist);
    first[u]=cnt-1;
    edge[cnt++]=EDGE(v, u, first[v], dist);
    first[v]=cnt-1;
}

void spfa(){
   dp[0][0]=0;
   q.push(make_pair(0, 0)); 
   vis[0]=1;
   while(!q.empty()){
       pair<int,int> cur=q.front();
       q.pop();
       int u=cur.second;
       vis[u]=0;
       for(int e=first[u]; e!=-1; e=edge[e].nt){
           int v=edge[e].v, dist=edge[e].dist;
           for(int j=w[v]; j<=sum; ++j)
              if(dp[v][j] > dp[u][j-w[v]] + dist){
                 dp[v][j] = dp[u][j-w[v]] + dist;
                 if(!vis[v]){
                    vis[v]=1;
                    q.push(make_pair(dp[v][j], v));
                 }
              }
       }
   }
}

int main(){
   int t;
   scanf("%d", &t);
   while(t--){
      scanf("%d%d", &n, &m);
      cnt=0;
      memset(first, -1, sizeof(first));
      for(int i=0; i<=n; ++i)
         for(int j=0; j<=n; ++j)
            map[i][j]=INF;
      while(m--){
          int u, v, dist;
          scanf("%d%d%d", &u, &v, &dist);
          if(map[u][v]>dist)
              map[u][v]=map[v][u]=dist;
      }
      for(int i=0; i<=n; ++i)
         for(int j=0; j<=n; ++j)
            if(map[i][j]!=INF)
              addEdge(i, j, map[i][j]); 
      for(int i=1; i<=n; ++i){//最后將1...n節點的最優值匯聚到 第 n+1個節點上 
           edge[cnt++]=EDGE(i, n+1, first[i], 0);
           first[i]=cnt-1;
      }
      sum=0;
      for(int i=1; i<=n; ++i){
         scanf("%d", &w[i]);
         sum+=w[i];
      }
      w[n+1]=0;
      for(int i=0; i<n+2; ++i)
         for(int j=0; j<sum+2; ++j)
            dp[i][j]=INF; 
      spfa();
      int maxCost=INF;
      for(int i=sum/2+1; i<=sum; ++i)
            if(maxCost>dp[n+1][i])
               maxCost=dp[n+1][i];
      if(maxCost==INF)
         printf("impossible\n");
      else printf("%d\n", maxCost);
   }
   return 0;
} 

?