Bellman-Ford算法–有负权边就用它（或spfa，spfa好一些）

两层循环
第一层循环n次
$~~~~~~~$第二层循环 循环所有的边(a,b,w)
$~~~~~~~~~~~~~$dist[j]=min(dist[j],dist[t]+w);

注意事项

1. 要用上一次的数组DIST去更新结果，避免出现串联
2. 最后判断的时候由于中间点到n之间可能存在负权边，所以要>0x3f3f3f3f-5e6才行
3. 如果存在负权回路，则最短路径不一定存在！

代码

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
typedef struct II{
    int first,second,third;
}II;
const int N=510,M=1e5+10;
II edge[M];
int dist[N],DIST[N];
int n,m,k;
bool bellmanFord(int x){
    int a,b,c;
    for(int i=0;i<k;i++){
        copy(begin(dist),end(dist),begin(DIST));//备份
        for(int j=0;j<m;j++){
            a=edge[j].first;
            b=edge[j].second;
            c=edge[j].third;
            if(dist[b]>DIST[a]+c) dist[b]=DIST[a]+c;//更新只用上一次的结果
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return false;//有可能1-5的最短路径是正无穷,5-n的距离是-2 那最后dist[n]会略小于0x3f3f3f3f
    //由于最多有500个点，dist[n]最多减500*10000=五百万
    return true;
}
int main(void){
    int a,b,c;
    memset(dist,0x3f,sizeof dist);
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        edge[i].first=a;
        edge[i].second=b;
        edge[i].third=c;
    }
    dist[1]=0;
    if(bellmanFord(1)) cout<<dist[n];
    else cout<<"impossible";

}