為了做一個最短路的題目，學了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;}