【HDOJ】2722 Here We Go，relians Again

根据矩阵建图，然后求最短路径。

  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         else
111             printf("%d blips\n", dis[vn-1]);
112     }
113 
114     return 0;
115 }