算法

procedure Shortest-Path-Faster-Algorithm(G, s)
  1    for each vertex v ≠ s in V(G) 
  2        d(v) := ∞
  3    d(s) := 0
  4    push s into Q
  5    while Q is not empty do
  6        u := poll Q
  7        for each edge (u, v) in E(G) do
  8            if d(u) + w(u, v) < d(v) then
  9                d(v) := d(u) + w(u, v)
 10                if v is not in Q then
 11                    push v into Q

c++

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=100010;

class Grap{
    public:
    using callt=function<void(int ,int)> ;

    Grap(){ memset(h,-1,sizeof h); }

    void add(int a,int b,int c){
        e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
    }

    void adj(int a,callt func){
        //小心这里的下一个是i=ne[i]，而不是i++
        for(int i=h[a];i!=-1;i=ne[i]) func(e[i],w[i]);
        //func获取a的下一个邻居e[i]和到这个邻居的距离w[i]
    }

    int h[N],e[N],ne[N],w[N],idx=0;
};

Grap grah;
int n,m;
int dist[N],st[N];
int spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    queue<int>q;
    q.push(1);
    st[1]=1;

    while(q.size()){
        int now=q.front();q.pop();
        st[now]=0;

        grah.adj(now,[&](int to,int w){
            if(dist[now]+w<dist[to]){
                dist[to]=dist[now]+w;
                //不在队列时才加入队列
                if(!st[to]) st[to]=1,q.push(to);
            }
        });
    }

    return dist[n];
}

int main(){
    cin>>n>>m;
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        grah.add(a,b,c);
    }

    int res=spfa();
    if(res==0x3f3f3f3f) puts("impossible");
    else cout<<res<<endl;
    return 0;

}