锐客网

  1. 首页 > it技术 > >

最短路|poj1511+链式前向星+dijkstra堆优化

算法最短路

如果看题解往下划拉……
这题网上说卡数据，只能链式前向星才能过？正好学一下链式前向星的处理
其实：这个和vector做的邻接表差不多。可能用起来会快一点？（不然这题邻接表为啥过不了）
我觉得dijkstra的堆优化和spfa算有非常强的关联性
这里提几句：（分析一下异同）
spfa是一种基于bfs的单源最短路算法，起源于bellman-ford。
这个算法名是个梗，一个西南交大的哥们自称发现了这个算法，毕业论文写的这个。他的神之分析复杂度为（m）……
对，就是边的个数。其实这个算法的复杂度是（n*m）.
算法实质就是：bfs遍历源到每个点，如果你熟悉二维迷宫问题的话，也就是每到一个点，就距离+1.其实思路是一样，只不过，因为在图中的bfs因为边权并不是单调递增的，（不是每跳边均为1），就是存在了一个更优j点，让你原本从i到o的距离，因为j点的存在，缩小了。但o之前已经访问过了，到o的距离应该是已经确定，所以o就不能再次被访问了。但实际上从i到j到o这样才是最优。如何给这个bfs机制一个反悔的过程？那就是把vis去掉！但是去掉这个数组你会发现，bfs会一直循环……所以还是需要vis标记。那怎么办？好办！因为bfs的过程需要一个队列，当o在队列中的时候，我们就标记vis，一出队列，就把他的标记取消，这样，o可以重复访问，
【最短路|poj1511+链式前向星+dijkstra堆优化】**SPFA思想:**是一种暴力，因为每次的重复访问都是找到了更优的方案，也就是意味着，当方案全都最优的时候，队列里面就啥也没有了。
dijkstra堆优化算法呢？
也是bfs的思路开始，从源点遍历周围的每个点，但是这个算法借住了堆序列，保证每次的出队列操&遍历作都是从源点到的距离最小的点开始，也就意味着，这个过程是一个新加入的边权单调递增的过程。实际也是一种起源bfs的算法！但是做起来就变成了dfs……简易自习揣摩迷宫问题，与这个最短路问题的联系。其实思想同源，很多人说这个算法是一种贪心，其实这个贪心思维我觉得应该是dijkstra，而不是dijkstra堆优化。dijkstra堆优化理解上更易，普通问题可以通过vector邻接表过，而且很块
卡点的可能需要链式前向星。
这个题就卡这了吧
学习这个小用法的视频
https://www.bilibili.com/video/BV1mJ411S7BB?from=search&seid=479824852082650829
AC代码，鄙人不才，代码可能不是那么pl

#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int M=1000005; int p,q; struct node { int to,next; ll w; } edg[M*2]; int tot; int head[M]; int rhead[M]; void addedge(int u,int v,long long w) { edg[tot].to=v; edg[tot].w=w; edg[tot].next=head[u]; head[u]=tot++; }void rad(int u,int v,long long w) { edg[tot].to=v; edg[tot].w=w; edg[tot].next=rhead[u]; rhead[u]=tot++; }ll dis[M]; ll rdis[M]; int vis[M]; int choice=1; struct cmp { bool operator()(int a, int b) { if(choice==1) //代表正向dij的比较 return dis[a] > dis[b]; //这比较函数，涨见识，可以用到全局变量 return rdis[a] > rdis[b]; } }; ll dijk(int s,int head[],ll dis[]) {priority_queue,cmp> que; que.push(s); memset(vis,0,sizeof(vis)); dis[s]=0; while(!que.empty()) { int now=que.top(); que.pop(); vis[now]=1; for(int i=head[now]; i!=0; i=edg[i].next) { if(dis[edg[i].to]>dis[now]+edg[i].w) { dis[edg[i].to]=dis[now]+edg[i].w; if(!vis[edg[i].to]) que.push(edg[i].to); } } } ll ans=0; for(int i=1; i<=p; i++) { ans+=dis[i]; } return ans; }int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&p,&q); int a,b; ll c; tot=1; memset(head,0,sizeof(head)); memset(rhead,0,sizeof(rhead)); while(q--) { scanf("%d%d%lld",&a,&b,&c); addedge(a,b,c); rad(b,a,c); }ll ans=0; choice=1; memset(dis,0x3f3f3f3f,sizeof(dis)); ans+=dijk(1,head,dis); choice=0; memset(rdis,0x3f3f3f3f,sizeof(rdis)); ans+=dijk(1,rhead,rdis); printf("%lld\n",ans); }return 0; }

    推荐阅读


    上一篇：POJ3414

    下一篇：dfs|codevs【1569】最佳绿草