題目：（來源于AcWing）

給定一個?n?個點?m?條邊的有向圖，圖中可能存在重邊和自環，?邊權可能為負數。

請你求出?1?號點到?n?號點的最短距離，如果無法從?1?號點走到?n?號點，則輸出?impossible。

數據保證不存在負權回路。

輸入格式

第一行包含整數?n?和?m。

接下來?m?行每行包含三個整數?x,y,z，表示存在一條從點?x?到點?y?的有向邊，邊長為?z。

輸出格式

輸出一個整數，表示?1?號點到?n?號點的最短距離。

如果路徑不存在，則輸出?impossible。

數據范圍

1≤n,m≤105,
圖中涉及邊長絕對值均不超過?10000。

輸入樣例：

3 3
1 2 5
2 3 -3
1 3 4

輸出樣例：

2

改進思路：

我們發現，只有一個節點的最短路徑被更新之后，這個節點才可能被用來繼續更新其出邊的節點的最短路徑。

代碼實現：

?

#include<iostream>
#include<algorithm>
using namespace std;
#include<queue>
int n,m;
const int N = 100010;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool exi[N];//存儲隊列中是否已經有這個點了void add(int a,int b,int c)
{e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx++;
}int spfa()
{queue<int> q;q.push(1);dist[1] = 0;exi[1] = true;while(q.size()){int nownode = q.front();q.pop();exi[nownode] = false;//取出該節點后更新exi數組//遍歷出邊for(int i = h[nownode];i!=-1;i=ne[i]){int tempnode = e[i];if(dist[tempnode] > dist[nownode]+w[i]){dist[tempnode] = dist[nownode]+w[i];if(!exi[tempnode]){q.push(tempnode);//只有本節點最短路被更新了，才需要更新這個節點的出邊exi[tempnode] =true;}}}}if(dist[n] ==0x3f3f3f3f) return 0x3f3f3f3f;return dist[n];
}int main()
{fill(h,h+N,-1);//必須在存儲邊操作前初始化fill(dist,dist+N,0x3f3f3f3f);idx = 0;scanf("%d%d",&n,&m);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}int t = spfa();if(t == 0x3f3f3f3f)cout <<"impossible"<<endl;else cout << t<<endl;return 0;
}

細節：

1. ?需要記錄隊列中是否已經存在該節點，如果已經存在，即便其被更新，也不用再添加它。

2. 頭指針h[]要在添加邊之前初始化為-1.

spfa算法判斷負環：

只需要添加數組count[]，記錄每個節點最短路徑，上的邊的數量，如果邊數>n，說明存在負環。

spfa算法的性能：?

1. 時間復雜度可以為O(n+m），但最壞時退化為O(nm）。
2. 可以處理自環、重邊、負環、允許邊權為負。

?