本题开始题意理解有问题，以为是坦克一起开到每个地方炸掉station,使总路程最短，于是要考虑各个station之间的路程，而近于搜索暴力，百思不得其解。后来发现题意理解错了。“We have enough tanks”这句话不是白写的，要仔细读题。是把各个坦克开到各个地方守着，就是control（控制）power总量在占据一半以上的station,使之不能启动，于是就可以背包了。
首先求出各个station到开始位置的单源最短路，这里边数范围是点数范围的平方关系，用Dijkstra和spfa都可以，这是背包里面的价值。各个station总的power是背包容量，每个station的power是物品的容量。在容量一半以上的范围内找价值最小的。
代码如下：
代码
1 #include<iostream>
2 #include<vector>
3 #include<queue>
4 using namespace std;
5 #define MAXM 102
6 //#define clr(a) memset(a,0,sizeof(a))
7 #define INF 9999999
8 struct node
9 {
10 node (int v0, int dis0):v(v0),dis(dis0){}
11 int v;
12 int dis;
13 };
14 vector<node> map[MAXM];
15 bool visit[MAXM];
16 int n;
17 void spfa(int x,int dis[])
18 {
19 int i;
20 //clr(visit);
21 for(i = 0; i < (n+1); i++)
22 {
23 dis[i] = INF;
24 visit[i] = false;
25 }
26 visit[x] = true;
27 dis[x] = 0;
28 queue<int> q;
29 q.push(x);
30 while(!q.empty())
31 {
32 int u = q.front();
33 q.pop();
34 visit[u] = false;
35 for(i = 0; i < map[u].size(); i++)
36 {
37 node p = map[u][i];
38 if(dis[p.v] > (dis[u] + p.dis))
39 {
40 dis[p.v] = dis[u] + p.dis;
41 if(!visit[p.v])
42 {
43 visit[p.v] = true;
44 q.push(p.v);
45 }
46 }
47 }
48 }
49 }
50 int main()
51 {
52 int T,m,i,j,a,b,len,sum,min;
53 int pow[MAXM],oil[MAXM],pack[MAXM*MAXM];
54 scanf("%d",&T);
55 while(T--)
56 {
57 scanf("%d %d",&n,&m);
58 for(i = 0; i <= n; i++)
59 map[i].clear();
60 for(i = 0; i < m;i++)
61 {
62 scanf("%d %d %d",&a,&b,&len);
63 map[a].push_back(node(b,len));
64 map[b].push_back(node(a,len));
65 }
66 sum = 0;
67 for(i = 1;i <= n; i++)
68 {
69 scanf("%d",&pow[i]);
70 sum += pow[i];
71 }
72 for(i = 1; i <= sum; i++)
73 pack[i] = INF;
74 spfa(0,oil);
75 pack[0] = 0;
76 for(i = 1; i <= n; i++)
77 {
78 for(j = sum;(j-pow[i]) >= 0;j--)
79 {
80 if((pack[j - pow[i]] + oil[i]) < pack[j])
81 pack[j] = pack[j - pow[i]] + oil[i];
82 }
83 }
84 min = INF;
85 for(i = sum/2+1; i <= sum; i++)
86 {
87 if(min > pack[i])
88 min = pack[i];
89 }
90 if(min != INF)
91 printf("%d\n",min);
92 else
93 printf("impossible\n");
94 }
95