本文主要是介绍2013成都邀请赛J题||HDU4725 The Shortest Path in Nya Graph（spfa+slf优化最短路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：HDU 4725
这题卡了好长时间了，建图倒是会建，但是不会最短路的算法优化，本以为都需要堆去优化的，打算学了堆之后再来优化，但是昨晚CF的一道题。。（那题也是不优化过不了。。）然后我就知道了还有不需要堆也可以的优化，而且优化的操作很简单，把单向队列变成双端队列就行了。具体优化思路是若d[v]比队列前端的元素的距离小，就加入队列前端，否则加入队列尾端。很简单吧。。。会了后，把这题一加上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);}elseq.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;
}
这篇关于2013成都邀请赛J题||HDU4725 The Shortest Path in Nya Graph（spfa+slf优化最短路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
