題目描述
如題，給出一個(gè)有向圖，請(qǐng)輸出從某一點(diǎn)出發(fā)到所有點(diǎn)的最短路徑長(zhǎng)度。
輸入輸出格式
輸入格式：

第一行包含三個(gè)整數(shù)N、M、S，分別表示點(diǎn)的個(gè)數(shù)、有向邊的個(gè)數(shù)、出發(fā)點(diǎn)的編號(hào)。

接下來M行每行包含三個(gè)整數(shù)Fi、Gi、Wi，分別表示第i條有向邊的出發(fā)點(diǎn)、目標(biāo)點(diǎn)和長(zhǎng)度。

輸出格式：
一行，包含N個(gè)用空格分隔的整數(shù)，其中第i個(gè)整數(shù)表示從點(diǎn)S出發(fā)到點(diǎn)i的最短路徑長(zhǎng)度（若S=i則最短路徑長(zhǎng)度為0，若從點(diǎn)S無法到達(dá)點(diǎn)i，則最短路徑長(zhǎng)度為2147483647）
輸入輸出樣例
輸入樣例#1：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
輸出樣例#1：
0 2 4 3
1.SPFA的描述
SPFA（Shortest Path Faster Algorithm）（隊(duì)列優(yōu)化）算法是求單源最短路徑的一種算法，它還有一個(gè)重要的功能是判負(fù)環(huán)（在差分約束系統(tǒng)中會(huì)得以體現(xiàn)），在Bellman-ford算法的基礎(chǔ)上加上一個(gè)隊(duì)列優(yōu)化，減少了冗余的松弛操作，是一種高效的最短路算法。SPFA算法由段凡丁于1994年西安交通大學(xué)提出。
2.SPFA算法過程
算法過程分為兩步
1.初始化
2.松弛操作
a)初始化過程
將未特別說明的數(shù)據(jù)設(shè)置為正無窮（int最大值2147483647）。
i=j時(shí)，它到它自己的邊權(quán)為0，無向邊的數(shù)據(jù)直接更新為正無窮，在后面的代碼實(shí)現(xiàn)時(shí)，我們可以進(jìn)行對(duì)比更新。
b)松弛操作
初始化源點(diǎn)數(shù)據(jù)，設(shè)置一個(gè)dis數(shù)組，inq數(shù)組，q隊(duì)列。
dis用于存最小路徑，inq判斷當(dāng)點(diǎn)是否在隊(duì)列內(nèi)，q用于存待松弛的邊。
第一個(gè)壓入q隊(duì)列的數(shù)據(jù)為源點(diǎn)1。
進(jìn)入核心循環(huán)代碼。
取出隊(duì)列頂數(shù)據(jù)，為待松弛的邊。
之后進(jìn)行遍歷，spfa的核心就是過一點(diǎn)的距離+該點(diǎn)長(zhǎng)度小于末點(diǎn)的dis值，就更新末點(diǎn)的dis。
接著繼續(xù)判斷沒有訪問過的邊，加入待松弛隊(duì)列。
最后直接輸出dis數(shù)組數(shù)據(jù)即為最小路徑。
代碼實(shí)現(xiàn)

#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<list>
using namespace std;
const int maxn = 500000 + 10;
struct nodes {
 int u, to, w;
};//to表示末點(diǎn)，w表示長(zhǎng)度
int dis[10000 + 20];
typedef struct nodes node;//方便后面的定義。。
list<node> v[10000 + 20];//邊集，list和vector都可以。。
int n, m, s;
int inq[10000 + 20]; //用inq來表示點(diǎn)是否在queue中，判重和記憶。。
queue<int> q;//不解釋了、、
int main()
{
 cin >> n >> m >> s;
 for (int i = 0; i < m; i++) {
  int x, y, z;
  cin >> x >> y >> z;
  v[x].push_back({ x,y,z });    //用list來讀入邊集
 }
 for (int i = 0; i < 10000 + 20; i++) dis[i] = 2147483647; //初始化的時(shí)候  dis全部是2147483647，而是dis[s]=0；這個(gè)在輸出的時(shí)候有用。。
 dis[s] = 0;
 q.push(s);
 inq[s] = 1;    //用來判斷點(diǎn)是否在隊(duì)列里面，，類似記憶。。
 while (!q.empty()) {
  int cur = q.front(); q.pop();//取出待松弛的邊
  inq[cur] = 0;
  for (list<node>::iterator it = v[cur].begin(); it != v[cur].end(); it++) {//遍歷
   if (dis[cur] + it->w < dis[it->to]) {//這個(gè)是松弛操作的核心。。如果過一點(diǎn)的距離+該點(diǎn)長(zhǎng)度小于末點(diǎn)的dis值，就更新末點(diǎn)的dis
    dis[it->to] = dis[cur] + it->w;
    if (!inq[it->to]) {//判斷是否in queue
     q.push(it->to);//松弛之后，加入queue，等待接下來的松弛。。
    }
   }
  }
 }
 for (int i = 1; i <= n; i++) {
  cout << dis[i] << " ";
 }
 return 0;
}