AOJ 0224 - Bicycle Diet

問題文 : 自転車ダイエット

解法 :
ケーキ屋の数が少ないので, 訪れたケーキ屋の集合および今いる頂点を持ったダイクストラを行う.
"一度訪れたケーキ屋に再び訪れることができない"ということに注意.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>

using namespace std;

#define NODE (128)
#define INF (1 << 30)
#define SHOP (6)

int cost[NODE][NODE];
int v[1 << (SHOP)][NODE];
int V;
int m, n, k, d;
int cake[SHOP];

typedef struct{
	int pos, val, bit;
} State;

bool operator > (const State &a, const State &b)
{
	return (a.val > b.val);
}

int conv(char *s)
{
	if (s[0] == 'H') return (0);
	if (s[0] == 'D') return (m + n + 1);
	if (s[0] == 'C') return (atoi(s + 1));
	return (atoi(s + 1) + m);
}

void dijkstra()
{
	priority_queue<State, vector<State>, greater<State> > que;
	State st;
	
	st.pos = 0, st.val = 0, st.bit = 0;
	que.push(st);
	
	for (int i = 0; i < 1 << (SHOP); i++){
		for (int j = 0; j < V; j++){
			v[i][j] = INF;
		}
	}
	v[0][0] = 0;
	
	while (!que.empty()){
		State temp = que.top(); que.pop();
		for (int i = 0; i < V; i++){
			if (i == temp.pos || cost[temp.pos][i] == INF){
				continue;
			}
			
			State next;
			next.val = temp.val + cost[temp.pos][i];
			next.pos = i;
			next.bit = temp.bit;
			if (1 <= i && i <= m){
				if (!((next.bit >> (i - 1)) & 1)){
					next.bit |= (1 << (i - 1));
					next.val -= cake[i - 1];
				}
				else continue;
			}
			
			if (v[next.bit][i] > next.val){
				v[next.bit][i] = next.val;
				que.push(next);
			}
		}
	}
}

int main(void)
{
	int i, j, l;
	int from, to;
	int cal;
	char div[5];
	
	while (1){
		scanf("%d %d %d %d", &m, &n, &k, &d);
		if (m + n + k + d == 0){
			break;
		}
		
		V = m + n + 2;
		
		for (i = 0; i < m; i++){
			scanf("%d", &cake[i]);
		}
		
		for (i = 0; i < V; i++){
			for (j = 0; j < V; j++){
				cost[i][j] = INF;
			}
		}
		
		for (i = 0; i < d; i++){
			scanf("%s", div);
			from = conv(div);
			scanf("%s", div);
			to = conv(div);
			
			scanf("%d", &cal);
			
			cost[from][to] = cost[to][from] = cal * k;
		}
		
		int ans = INF;
		
		dijkstra();
		
		for (i = 0; i < 1 << (SHOP); i++){
			ans = min(ans, v[i][m + n + 1]);
		}
		
		printf("%d\n", ans);
	}
	return (0);
}