【競技プログラミング】WAで反例がわからなくて困っています。

AOJ0224 Bicycle Dietをダイクストラ法を用いて解いたのですが、
AOJのジャッジではWAが返ってきてしまいます。
いくつか変更を加えてみたり、他の方の解答を見てみたりしたのですが、
なぜACしないのかがどうしても分からず、質問をしている次第です。

私の書いたコードは下記のとおりです。
反例がわかりましたら、コメント頂ければ幸いです。
拙いコードではありますが、宜しくお願い致します。

lang
1#include <iostream>
2#include <stdio.h>
3#include <sstream>
4#include <string>
5#include <vector>
6#include <map>
7#include <queue>
8#include <algorithm>
9#include <set>
10#include <math.h>
11#include <utility>
12#include <stack>
13#include <string.h>
14#include <complex>
15using namespace std;
16
17const int INF = 1<<29;
18const double EPS = 1e-8;
19typedef vector<int> vec;
20typedef pair<int,int> P;
21
22struct edge{int to,cost;};
23
24struct State{
25    int d,m,n;
26    bool operator<( const State& right ) const {
27        return d > right.d;
28    }
29};
30
31int d[1<<6][108];
32int cake[6];
33int m,n,k,di;
34
35int str2index(string& str){
36    if(str[0]=='H'){
37        return 0;
38    }else if(str[0]=='D'){
39        return 1;
40    }else if(str[0]=='C'){
41        return (int)(str[1]-'1'+2);
42    }else{
43        return (int)(str[1]-'1'+2+m);
44    }
45}
46
47int main(){
48    while(1){
49        scanf("%d%d%d%d",&m,&n,&k,&di);
50        if(!n)break;
51
52        vector<vector<edge> > g(n+m+2);
53        for(int i=0;i<m;i++){
54            scanf("%d",&cake[i]);
55        }
56        for(int i=0;i<di;i++){
57            string a,b;
58            int c;
59            cin >> a >> b >> c;
60            int a_i = str2index(a), b_i = str2index(b);
61            g[a_i].push_back((edge){b_i,c});
62            g[b_i].push_back((edge){a_i,c});
63        }
64
65        for(int i=0;i<(1<<m);i++){
66            for(int j=0;j<n+m+2;j++){
67                d[i][j] = INF;
68            }
69        }
70
71
72        d[(1<<m)-1][0] = 0;
73        priority_queue<State> que;
74        que.push((State){0,(1<<m)-1,0});
75
76        while(que.size()){
77            State p = que.top(); que.pop();
78            //printf("p.d=%d p.m=%d p.n=%d\n",p.d,p.m,p.n);
79            if(d[p.m][p.n] < p.d) continue;
80            for(int i=0;i<g[p.n].size();i++){
81                int next_d = p.d+g[p.n][i].cost*k;
82                if(2<=g[p.n][i].to&&g[p.n][i].to<m+2){
83                    int m_i = g[p.n][i].to - 2;
84                    if((p.m>>m_i)&1){
85                        next_d -= cake[m_i];
86                        int next_m = p.m^(1<<m_i);
87                        if(next_d < d[next_m][g[p.n][i].to]){
88                            d[next_m][g[p.n][i].to] = next_d;
89                            que.push((State){next_d,next_m,g[p.n][i].to});
90                        }
91                    }
92                }else{
93                    if(next_d < d[p.m][g[p.n][i].to]){
94                        d[p.m][g[p.n][i].to] = next_d;
95                        que.push((State){next_d,p.m,g[p.n][i].to});
96                    }
97                }
98            }
99        }
100
101        int ans = INF;
102        for(int i=(1<<m)-1;i>=0;i--) ans = min(ans, d[i][1]);
103        cout << ans << endl;
104    }
105
106    return 0;
107}
108