SPFA算法 最短路 蓝桥杯

为了做一个最短路的题目，学了Floyd算法，但后来发现Floyd算法只能用邻接矩阵表示图，空间开销大，对于点太多的题目来说很容易爆栈，只好又学习了SPFA算法，终于在平台上测试通过了，把代码贴出来供大家参考。

问题描述

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

第一行两个整数n, m。

接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

对于10%的数据，n = 2，m = 2。

对于30%的数据，n <= 5，m <= 10。

对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

#include<iostream>#include<queue>#include<cstring>#define MAXM 200000+1#define MAXN 20000+1#define INF 0x3f3f3f3fusing namespace std;int dis[MAXN],vis[MAXN];//dis[i]表示开始位置到i位置的最短距离，VIS[i]表示第i个点是否未存入队列struct NODE{	int to;//该边指向的点	int next;//邻接表下一个结点	int value;//权值	NODE(const NODE&t):to(t.to),next(t.next),value(t.value){}    NODE(){}};struct G{	int head[MAXM];//head[i]表示邻接表第i条链指向的第一个节点	NODE node[MAXM];//边节点	int count;//当前存储的边的数目	G() { memset(head, -1, sizeof(head));memset(node, -1, sizeof(node));count = 0; }	void Init(int m)	{		int from, to, value;		for (int i = 0;i < m;i++)		{			cin >> from >> to >> value;			node[count].to = to;			node[count].value = value;			node[count].next = head[from];			head[from] = count++;		}	}	void SPFA(int start)	{		queue<int> s;		int t,cur;		s.push(start);		memset(dis, INF, sizeof(dis));		dis[1] = 0;		vis[start] = 1;		while (!s.empty())		{			cur = s.front();			t = head[cur];			vis[cur] = 0;			s.pop();			while (t != -1)			{				if (dis[node[t].to] > dis[cur] + node[t].value)				{					dis[node[t].to] = dis[cur] + node[t].value;					if (vis[node[t].to] == 0)						s.push(node[t].to), vis[node[t].to] = 1;				}				t = node[t].next;			}		}	}}g;int main(){	int m,n;	cin >> n>>m;	g.Init(m);	g.SPFA(1);	for(int i=2;i<=n;i++)	cout << dis[i]<<endl;	return 0;}