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; }
《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的hdu1428 spfa+记忆化搜索的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。

网址：hdu1428 spfa+记忆化搜索 https://www.yuejiaxmz.com/news/view/1250052

相关内容

CF910A The Way to Home SPFA(队列优化)
动态规划特训：旅行商问题（回溯法或记忆搜索法）
活用标签，提高笔记搜索效率
以旧衣编织情感，探索个人记忆与时尚的交织
记忆与遗忘资料.ppt
高效记忆——联想记忆法
「搜Easy」超级搜索日来袭，发现搜索背后的情绪价值
第8章 记忆
【我敲】大家的搜索记...
[宫殿记忆法的学习方法是什么]宫殿记忆法.docx

随便看看