大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
职务地址:HDU 4725
这题卡了好长时间了,建图倒是会建,可是不会最短路的算法优化,本以为都须要堆去优化的,打算学了堆之后再来优化。可是昨晚CF的一道题。。(那题也是不优化过不了。。)然后我就知道了还有不须要堆也能够的优化。并且优化的操作非常easy,把单向队列变成双端队列即可了。详细优化思路是若d[v]比队列前端的元素的距离小,就增加队列前端,否则增加队列尾端。
非常easy吧。
。。会了后。把这题一加上slf优化就过了。
。。
事实上这题的重点在于建图。。不在于优化。。。。sad。。
这题的建图就是把层次也都抽象成两个点。一个用来出,一个用来进。我是看的kuangbin大神的博客才知道的。
详情见kuangbin大神博客。。kuangbin大神博客
懒得去的能够看以下博文文字的复制。。
N个点,然后有N层。要假如2*N个点。
总共是3*N个点。
点1~N就是相应的实际的点1~N. 要求的就是1到N的最短路。
然后点N+1 ~ 3*N 是N层拆出出来的点。
第i层,入边到N+2*i-1, 出边从N+2*i 出来。
(1<= i <= N)
N + 2*i 到 N + 2*(i+1)-1 加边长度为C. 表示从第i层到第j层。
N + 2*(i+1) 到 N + 2*i – 1 加边长度为C,表示第i+1层到第j层。
假设点i属于第u层,那么加边 i -> N + 2*u -1 N + 2*u ->i 长度都为0
然后我的代码例如以下:
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f; int vis[310000], d[310000], cnt, head[310000], n, num; struct node { int u, v, w, next; } edge[700000]; void add(int u, int v, int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void spfa() { int f1=0, f2=0, i; deque<int>q; q.push_back(1); memset(d,INF,sizeof(d)); memset(vis,0,sizeof(vis)); d[1]=0; vis[1]=1; while(!q.empty()) { int u=q.front(); q.pop_front(); vis[u]=0; for(i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(d[v]>d[u]+edge[i].w) { d[v]=d[u]+edge[i].w; if(!vis[v]) { vis[v]=1; if(!q.empty()&&d[v]<d[q.front()]) { q.push_front(v); } else q.push_back(v); } } } } if(d[n]==INF) d[n]=-1; printf("Case #%d: %d\n",num,d[n]); } int main() { int t, u, v, w, m, c, i; num=0; scanf("%d",&t); while(t--) { num++; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); cnt=0; scanf("%d%d%d",&n,&m,&c); for(i=1; i<=n; i++) //将第i个边与该边所属的层次u相连。 { scanf("%d",&u); add(i,n+2*u-1,0); add(n+2*u,i,0); } for(i=1; i<n; i++) //将每两个相邻的层次互连 { add(n+2*i+1,n+2*i,c); add(n+2*i-1,n+2*i+2,c); } while(m--) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } spfa(); } return 0; }
版权声明:本文博客原创文章。博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117554.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...