本文主要是介绍P - The Shortest Path in Nya Graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://cn.vjudge.net/problem/HDU-4725
题意：要求你建立一个奇怪的图，每一个点都在某一个层上，每一层上的点相互到达的权值为0，每一层可以到达相邻的两个层，权值为c，还有一些特殊的边可以链接不同层上的两个点，要求求第一个点到最后一个点的最短路。
题解：对于每一个点我们都要建立两个辅助点，然后每一层的相邻两个层连起来，最后把特殊边连起来，用优先队列+spfa就求出来了。
代码：
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#define inf 0x3f3f3f3fusing namespace std;struct node
{int u,v,w,next;
}ma[700005];int h[500005];
int t,b;void adde(int u,int v,int w)
{ma[t].u=u;ma[t].v=v;ma[t].w=w;ma[t].next=h[u];h[u]=t++;
}int dis[500005],vis[500005];void spfa()
{int i;for( i = 1;i <= 3*b;i++)vis[i] = 0;for( i = 1;i <= 3*b;i++)dis[i] = inf;deque<int >Q;Q.push_back(1);vis[1]=1;dis[1]=0;while(Q.size()){int u=Q.front();Q.pop_front();vis[u]=0;for(i=h[u];i!=-1;i=ma[i].next){if(dis[ma[i].v]>dis[u]+ma[i].w){dis[ma[i].v]=dis[u]+ma[i].w;if(!vis[ma[i].v]){vis[ma[i].v]=1;if(Q.size()&&dis[ma[i].v]<dis[Q.front()])Q.push_front(ma[i].v);elseQ.push_back(ma[i].v);}}}}
}int main()
{int a,c,d,e,f,g;int i,j=0,s;scanf("%d",&a);while(a--){++j;scanf("%d %d %d",&b,&c,&d);memset(h,-1,sizeof(h));t=0;for(i=1;i<=b;i++){scanf("%d",&s);adde(i,b+s*2-1,0);adde(b+s*2,i,0);}for(i=1;i<b;i++){adde(b+i*2-1,b+(i+1)*2,d);adde(b+(i+1)*2-1,b+i*2,d);}for(i=1;i<=c;i++){scanf("%d %d %d",&e,&f,&g);adde(e,f,g);adde(f,e,g);}spfa();if(dis[b]==inf||b==0)printf("Case #%d: %d\n",j,-1);else printf("Case #%d: %d\n",j,dis[b]);}return 0;
}
这篇关于P - The Shortest Path in Nya Graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
