1 /*  2    题意：有 n 个站点（编号1...n），每一个站点都有一个能量值，为了不让这些能量值连接起来，要用   3    坦克占领这个站点！已知站点的 之间的距离，每个坦克从0点出发到某一个站点，1 unit distance costs 1 unit oil！  4    最后占领的所有的站点的能量值之和为总能量值的一半还要多，问最少耗油多少！  5       6 */  7   8 /*  9      思路：不同的坦克会占领不同的站点，耗油最少那就是路程最少，所以我们先将从 0点到其他各点的 10      最短距离求出来！也就是d[i]的值！然后我们又知道每一个站点的所具有的能量值！也就是w[i]; 11      最后求出满足占领站点的能量比总能量的一半多并且路程最少。。。直接01背包走起！  12 */  13 #include<iostream> 14 #include<queue> 15 #include<cstring> 16 #include<cstdio> 17 #include<algorithm> 18 #include<vector> 19 #define N 10005 20 #define INF 0x3f3f3f3f 21 using namespace std; 22  23 int w[105]; 24  25 struct EDGE{ 26    int u, v, nt, dist; 27    EDGE(){} 28     29    EDGE(int u, int v, int nt, int dist){ 30       this->u=u; 31       this->v=v; 32       this->nt=nt; 33       this->dist=dist; 34    } 35 }; 36  37 EDGE edge[N*2]; 38 int first[105]; 39 int cnt; 40 queue<pair<int, int> >q; 41 int n, m; 42 int dp[10005]; 43 int d[105]; 44 int map[105][105]; 45  46 void addEdge(int u, int v, int dist){ 47     edge[cnt++]=EDGE(u, v, first[u], dist); 48     first[u]=cnt-1; 49     edge[cnt++]=EDGE(v, u, first[v], dist); 50     first[v]=cnt-1; 51 } 52  53 void Dijkstra(){ 54    d[0]=0; 55    q.push(make_pair(0, 0));  56    while(!q.empty()){ 57        pair<int,int> cur=q.front(); 58        q.pop(); 59        int u=cur.second; 60        if(d[u] != cur.first) continue; 61        for(int e=first[u]; e!=-1; e=edge[e].nt){ 62               int v=edge[e].v, dist=edge[e].dist; 63               if(d[v] > d[u] + dist){ 64                  d[v] = d[u] + dist; 65                  q.push(make_pair(d[v], v)); 66               } 67        } 68    } 69 } 70  71 int main(){ 72    int t; 73    int sumP, sumD; 74    scanf("%d", &t); 75    while(t--){ 76       scanf("%d%d", &n, &m); 77       cnt=0; 78       memset(d, 0x3f, sizeof(d)); 79       memset(first, -1, sizeof(first)); 80       for(int i=0; i<=n; ++i) 81          for(int j=0; j<=n; ++j) 82             map[i][j]=INF; 83       while(m--){ 84           int u, v, dist; 85           scanf("%d%d%d", &u, &v, &dist); 86           if(map[u][v]>dist) 87               map[u][v]=map[v][u]=dist; 88       } 89       for(int i=0; i<=n; ++i) 90          for(int j=0; j<=i; ++j) 91             if(map[i][j]!=INF) 92               addEdge(i, j, map[i][j]);  93       Dijkstra();//求出 0点到其他个点的最短的距离！  94       sumP=sumD=0; 95       for(int i=1; i<=n; ++i){ 96          scanf("%d", &w[i]); 97          sumP+=w[i]; 98          sumD+=d[i]; 99       }100       memset(dp, 0x3f, sizeof(dp));//初始背包的总价值为无穷大 101       dp[0]=0;102       103       //zeroOnePackage... d[i]相当于价值（也就是耗油量）， w[i]相当于容积（也就是能量值） 104       for(int i=1; i<=n; ++i) 105          for(int j=sumP; j>=w[i]; --j)106             dp[j]=min(dp[j], dp[j-w[i]]+d[i]);107       108       int maxCost=INF;109       for(int i=sumP/2+1; i<=sumP; ++i)//注意是sumP/2+1(因为要比一半多) 110             if(maxCost>dp[i])111                maxCost=dp[i];112       if(maxCost==INF)113          printf("impossible\n");114       else printf("%d\n", maxCost);115    }116    return 0;117 }118 
119 /*120    思路：dp[i][j]表示到达 i站点， 并且占领的能量值为 j时的耗油最小值！ 121          开始想用的是spfa算法，并且在进行节点之间距离松弛的时候，也将       背包融进来，但是超时啊！122          好桑心..... 123 */124 125 #include<iostream>126 #include<queue>127 #include<cstring>128 #include<cstdio>129 #include<algorithm>130 #include<vector>131 #define N 10005132 #define INF 0x3f3f3f3f133 using namespace std;134 135 int w[105];136 137 struct EDGE{138    int u, v, nt, dist;139    EDGE(){}140    141    EDGE(int u, int v, int nt, int dist){142       this->u=u;143       this->v=v;144       this->nt=nt;145       this->dist=dist;146    }147 };148 149 EDGE edge[N*2];150 int first[105];151 int cnt;152 queue<pair<int, int> >q;153 int vis[105];154 int n, m, sum;155 int dp[105][10005];156 int map[105][105];157 158 void addEdge(int u, int v, int dist){159     edge[cnt++]=EDGE(u, v, first[u], dist);160     first[u]=cnt-1;161     edge[cnt++]=EDGE(v, u, first[v], dist);162     first[v]=cnt-1;163 }164 165 void spfa(){166    dp[0][0]=0;167    q.push(make_pair(0, 0)); 168    vis[0]=1;169    while(!q.empty()){170        pair<int,int> cur=q.front();171        q.pop();172        int u=cur.second;173        vis[u]=0;174        for(int e=first[u]; e!=-1; e=edge[e].nt){175            int v=edge[e].v, dist=edge[e].dist;176            for(int j=w[v]; j<=sum; ++j)177               if(dp[v][j] > dp[u][j-w[v]] + dist){178                  dp[v][j] = dp[u][j-w[v]] + dist;179                  if(!vis[v]){180                     vis[v]=1;181                     q.push(make_pair(dp[v][j], v));182                  }183               }184        }185    }186 }187 188 int main(){189    int t;190    scanf("%d", &t);191    while(t--){192       scanf("%d%d", &n, &m);193       cnt=0;194       memset(first, -1, sizeof(first));195       for(int i=0; i<=n; ++i)196          for(int j=0; j<=n; ++j)197             map[i][j]=INF;198       while(m--){199           int u, v, dist;200           scanf("%d%d%d", &u, &v, &dist);201           if(map[u][v]>dist)202               map[u][v]=map[v][u]=dist;203       }204       for(int i=0; i<=n; ++i)205          for(int j=0; j<=n; ++j)206             if(map[i][j]!=INF)207               addEdge(i, j, map[i][j]); 208       for(int i=1; i<=n; ++i){//最后将1...n节点的最优值汇聚到 第 n+1个节点上 209            edge[cnt++]=EDGE(i, n+1, first[i], 0);210            first[i]=cnt-1;211       }212       sum=0;213       for(int i=1; i<=n; ++i){214          scanf("%d", &w[i]);215          sum+=w[i];216       }217       w[n+1]=0;218       for(int i=0; i<n+2; ++i)219          for(int j=0; j<sum+2; ++j)220             dp[i][j]=INF; 221       spfa();222       int maxCost=INF;223       for(int i=sum/2+1; i<=sum; ++i)224             if(maxCost>dp[n+1][i])225                maxCost=dp[n+1][i];226       if(maxCost==INF)227          printf("impossible\n");228       else printf("%d\n", maxCost);229    }230    return 0;231 }