Bellman-ford（队列优化）

洛谷上的题：https://www.luogu.com.cn/problem/P3371
时间复杂度，最坏的情况也是(MN)
代码如下：

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int FF = 0x7fffffff;
const int N = 1e6+5;
int u[N],v[N],w[N],dis[N],b[N],first[N],net[N];
int n,m,k;
int main ()
{
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i]>>w[i];
        net[i]=first[u[i]];
        first[u[i]]=i;
    }
    memset(dis,0x3f,sizeof dis);
    //memset(first,-1,sizeof first);
    dis[k]=0;
    queue<int> q;
    q.push(k);
    b[k]=1; //标记点k已入队
    while(!q.empty())
    {
        for(int i=first[q.front()];i;i=net[i])//扫描当前顶点所有边 
        {
            if(dis[v[i]]>dis[u[i]]+w[i])//判断此边是否可以松弛 
            {
                dis[v[i]]=dis[u[i]]+w[i];//更新k到v[i]的最短路程 
                if(b[v[i]]==0)//判断是否在队列中
                {
                    b[v[i]]=1;
                    q.push(v[i]);
                }
            }
        }
        b[q.front()]=0;
        q.pop();
    }
    for(int i=1;i<=n;i++) 
    {
        if(dis[i]==INF)
            cout<<FF<<" ";
        else
            cout<<dis[i]<<" ";
    }
    return 0;
}