这几天忙着复习也没顾得刷题,,罪过啊,,O(∩_∩)O~
这一题是一道小综合题,最短路和0—1背包结合,,调试了好大一会,,纠结,,感觉自己弱爆了,,
我感觉像邻接表,循环链表了,能自己写的自己写也挺好的,,毕竟容易查找错误,而且能加深对邻接表,循环链表的理解,,
#include<iostream> #include<algorithm> #include<cstdio> #include<string.h> #define N 101 #define M 0x3f using namespace std; typedef struct { int to,len,next; }Node; Node node[1000*N]; int dist[N],head[N],cost[N],result[10000*N],Q[N*1000]; bool visit[N]; int num,s,n,m; void init() { num=0; memset(head,-1,sizeof(head)); memset(result,0,sizeof(result)); memset(dist,M,sizeof(dist));//有时候这样初始化不正确 /* 这样写保险,,,, for(int i=0;i<=n;++i) dist[i]=M;*/ } void Add(int a,int b,int c) { node[num].len=c; node[num].to= b; node[num].next=head[a]; head[a]=num++; } void SPFA() { dist[0]=0; memset(visit,false,sizeof(visit)); int top=-1,tail=-1; Q[++top]=0; visit[0]=true; while(top>tail) { int u=Q[++tail]; visit[u]=false; for(int i=head[u];i!=-1;i=node[i].next) if(dist[u]+node[i].len<dist[node[i].to]) { dist[node[i].to]=dist[u]+node[i].len; if(!visit[node[i].to]) { Q[++top]=node[i].to; visit[node[i].to]=true; } } } } int main() { int Case; scanf("%d",&Case); while(Case--) { init(); scanf("%d%d%d",&s,&n,&m); for(int i=0;i!=m;++i) { int a,b,c; scanf("%d%d%d",&a,&b,&c); Add(a,b,c); Add(b,a,c); } for(int i=1;i<=n;++i) scanf("%d",&cost[i]); SPFA(); for(int i=1;i<=n;++i) for(int j=s;j>=dist[i];--j) result[j]=max(result[j-dist[i]]+cost[i],result[j]); printf("%d\n",result[s]); } //system("pause"); return 0; }
您还没有登录,请您登录后再发表评论
NULL 博文链接:https://128kj.iteye.com/blog/1716385
NULL 博文链接:https://128kj.iteye.com/blog/1716609
查看地址 https://blog.csdn.net/qq_43333395/article/details/98508424 目录: 数据结构: 1.RMQ (区间最值,区间出现最大次数,求区间gcd) 2.二维RMQ求区间最大值 (二维区间极值) 3.线段树模板(模板为区间加法) ...
ACM Template of kuangbin 3 数据结构 56 3.1 划分树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2 RMQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....
3 | 大团问题 DP + DFS ................................................. 3 | 欧拉路径O(E) ............................................................... 3 | DIJKSTRA数组实现O(N^2) ....................
SPFA[知乎:叶枝黎曼].py
ACM算法模板的PDF版本,方便大家打印与使用,所有模板均经过测试。 最短路: SPFA模板 Dijkstra模板 Floyd模板 图论--最短路--第K短路(IDA*)(IDA Star)模板 传递闭包: 传递闭包 欧拉与...
SPFA算法模版+邻接表实现.docx
各种算法模板(二分图最大匹配匈牙利算法、最小生成树prime和kruskal算法、Dijkstra算法、两点最短路径负权值边SPFA算法、图任意两点最短路径Floy算法、网络最大流SAP算法、网络最大流最小费用算法、乘法逆元gcd扩展...
SPFA算法,acm常用的算法,求最短路径
最短路无向图spfa+slm优化,可作为模板使用
SPFA import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class SPFA { static SE[] e = new SE[9999]; static int[] dis = new int[9999]; ...
Solving the shortest path problem
这里面的内容是个PPT,介绍的很好,如果你想更加的清楚 SPFA 和Bellman_ford.ppt 最短路算法的原理,这是个不错的选择
最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。
自己打的spfa算法板子。包含邻接表的两种形式,邻接矩阵Map;此代码不完全,(使用是要注释掉部分的)在使用时要结合题意更改。望采纳!
ACM/ICPC模板 内容大概有这些 其他 --高精度模板 --RMQ --改点堆优化的dijkstra算法 --快速付利叶变换 --稳定婚姻问题 --SPFA(最短路快速算法) // thanks to love8909 几何相关 --初等几何学 --多边形几何 --...
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 这个是自己写的,思想还是一样发的。
基本思想 用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。直到队列为空时算法结束; 利用了每个点不会更新次数太多的...
SPFA算法就解决了重复计算的问题,在大数据面前大大减少运行时间 该算法改善的思想是避免顶点进行无效的重复更新,对有待更新的顶点移入队列,已更新的顶点移出队列,避免待更新的顶点中存在重复顶点
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1716385
NULL 博文链接:https://128kj.iteye.com/blog/1716609
查看地址 https://blog.csdn.net/qq_43333395/article/details/98508424 目录: 数据结构: 1.RMQ (区间最值,区间出现最大次数,求区间gcd) 2.二维RMQ求区间最大值 (二维区间极值) 3.线段树模板(模板为区间加法) ...
ACM Template of kuangbin 3 数据结构 56 3.1 划分树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2 RMQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....
3 | 大团问题 DP + DFS ................................................. 3 | 欧拉路径O(E) ............................................................... 3 | DIJKSTRA数组实现O(N^2) ....................
SPFA[知乎:叶枝黎曼].py
ACM算法模板的PDF版本,方便大家打印与使用,所有模板均经过测试。 最短路: SPFA模板 Dijkstra模板 Floyd模板 图论--最短路--第K短路(IDA*)(IDA Star)模板 传递闭包: 传递闭包 欧拉与...
SPFA算法模版+邻接表实现.docx
各种算法模板(二分图最大匹配匈牙利算法、最小生成树prime和kruskal算法、Dijkstra算法、两点最短路径负权值边SPFA算法、图任意两点最短路径Floy算法、网络最大流SAP算法、网络最大流最小费用算法、乘法逆元gcd扩展...
SPFA算法,acm常用的算法,求最短路径
最短路无向图spfa+slm优化,可作为模板使用
SPFA import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class SPFA { static SE[] e = new SE[9999]; static int[] dis = new int[9999]; ...
Solving the shortest path problem
这里面的内容是个PPT,介绍的很好,如果你想更加的清楚 SPFA 和Bellman_ford.ppt 最短路算法的原理,这是个不错的选择
最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。
自己打的spfa算法板子。包含邻接表的两种形式,邻接矩阵Map;此代码不完全,(使用是要注释掉部分的)在使用时要结合题意更改。望采纳!
ACM/ICPC模板 内容大概有这些 其他 --高精度模板 --RMQ --改点堆优化的dijkstra算法 --快速付利叶变换 --稳定婚姻问题 --SPFA(最短路快速算法) // thanks to love8909 几何相关 --初等几何学 --多边形几何 --...
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 这个是自己写的,思想还是一样发的。
基本思想 用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。直到队列为空时算法结束; 利用了每个点不会更新次数太多的...
SPFA算法就解决了重复计算的问题,在大数据面前大大减少运行时间 该算法改善的思想是避免顶点进行无效的重复更新,对有待更新的顶点移入队列,已更新的顶点移出队列,避免待更新的顶点中存在重复顶点