自以为已经做了好多年dp，可最近随意一个dp放在眼前却总是不能想到！！

先用bfs（队列）处理每个点到目的地最短路，不用转化为图用dijkstra，麻烦且超时。

然后记忆化搜素，对于起始点，四个方向若有到达目的地最短路小于当前点，则起始点的方案数+=该方向点到目的地方案数。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 struct dian{ 7     int x,y,time; 8 }; 9 int xx[]={
    1,-1,0,0,};10 int yy[]={
    0,0,1,-1};11 int n,dis[55][55],a[55][55];12 long long vis[55][55];13 void shortpath()14 {15     dian n1,n2;16     queue
          
           q;17     while (!q.empty()) q.pop();18     n1.x=n; n1.y=n; n1.time=a[n][n];19     q.push(n1); dis[n][n]=n1.time;20     while (!q.empty())21     {22         n1=q.front(); q.pop();23         for (int i=0;i<4;i++)24         {25             n2.x=n1.x+xx[i]; n2.y=n1.y+yy[i]; n2.time=n1.time+a[n2.x][n2.y];26             if (n2.x>0&&n2.x<=n&&n2.y>0&&n2.y<=n&&dis[n2.x][n2.y]>n2.time)27             {28                 dis[n2.x][n2.y]=n2.time;29                 q.push(n2);30             }31         }32     }33 }34 long long dp(int x,int y)35 {36     if (x==n&&y==n) vis[x][y]=1;37     if (vis[x][y]!=-1) return vis[x][y];38     int x1,y1;39     long long temp=0;40     for (int i=0;i<4;i++)41     {42         x1=x+xx[i]; y1=y+yy[i];43         if (x1>0&&x1<=n&&y1>0&&y1<=n&&dis[x1][y1]
          
         
        
       
      

传送门：