/* 题意：有 n 个站点（编号1...n），每一个站点都有一个能量值，为了不让这些能量值连接起来，要用 坦克占领这个站点！已知站点的 之间的距离，每个坦克从0点出发到某一个站点，1 unit distance costs 1 unit oil！ 最后占领的所有的站点的能量值之和为总能量值的一半还要多，问最少耗油多少！ *//* 思路：不同的坦克会占领不同的站点，耗油最少那就是路程最少，所以我们先将从 0点到其他各点的 最短距离求出来！也就是d[i]的值！然后我们又知道每一个站点的所具有的能量值！也就是w[i]; 最后求出满足占领站点的能量比总能量的一半多并且路程最少。。。直接01背包走起！ */ #include #include #include #include #include #include #define N 10005#define INF 0x3f3f3f3fusing 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 >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 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 #include #include #include #include #include #define N 10005#define INF 0x3f3f3f3fusing 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 >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 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 dp[n+1][i]) maxCost=dp[n+1][i]; if(maxCost==INF) printf("impossible\n"); else printf("%d\n", maxCost); } return 0;}