1 #include <cstdio>  2 #include <cstring>  3 #include <cstdlib>  4   5 #define L 2520  6 #define MAXN 600  7 #define INF 0x2f2f2f2f  8   9 int map[MAXN][MAXN]; 10 int dis[MAXN]; 11 int path[MAXN]; 12 int vn; 13 bool visit[MAXN]; 14  15 void dijkstra() { 16     int i, j, v, min; 17  18     memset(visit, false, sizeof(visit)); 19     memset(path, 0, sizeof(path)); 20     visit[0] = true; 21     dis[0] = 0; 22     for (i=1; i<vn; ++i) 23         dis[i] = map[0][i]; 24     for (j=1; j<vn; ++j) { 25         min = INF; 26         for (i=0; i<vn; ++i) { 27             if (!visit[i] && dis[i]<min) { 28                 min = dis[i]; 29                 v = i; 30             } 31         } 32         if (min == INF) 33             break; 34         visit[v] = true; 35         for (i=0; i<vn; ++i) { 36             if (!visit[i] && dis[i]>min+map[v][i]) { 37                 dis[i] = min + map[v][i]; 38                 path[i] = v; 39             } 40         } 41     } 42 } 43  44 void output() { 45     int i, j; 46  47     for (i=0; i<vn; ++i) { 48         for (j=0; j<vn; ++j) { 49             printf("%d ", map[i][j]); 50         } 51         printf("\n"); 52     } 53 } 54  55 int main() { 56     int n, m; 57     char dir[3]; 58     int i, j, k, v, r; 59  60 #ifndef ONLINE_JUDGE 61     freopen("data.in", "r", stdin); 62 #endif 63  64     while (scanf("%d %d",&n,&m)!=EOF && (n||m)) { 65         vn = (m+1) * (n+1); 66         memset(map, 0x2f, sizeof(map)); 67         r = 0; 68         for (j=1; j<=m; ++j) { 69             scanf("%d %s", &v, dir); 70             if (v == 0) { 71                 map[j-1][j] = map[j][j-1] = INF; 72             } else { 73                 if (dir[0] == ‘<‘ || dir[0] == ‘*‘) 74                     map[j][j-1] = L/v; 75                 if (dir[0] == ‘>‘ || dir[0] == ‘*‘) 76                     map[j-1][j] = L/v; 77             } 78         } 79         k = m+1; 80         for (i=1; i<=n; ++i) { 81             // column 82             for (j=0; j<=m; ++j) { 83                 scanf("%d %s", &v, dir); 84                 if (v == 0) { 85                     map[r+j][r+k+j] = map[r+k+j][r+j] = INF; 86                 } else { 87                     if (dir[0] == ‘^‘ || dir[0] == ‘*‘) 88                         map[r+k+j][r+j] = L/v; 89                     if (dir[0] == ‘v‘ || dir[0] == ‘*‘) 90                         map[r+j][r+k+j] = L/v; 91                 } 92             } 93             r += k; 94             // row 95             for (j=1; j<=m; ++j) { 96                 scanf("%d %s", &v, dir); 97                 if (v == 0) { 98                     map[r+j-1][r+j] = map[r+j][r+j-1] = INF; 99                 } else {100                     if (dir[0] == ‘<‘ || dir[0] == ‘*‘)101                         map[r+j][r+j-1] = L/v;102                     if (dir[0] == ‘>‘ || dir[0] == ‘*‘)103                         map[r+j-1][r+j] = L/v;104                 }105             }106         }107         dijkstra();108         if (dis[vn-1] == INF)109             printf("Holiday\n");110         else111             printf("%d blips\n", dis[vn-1]);112     }113 114     return 0;115 }