HDU 3339 In Action(dijkstra+01背包)

#include <bits/stdc++.h>
#define maxn 205
#define maxm 20005
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
  int to,w,next;
  bool operator < (const Node &a) const{
    return a.w < w;
  }
}Edge[maxm],Now,Next;
int head[maxm],num;
int dist[maxn],v[maxn],sum;
int T,n,m;

void init(){
  memset(head,-1,sizeof(head));
  num = 0;
  sum = 0;
}

void add(int u,int v,int w){
  Edge[num].to = v;
  Edge[num].w = w;
  Edge[num].next = head[u];
  head[u] = num ++;
}

void dijkstra(){
  bool vis[maxn];
  memset(vis,false,sizeof(vis));
  memset(dist,inf,sizeof(dist));
  dist[0] = 0;
  Now.to = 0;
  priority_queue<Node> q;
  q.push(Now);
  while(!q.empty()){
    Now = q.top();
    q.pop();
    int ans = Now.to;
    if(vis[ans] == true) continue;
    vis[ans] = true;
    for(int i=head[ans];i!=-1;i=Edge[i].next){
      int u = Edge[i].to;
      if(!vis[u] && dist[u] > dist[ans] + Edge[i].w){
        dist[u] = dist[ans] + Edge[i].w;
        Next.to = u;
        Next.w = dist[u];
        q.push(Next);
      }
    }
  }
}

void ZeroBack(){
  int dp[maxm];
  memset(dp,inf,sizeof(dp));
  dp[0] = 0;
  for(int i=1;i<=n;i++){
    for(int j=sum;j>=v[i];j--){
      dp[j] = min(dp[j], dp[j - v[i]] + dist[i]);
    }
  }
  int ans = inf;
  for(int i=sum/2+1;i<=sum;i++){
    ans = min(ans, dp[i]);
  }
  if(ans == inf){
    printf("impossible\n");
  }
  else{
    printf("%d\n",ans);
  }
}

int main()
{
  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&n,&m);
    init();
    for(int i=0;i<m;i++){
      int u,v,w;
      scanf("%d%d%d",&u,&v,&w);
      add(u, v, w);
      add(v, u, w);
    }
    for(int i=1;i<=n;i++){
      scanf("%d",&v[i]);
      sum += v[i];
    }
    dijkstra();
    ZeroBack();
  }
  return 0;
}