首先从终点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;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dir[4][2] =
{
{0, 1},
{0, -1},
{1, 0},
{-1, 0}};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct point
{
int x;
int y;
int time;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
bool friend operator < (point a, point b)
{
return a.time > b.time;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}temp, tt;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
priority_queue < point > q;
int hash[51][51], map[51][51];
__int64 dp[51][51];
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
__int64 dfs(int x, int y)
{
int i;
int tx, ty;
__int64 sum = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(x == n && y == n)
return 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(hash[x][y] > hash[tx][ty])
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(dp[tx][ty] == -1)
{
dp[tx][ty] = dfs(tx, ty);
}
sum += dp[tx][ty];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return sum;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i, j;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(scanf("%d", &n) != EOF)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
q.push( temp );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(!q.empty())
{
temp = q.top();
q.pop();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(hash[ tt.x ][ tt.y ] == -1 || tt.time < hash[ tt.x ][ tt.y ])
{
hash[ tt.x ][ tt.y ] = tt.time;
q.push( tt );
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(dp, -1, sizeof(dp));
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dp[1][1] = dfs(1, 1);
printf("%I64d\n", dp[1][1]);
}
return 0;
}