HDU 2544 最短路 SPFA模板题 发表于 2017-05-14 | 分类于 算法 | 阅读次数: 字数统计: 432 字 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2544 题意&题解最短路模板题,以此题记录SPFA模板 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<ctime>#include<iostream>#include<queue>#include<algorithm>using namespace std;#define INF 0x3f3f3f3fconst int maxn=105;const int maxm=10005;int visit[maxn],dist[maxn];int n,m,id;//链式前向星建图struct Node{ int v,w,next;}edges[maxm];int head[maxn]; void addedge(int u,int v,int w) //u到v的权值为w的边{ edges[id].v=v; edges[id].w=w; edges[id].next=head[u]; //把之前的第一条边作为当前边的最后一条边 head[u]=id++; //id为从0开始的标号}//建图void init(){ memset(head,-1,sizeof(head)); int u,v,w; id=0; for(int i=0;i<m;i++) { scanf("%d %d %d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); }}void spfa(int st){ fill(visit,visit+maxn,0); //标记所有节点未被访问 fill(dist,dist+maxn,INF); //求最短路,初始化最大值 queue<int> Q; visit[st]=1; dist[st]=0; Q.push(st); while (!Q.empty()) { int now=Q.front(); Q.pop(); visit[now]=0; //注意此处将该点标记为未访问 for(int i=head[now];i!=-1;i=edges[i].next) { int v=edges[i].v; int w=edges[i].w; if(dist[v]>dist[now]+w) //最短路松弛 { dist[v]=dist[now]+w; if(!visit[v]) { Q.push(v); visit[v]=1; } } } }}void solve(){ while(scanf("%d %d",&n,&m)!=EOF) { if(n==0 &&m==0) break; init(); spfa(1); int ans=dist[n]; printf("%d\n",ans); }}int main(){ freopen("input.txt","r",stdin); solve(); return 0;} 赏 WeChat Pay Alipay 本文作者: Sixzeroo 本文链接: https://www.liuin.cn/2017/05/14/HDU-2544-最短路-SPFA模板题/ 发布时间: 2017年5月14日 - 21时05分 最后更新: 2019年1月6日 - 14时01分 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!