1048-Provident Housewife

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1048&lang=jp
問題概要
略

考え方
もっと安い値段で買うために、他の店より高い値段で売っている商品は考えないことにする。
また、全ての店に行くことが出来ることから、物が集められないのは、目的のものがどの店でも売っていないときとなる。
後は全ての店の選び方に対して、あらかじめワーシャルフロイド法を使っておき、
循環セールスマン問題として解く。
実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <ctime>
#include <cassert>
#include <cwchar>
#include <cstdarg>
#include <cwctype>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <functional>
using namespace std;
typedef long long int lli;
typedef unsigned int uint;

struct edge{
    int from,to;
    int cost;
    edge(int f,int t,int c){from=f;to=t;cost=c;}
};
struct node:public vector<edge>{
    vector<string> name;
    vector<int> value;
    int buy;
};
typedef vector<node> graph;
const int MAX_V=12;
int d[MAX_V][MAX_V];
int dp[1<<MAX_V][MAX_V];
const int INF=99999999;
int rec(int n,int bit,int s){
    if(dp[bit][s]>=0) return dp[bit][s];
    int res=INF;
    if(bit==(1<<n)-1&&s==0)return dp[bit][s]=0;
    for(int i=0;i<n;i++){
        if(!((bit>> i) &1)){
            res=min(res,rec(n,bit | 1<<i,i)+d[s][i]);
        }
    }
    return dp[bit][s]=res;
}
void warshall_floyd(int n){
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}
void graph2matrix(graph &g){
    int V=g.size();
    for(int i=0;i<V;i++)for(int j=0;j<V;j++)
        if(i==j)d[i][j]=0;else d[i][j]=INF;
    for(int i=0;i<V;i++){
        for(uint j=0;j<g[i].size();j++){
            d[i][g[i][j].to]=g[i][j].cost;
        }
    }
}
int main(){
    for(;;){
        int n;cin >> n;
        if(!n)break;
        map<string,int> min_value;
        graph G(n+1);
        for(int i=1;i<=n;i++){
            int q;cin >> q;string name;int value;
            for(;q--;){
                cin >> name >> value;
                G[i].name.push_back(name);
                G[i].value.push_back(value);
                if(min_value.find(name)!=min_value.end()){
                    min_value[name]=min(min_value[name],value);
                }else{
                    min_value[name]=value;
                }
            }
        }
        int q;vector<string> need;
        int min_v=0;
        cin >> q;
        for(int i=0;i<q;i++){
            string name;
            cin >> name;
            need.push_back(name);
            if(min_value.find(name)!=min_value.end()){
            }else{
                min_v=-1;
            }
        }

        for(int i=1;i<=n;i++){
            G[i].buy=0;
            for(uint j=0;j<G[i].name.size();j++){
                for(int k=0;k<q;k++){
                    if(need[k]==G[i].name[j]){
                        if(G[i].value[j]==min_value[need[k]]){
                            G[i].buy|=1<<k;
                        }
                    }
                }
            }
        }
        int m;
        cin >> m;
        for(int i=0;i<m;i++){
            int a,b,c;
            cin >> a >> b >> c;
            G[a].push_back(edge(a,b,c));
            G[b].push_back(edge(b,a,c));
        }
        //Before Runtime Error
        if(min_v==-1){
            cout << "impossible" << endl;
            continue;
        }


        int minres=INF;
        graph2matrix(G);
        warshall_floyd(n+1);
        //どの店を使うか全通り調べる
        for(int i=0;i<(1<<n);i++){
            int buy=0;
            for(int j=0;j<n;j++){
                if((i>>j)&1){
                    buy|=G[j+1].buy;
                }
            }
            if(buy==(1<<q)-1){
                memset(dp,-1,sizeof(dp));
                minres=min(minres,rec(n+1,((1<<(n+1))-1)^(1+(i<<1)),0));
            }
        }
        min_v=0;
        for(int i=0;i<q;i++){
            min_v+=min_value[need[i]];
        }
        cout << min_v << " "<< minres << endl;
    }

    return 0;
}