hdu1428 spfa+记忆化搜寻
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\n" ,dfs(0 ,n * n)); } return 0; }