本文主要是介绍1382：最短路(Spfa)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
给定 MM 条边， NN 个点的带权无向图。求 11到 NN 的最短路。
【输入】
第一行：N,M(N≤100000，M≤500000)N,M(N≤100000，M≤500000)；
接下来MM行33个正整数：ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci≤1000ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci≤1000。
【输出】
一个整数，表示 11 到 NN 的最短距离。
【输入样例】
4 4 1 2 1 2 3 1 3 4 1 2 4 1
【输出样例】
2
【提示】
【样例解释】
注意图中可能有重边和自环,数据保证 11 到 NN 有路径相连。
spfa的模板题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
int head[320000]; //头结点数组
int cnt; //点的个数struct node
{int next;int from, to, dis;
}s[3200000]; //点void add_edge(int from, int to, int dis)
{s[++cnt].next = head[from];s[cnt].to = to;s[cnt].dis = dis;head[from] = cnt;
}int dis[250000]; //距离
int vis[250000]; //标记
void spfa()
{memset(dis, inf, sizeof(dis)); //初始化距离memset(vis, 0, sizeof(vis)); //初始化标记vis[1] = 1;dis[1] = 0;queue<int>Q; //队列在dpfa里面Q.push(1); //放入初始点！！！！while (!Q.empty()) {int u = Q.front(); // uQ.pop();vis[u] = 0;for (int i = head[u];i;i = s[i].next) {int to = s[i].to;int di = s[i].dis;if (dis[to]>dis[u] + di) {dis[to] = dis[u] + di;if (!vis[to]) {vis[to] = 1;Q.push(to);}}}}
}int main()
{scanf("%d %d", &n, &m);memset(head, 0, sizeof(head));for (int i = 0;i<m;i++) {int a, b, c; //起点，终点，距离scanf("%d %d %d", &a, &b, &c);add_edge(a, b, c);add_edge(b, a, c);}spfa();printf("%d\n", dis[n]);return 0;
}
这篇关于1382：最短路(Spfa)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
