hdu1428 spfa+记忆化搜索

题意:
     题意坑爹,很容易误认成是做短路的条数,题意是给你一个图,让你从起点走到终点,问你有多少种走法,但有一个限制,假如你想从a走到b,必须满足终点到b的最短距离小于终点到a的最短距离.


思路:
     先以终点为起点跑一便单元源最短路,然后记忆化搜索路径条数就行了...

#include<stdio.h>
#include<string.h>
#include<queue>

#define N_node 2500 + 500
#define N_edge 10000 + 1000
#define inf 9223372036854775807 

using namespace std;

typedef struct
{
   int to ,next;
   __int64 cost;
}STAR;

STAR E[N_edge];
int list[N_node] ,tot;
__int64 s_x[N_node];

void add(int a ,int b ,__int64 c)
{
   E[++tot].to = b;
   E[tot].cost = c;
   E[tot].next = list[a];
   list[a] = tot;
}

void spfa(int s ,int n)
{
   int mark[N_node] = {0};
   mark[s] = 1;
   for(int i = 0 ;i <= n ;i ++)
   s_x[i] = inf;
   s_x[s] = 0;
   queue<int>q;
   q.push(s);
   while(!q.empty())
   {
      int tou ,xin;
      tou = q.front();
      q.pop();
      mark[tou] = 0;
      for(int k = list[tou] ;k ;k = E[k].next)
      {
         xin = E[k].to;
         if(s_x[xin] > s_x[tou] + E[k].cost)
         {
            s_x[xin] = s_x[tou] + E[k].cost;
            if(!mark[xin])
            {
               mark[xin] = 1;
               q.push(xin);
            }
         }
      }
   }
}

__int64 maxx[N_node];
int mark[N_node];
__int64 map[N_node][N_node];
__int64 dfs(int s ,int t)
{
   if(maxx[s] != 0) return maxx[s];
   __int64 sum = 0;
   for(int k = list[s] ;k ;k = E[k].next)
   {
      int to = E[k].to;
      if(mark[to] || s_x[to] >= s_x[s]) continue;
      mark[to] = 1;
      sum += dfs(to ,t);
      mark[to] = 0;
   }
   maxx[s] = sum;
   return sum;
}

int main ()
{
   int n ,i ,j;
   while(~scanf("%d" ,&n))
   {
      for(i = 1 ;i <= n ;i ++)
      for(j = 1 ;j <= n ;j ++)
      scanf("%I64d" ,&map[i][j]);
      memset(list ,0 ,sizeof(list));
      tot = 1;
      for(i = 1 ;i <= n ;i ++)
      for(j = 1 ;j <= n ;j ++)
      {
         int now = (i - 1) * n + j;
         if(j < n) add(now ,now + 1 ,map[i][j+1]);
         if(j > 1) add(now ,now - 1 ,map[i][j-1]);
         if(i < n) add(now ,now + n ,map[i+1][j]);
         if(i > 1) add(now ,now - n ,map[i-1][j]);
      }
      add(0 ,1 ,map[1][1]);
      add(1 ,0 ,map[1][1]);
      spfa(n * n ,n * n);
      
      memset(maxx ,0 ,sizeof(maxx));
      memset(mark ,0 ,sizeof(mark));
      mark[0] = 1;
      maxx[n*n] = 1;
      printf("%I64d
" ,dfs(0 ,n * n));
   }
   return 0;
}