http://acm.hdu.edu.cn/showproblem.php?pid=3339

    这道题关键是读懂题意，揣摩每句话的意思。
    some connected electric stations表示除0点外，其他电站都是连通的。（1）
    As for a electric station, we control them if and only if our tanks stop there表示我们的坦克必须停在那里才能说是控制了电站。（2）
    大致题意是说：有n个电站，每个电站都有一定的电量，电站之间有一定距离，我们要从0点出发去占领一些电站，使得占领的电站电量之和超过总电量的一半，求达到条件所要走的最短距离。如果可能的话，输出距离，否则输出不可能。什么时候不可能呢？我们知道电站都是连通的，只要0点与任何一个电站连通，我们就可以占领所有电站，如果0点不与任何一个电站相连，就是不可能实现，也就是说0点到任何一个电站的距离都是无穷。
    我们从0点开始派出一些坦克去占领一些电站，坦克到每个电站都有一定距离，而占领每个电站之后可以得到一定电量，距离就相当于体积，电量就相当于价值，这不是就01背包吗？01背包通常的问法是给定体积，求获得最大的价值，这里的问法是给定价值，求恰好得到或多于该价值时的最小体积。我们只要从前向后搜索，找到第一个大于该价值的体积即可。
    求0点到其他点的距离，就是最短路径问题，可以用floyd算法，也可以用dijkstra算法，或者SPFA算法。

#include <iostream>

using namespace std;

const int M=101,MAX=10012;
int map[M][M];
int cost[M]; //从0点到i点的费油量
int value[M];//i点的价值
int dp[MAX];//存储cost为i时的价值
int bivalue,n,m;
bool visit[M];

void dj()
{
    int i,j,temp,min;
    for(i=1;i<=n;i++)
    {
        visit[i]=false;
        cost[i]=map[0][i];
    }
    for(i=1;i<n;i++)
    {
        min=MAX;
        for(j=1;j<=n;j++)
            if(!visit[j] && cost[j]<min)
            {
                temp=j;
                min=cost[j];
            }
        if(min==MAX)
            break;
        visit[temp]=true;
        for(j=1;j<=n;j++)
            if(!visit[j] && cost[j]>cost[temp]+map[temp][j])
                cost[j]=cost[temp]+map[temp][j];
    }
}

int main()
{
    int i,j,t,c,v,d;
    bool flag;
    scanf("%d",&t);
    while(t--)
    {
        v=c=0;
        scanf("%d%d",&n,&m);
        for(i=0;i<=n;i++) //初始化为无穷
            for(j=0;j<=n;j++)
                if(i==j)
                    map[i][j]=0;
                else
                    map[i][j]=MAX;
        while(m--)
        {
            scanf("%d%d%d",&i,&j,&d);//输入注意用scanf，否则会超时
            if(d<map[i][j])        //当心陷阱，可能输入多个i,j之间的距离，我们取最小的
                map[i][j]=map[j][i]=d;
        }
        dj();
        flag=true;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&value[i]);
        }
        for(i=1;i<=n;i++)
        {
            v+=value[i];
            c+=cost[i];
            if(cost[i]==MAX) //只要有一个距离是无穷，其他的也是无穷，就不可能实现
            {
                flag=false;
                break;
            }
        }
        if(flag==false)
        {
            printf("impossible\n");
            continue;
        }
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
            for(j=c;j>=cost[i];j--)
                if(dp[j-cost[i]]+value[i]>dp[j])
                    dp[j]=dp[j-cost[i]]+value[i];
        bivalue=v/2+1;
        for(i=1;i<=c;i++)   //找出恰好>半量的i
            if(dp[i]>=bivalue)
                break;
        
        printf("%d\n",i);
    }
    return 0;
}