首先从终点bfs，保存每一个节点到终点的最短路径，然后从起点dfs，记忆化，如果满足题目给定的拓扑序就加上从那个点到终点的路径数。所谓满足拓扑序就是题目所给定的taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A，这句话仔细读上几十遍就能明白题目意图了。
漫步校园
代码：
#include <iostream>
#include <queue>
using namespace std;
int dir[4][2] = 
{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
struct point {
int x;
int y;
int time;
bool friend operator < (point a, point b) {
return a.time > b.time;
}
}temp, tt;
priority_queue < point > q;
int hash[51][51], map[51][51];
__int64 dp[51][51];
int n;
__int64 dfs(int x, int y) {
int i;
int tx, ty;
__int64 sum = 0;
if(x == n && y == n)
return 1;
for(i = 0; i < 4; i++) {
tx = x + dir[i][0];
ty = y + dir[i][1];
if(tx < 1 || ty < 1 || tx > n || ty > n)
continue;
if(hash[x][y] > hash[tx][ty]) {
if(dp[tx][ty] == -1) {
dp[tx][ty] = dfs(tx, ty);
}
sum += dp[tx][ty];
}
}
return sum;
}
int main() {
int i, j;
while(scanf("%d", &n) != EOF) {
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
scanf("%d", &map[i][j]);
}
}
temp.x = n;
temp.y = n;
temp.time = map[n][n];
memset(hash, -1, sizeof(hash));
hash[n][n] = map[n][n];
while(!q.empty())
q.pop();
q.push( temp );
while(!q.empty()) {
temp = q.top();
q.pop();
for(i = 0; i < 4; i++) {
tt.x = temp.x + dir[i][0];
tt.y = temp.y + dir[i][1];
if(tt.x < 1 || tt.y < 1 || tt.x > n || tt.y > n)
continue;
tt.time = temp.time + map[tt.x][tt.y];
if(hash[ tt.x ][ tt.y ] == -1 || tt.time < hash[ tt.x ][ tt.y ]) {
hash[ tt.x ][ tt.y ] = tt.time;
q.push( tt );
}
}
}
memset(dp, -1, sizeof(dp));
dp[1][1] = dfs(1, 1);
printf("%I64d\n", dp[1][1]);
}
return 0;
}