SPFA+链式前向星

板子

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=2<<30-1;
const ll maxn=599999;
ll head[maxn*2],cnt=1,n,m,s,dis[maxn];
struct edge{
    ll to,w,nxt;
}d[maxn];
queue<ll>q;
bool vis[maxn];
void add(int u,int v,int w){
    d[cnt].to=v,d[cnt].nxt=head[u];
    d[cnt].w=w;head[u]=cnt++;
}
void spfa(ll s)
{
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=n;i++)    dis[i]=inf;
    dis[s]=0;q.push(s);vis[s]=1;
    while(!q.empty())
    {
        ll ans=q.front();q.pop();vis[ans]=0;
        for(int i=head[ans];i;i=d[i].nxt)
        {
            if(dis[d[i].to]>dis[ans]+d[i].w)
            {
                dis[d[i].to]=dis[ans]+d[i].w;
                if(!vis[d[i].to])//没在队列中
                {
                    vis[d[i].to]=1;
                    q.push(d[i].to);    
                } 
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int l,r,w;
        cin>>l>>r>>w;
        add(l,r,w);
    }
    spfa(s);
}