【算法】spfa算法求最短路（没有负环）

题目 

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围

1 ≤ n,m ≤ 1e5
图中涉及边长绝对值均不超过 10000。

思路

         bfs思想，将节点1的距离初始化为0，存入队列中进入循环。在循环中从队列中取出一个节点p，使用节点p对p的后继节点a进行更新（如果1->...->a的距离大于1->...->p->a的距离，则对a节点进行更新，如果点a不在队列中，就把点a放入这个队列中），将p的后继节点遍历完之后进入下一次循环，直到队列为空（如果存在负环，则会进入无限循环，但是题目保证不存在负环）。

代码

#include
#define int long long
#define N 100100
using namespace std;
 
int n,m;// n表示点数，m表示边数
int w[N],e[N],ne[N],h[N],idx;// 邻接表四件套，w数组储存点a到点b的距离
int dist[N];// dist数组储存点1到点i的距离
bool st[N];// 用来记录点i是否在队列q中
queue<int> q;// bfs核心
void add(int a,int b,int c)
{
    w[idx] = c,e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
 
void spfa()
{
    memset(dist,0x3f,sizeof(dist));//将距离初始化为无穷大
    dist[1] = 0;// 点1到点1的距离为0
    st[1] = true;// 将点1储存到队列中
    q.push(1);
    while(!q.empty())
    {
        int t = q.front();
        q.pop();//将节点从队列中取出
        st[t] = false;// 标记一下点t已经不在队列中了
        for(int i = h[t]; i != -1; i = ne[i])// 将点t的后继节点遍历一遍
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])// 更新符合条件的点
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])// 如果这个点满足dist[j] > dist[t] + w[i]的条件，并且不再队列内部，则将其放入队列中
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}
 
int32_t main()
{
    memset(h,-1,sizeof(h));// 初始化头节点
    cin >> n >> m;
    for(int i = 0; i < m; i ++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    spfa();
    if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;
}