hdu1428

每走一步需要保证（走完之后所到区域）距离实验室的最短距离 < （当前区域）距离实验室的最短距离
问，从宿舍到实验室有多少条路可以走
单源最短路 + 记忆化搜索
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <climits>
 4 #include <queue>
 5 
 6 #define MAXN 50
 7 
 8 struct QueueNode
 9 {
10     int x, y;
11 };
12 
13 int n, G[MAXN+5][MAXN+5], dist[MAXN+5][MAXN+5];
14 long long dp[MAXN+5][MAXN+5];
15 int dir[4][4] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
16 bool vis[MAXN+5][MAXN+5];
17 // for every moment , there are not two same elements in the queue is OK 
18 void spfa()
19 {
20     std::queue<QueueNode> q;
21 
22     QueueNode head;
23     dist[n][n] = G[n][n];
24     head.x = head.y = n;
25     q.push(head);
26 
27     while(q.empty()==false){
28 
29         QueueNode u = q.front();
30         // if u is out the queue
31         // vis[u] is false
32         vis[u.x][u.y] = false;
33         q.pop();
34 
35         QueueNode v;
36 
37         for(int i = 0; i < 4; ++i){
38             v.x = u.x + dir[i][0];
39             v.y = u.y + dir[i][1];
40             if( v.x>=1 && v.x<=n && v.y>=1 && v.y<=n ){
41                 if(dist[v.x][v.y] > dist[u.x][u.y] + G[v.x][v.y]){
42 
43                     dist[v.x][v.y] = dist[u.x][u.y] + G[v.x][v.y];
44 
45                     if(vis[v.x][v.y] == false){
46                         // if u is out of the queu
47                         // vis[u] is true
48                         vis[v.x][v.y] = true;
49                         q.push(v);
50                     }
51                 }
52             }
53         }
54 
55     }
56 }
57 
58 long long dfs(int x, int y)
59 {
60     if(dp[x][y] > 0)
61         return dp[x][y];
62 
63     for(int i = 0; i < 4; ++i){
64         int _x = x + dir[i][0];
65         int _y = y + dir[i][1];
66         if(_x>=1 && _x<=n && _y>=1 && _y<=n){
67             if(dist[_x][_y] < dist[x][y]){
68                 dp[x][y] += dfs(_x, _y); 
69             }
70         }
71     }
72     return dp[x][y];
73 }
74 
75 int main(int argc, char const *argv[])
76 {
77     // freopen("_in", "r", stdin);
78     while(~scanf("%d", &n)){
79         for(int i = 1; i <= n; ++i){
80             for(int j = 1; j <= n; ++j){
81                 scanf("%d", &G[i][j]);
82                 dist[i][j] = INT_MAX;
83                 vis[i][j] = false;
84             }
85         }
86         spfa();
87 
88         memset(dp, 0, sizeof(dp));
89         dp[n][n] = 1;
90 
91         printf("%lld
", dfs(1, 1));        
92     }
93     return 0;
94 }