Bicycle Diet(AOJ No.0224)

ケーキ屋さんの数 m ランドマークの数 n 単位距離あたりの消費カロリー k
距離のデータの総数 d,
各ケーキ屋さんで摂取するカロリー c1, c,2, ..., cm
地点間の距離データ系列
が与えられる。
ある地点へ移動するには移動距離分のカロリーを消費する。
ケーキ屋さんに立ち寄ると必ず、ケーキを食べてカロリーを摂取する。
一度立ち寄ったケーキ屋さんに再び立ち寄ってはいけない。
スタート地点から目的地まで移動するのに消費するカロリーの最低値を求める(ケーキ屋でケーキを食べるのでマイナスになることもある)
一度目的地にたどり着いた後、いったん離れてまた戻ってきても良い。
制約
0 < m < 7
0 < n < 101
0 < k < 5
4 < d < 257
0 < 地点間距離 < 21
0 < ci < 101

アルゴリズム

拡張Dijkstra.
負のエッジコストがあるのでBellman-Fordを使うのかと思ったが、
ケーキ屋の再訪問ができないという制約があるため、
negative cycleができないようになっている。なのでDijkstraでおk。
ケーキ屋に訪問したかどうかを状態として持っていなければならないので、
各ノードへの最短路も状態毎に持っておく必要がある。

コード

ケーキ屋訪問状態はビットフィールド(int)で表す。
隣接リストを作るときに、ケーキ屋に行く場合は、消費カロリーから摂取するカロリー量を引いておく。

import java.util.*;
public class aoj0224 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE/2;
	static int m, n, k, d, N;
	public static class Edge implements Comparable<Edge>{
		int s, d, w, used;
		Edge(int s, int d, int w, int used){ this.s = s; this.d = d; this.w = w; this.used = used; }
		@Override public int compareTo(Edge o) { return w < o.w ? -1 : w == o.w ? 0 : 1; }
	}
	static int index(String s) {
		char prefix = s.charAt(0);
		switch(prefix) {
		case 'C': return Integer.parseInt(s.substring(1));
		case 'L': return Integer.parseInt(s.substring(1)) + m;
		case 'D': return N-1;
		case 'H': default: return 0;
		}
	}
	//static boolean isHome(int index) { return index == 0; }
	static boolean isCakeShop(int index) { return 0 < index && index <= m; }
	//static boolean isLandmark(int index) { return m < index && index <= m+n; }
	//static boolean isDestination(int index) { return index == N-1; }
	public static void main(String[] args) {
		while(true) {
			m = stdin.nextInt(); n = stdin.nextInt(); k = stdin.nextInt(); d = stdin.nextInt();
			if ((m|n|k|d) == 0) break;
			N = m+n+2;
			int ck[] = new int[m];
			for (int i = 0; i < m; ++i) ck[i] = stdin.nextInt();
			@SuppressWarnings("unchecked") List<Edge> adjList[] = new List[N];
			for (int i = 0; i < N; ++i) adjList[i] = new ArrayList<Edge>();
			for (int i = 0; i < d; ++i) {
				int src = index(stdin.next()), dst = index(stdin.next()), w = stdin.nextInt() * k;
				adjList[src].add(new Edge(src, dst, w - (isCakeShop(dst) ? ck[dst-1] : 0), 0));
				adjList[dst].add(new Edge(dst, src, w - (isCakeShop(src) ? ck[src-1] : 0), 0));
			}
			System.out.println(extDijkstra(adjList));
		}
	}
	public static int extDijkstra(List<Edge>[] list){
		int[][] dist = new int[N][1<<m]; 
		for (int i = 0; i < N; ++i) Arrays.fill(dist[i], INF);
		PriorityQueue<Edge> q = new PriorityQueue<Edge>(N*N);
		q.add(new Edge(-1, 0, 0, 0));
		dist[0][0] = 0;
		while(!q.isEmpty()){
			Edge p = q.poll();
			if(dist[p.d][p.used] < p.w) continue;
			for(final Edge u: list[p.d]){
				Edge next = new Edge(u.s, u.d, dist[p.d][p.used] + u.w, p.used);	
				if (isCakeShop(u.d)) {
					int bit = (1<<(u.d-1));
					next.used |= bit;
					if ((p.used & bit) != 0) next.w = INF; //cannot re-visit the cake shop.
				}
				if(dist[next.d][next.used] > next.w){
					dist[next.d][next.used] = next.w;
					q.add(next);
				}
			}
		}
		int ret = INF;
		for (int i = 0; i < (1<<m); ++i) ret = Math.min(ret, dist[N-1][i]);
		return ret;
	}
}