最短路模板（Floyd && Dijkstra优化 && Bellman-Ford && spfa优化）

1.Floyd

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+50;
const int inf=0x3f3f3f3f;
int g[N][N],n,m;
void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
         ///必要时剪枝
         ///if(g[i][k]<inf)
            for(int j=1;j<=n;j++)
                g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
        }
    }
}
int main()
{
    int a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                g[i][j]=inf;
        }
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(c<g[a][b])
                g[a][b]=g[b][a]=c;
        }
        floyd();
        cout<<g[1][n]<<'\n';
    }
    return 0;
}

(/▽＼) 新加~floyd对无向图的优化 https://blog.csdn.net/lanshuizhiyun/article/details/77864648

2.Dijkstra

<1>朴素版

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+50;
const int inf=0x3f3f3f3f;
int g[N][N],dis[N],vis[N];
int n,m;
void dijk()
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        dis[i]=g[1][i];
    vis[1]=1;
    dis[1]=0;
    for(int i=1;i<=n;i++)
    {
        int pos,minn=inf;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&minn>dis[j])
            {
                pos=j;
                minn=dis[j];
            }
        }
        vis[pos]=1;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]>dis[pos]+g[pos][j])
                dis[j]=dis[pos]+g[pos][j];
        }
    }
}
int main()
{
    int a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                g[i][j]=inf;
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(c<g[a][b])
                g[a][b]=g[b][a]=c;
        }
        dijk();
        cout<<dis[n]<<'\n';
    }
    return 0;
}

<2>dijkstra+堆优化（邻接矩阵存图）

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e4+10;
int n,m;

struct qnode
{
    int v;
    int c;
    qnode(int _v=0,int _c=0):v(_v),c(_c){}
    bool operator <(const qnode &r)const
    {
        return c>r.c;
    }
};

struct Edge
{
    int v,cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};

vector<Edge>E[N];
bool vis[N];
int dis[N];

void dijk(int n,int start)
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    priority_queue<qnode>q;
    while(!q.empty())
        q.pop();
    dis[start]=0;
    q.push(qnode(start,0));
    qnode tmp;
    while(!q.empty())
    {
        tmp=q.top();
        q.pop();
        int u=tmp.v;
        if(vis[u])
            continue;
        vis[u]=true;
        for(int i=0;i<E[u].size();i++)
        {
            int v=E[tmp.v][i].v;
            int cost=E[u][i].cost;
            if(!vis[v]&&dis[v]>dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
                q.push(qnode(v,dis[v]));
            }
        }
    }
}

void addadge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
}

void init()
{
    for(int i=0;i<N;i++)
        E[i].clear();
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&n+m)
    {
        init();
        int u,v,w;
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&w);
            addadge(u,v,w);///注意无向图加两条边
            addadge(v,u,w);
        }
        dijk(n,1);
        cout<<dis[n]<<'\n';
    }
    return 0;
}

<3>dijkstra+堆优化（链式前向星存图）

大佬的链式前向星详解

#include <bits/stdc++.h>    ///dijk+堆优化（链式前向星）
using namespace std;
const int N = 1e4 + 7;
const int inf = 0x3f3f3f3f;

int head[N];
bool vis[N];
int dis[N];
int n, m, tot;

struct Node
{
    int u, v, l, next;     ///起点 终点 长度 与该边同起点的上一条边的储存位置
}edge[N];

struct A
{
    int pos, cost;
    bool operator < (const A &a)const
    {
        return cost > a.cost;
    }
};

void addedge(int x, int y, int z)
{
    edge[tot].u = x;
    edge[tot].v = y;
    edge[tot].l = z;
    edge[tot].next = head[x];
    head[x] = tot++;
}

int dijk(int src, int des)
{
    memset(dis, inf, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    priority_queue<A>q;
    dis[src] = 0;
    A now;
    now.cost = 0;
    now.pos = src;
    q.push(now);
    while(!q.empty())
    {
        now = q.top();
        q.pop();
        if(vis[now.pos])
            continue;
        vis[now.pos] = 1;
        for(int i = head[now.pos]; ~i; i = edge[i].next)    //遍历以该点为顶点的所有边
        {
            int to = edge[i].v;    //to = 这条边的终点
            if(!vis[to] && dis[to] > edge[i].l + dis[edge[i].u])    //to没有更新过且目前源点到to的距离 > 该边的长度 + 源点到该边起点的距离
            {
                dis[to] = dis[edge[i].u] + edge[i].l;    //更新
                now.cost = dis[to];
                now.pos = to;
                q.push(now);
            }
        }
    }
    return dis[des];
}

int main()
{
    int u, v, w;
    while(scanf("%d%d", &n, &m) != EOF && n + m)
    {
        tot = 0;
        memset(head, -1, sizeof(head));
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        int ans = dijk(1, n);
        cout<<ans<<'\n';
    }
    return 0;
}

<4>dijkstra+堆优化（pair存储）

3.Bellman-ford

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int dis[N];
int n,m;

struct Edge
{
    int u,v,w;
}edge[N];

bool Bellman_Ford()
{
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    dis[1]=0;
    for(int k=1;k<=n-1;k++)
    {
        bool flag=0;
        for(int i=1;i<=2*m;i++)
        {
            if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
            {
                dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
                flag=1;
            }
        }
        if(!flag)
            return true;
    }
    for(int j=1;j<=2*m;j++)
        if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w)
            return false;///判负环
    return true;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&n+m)
    {
        int cnt=1;
        int a,b,c;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            edge[cnt].u=edge[cnt+1].v=a;
            edge[cnt].v=edge[cnt+1].u=b;
            edge[cnt].w=edge[cnt+1].w=c;
            cnt+=2;
        }
        if(Bellman_Ford())
            cout<<dis[n]<<'\n';
        else
            cout<<-1<<'\n';
    }
    return 0;
}

4.spfa

<1>朴素版（链式前向星）

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int dis[N],vis[N],head[N],num[N];
int n,m,tot;

struct Edge
{
    int u,v,w,next;
}edge[N];

void add(int a,int b,int c)
{
    edge[tot].u=a;
    edge[tot].v=b;
    edge[tot].w=c;
    edge[tot].next=head[a];
    head[a]=tot++;
}

bool spfa(int s)
{
    queue<int>q;
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    memset(vis,false,sizeof(vis));
    memset(num,0,sizeof(num));
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int pos=q.front();
        q.pop();
        vis[pos]=false;
        num[pos]++;
        for(int i=head[pos];i!=-1;i=edge[i].next)
        {
            if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
            {
                dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
                if(!vis[edge[i].v])
                {
                    vis[edge[i].v]=true;
                    q.push(edge[i].v);
                    if(num[edge[i].v]>=n)
                        return false;
                }
            }
        }
    }
    return true;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&n+m)
    {
        int a,b,c;
        tot=0;
        memset(head,-1,sizeof(head));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        if(!spfa(1))
            cout<<-1<<'\n';
        else
            cout<<dis[n]<<'\n';
    }
    return 0;
}

<2>SLF优化（链式前向星）

#include <bits/stdc++.h>///spfa   SLF优化
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int dis[N],head[N];
bool vis[N];
int n,m,tot;

struct Edge
{
    int u,v,w,next;
}edge[N];

void add(int a,int b,int c)
{
    edge[tot].u=a;
    edge[tot].v=b;
    edge[tot].w=c;
    edge[tot].next=head[a];
    head[a]=tot++;
}

void spfa(int s)
{
    deque<int>q;
    memset(dis,inf,sizeof(dis));
    memset(vis,false,sizeof(vis));
    vis[s]=true;
    dis[s]=0;
    q.push_back(s);
    while(!q.empty())
    {
        int from=q.front();
        q.pop_front();
        vis[from]=false;
        for(int i=head[from];i!=-1;i=edge[i].next)
        {
            int to=edge[i].v;
            if(dis[to]>dis[from]+edge[i].w)
            {
                dis[to]=dis[from]+edge[i].w;
                if(!vis[to])
                {
                    if(!q.empty()&&dis[to]>=dis[q.front()])///注意
                        q.push_back(to);
                    else
                        q.push_front(to);
                    vis[to]=true;
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&n+m)
    {
        int a,b,c;
        tot=0;
        memset(head,-1,sizeof(head));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        spfa(1);
        cout<<dis[n]<<'\n';
    }
    return 0;
}

<3>SLF+LLL优化（链式前向星）

#include <bits/stdc++.h>///spfa   SLF+LLL优化
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int dis[N],head[N];
bool vis[N];
int n,m,tot;

struct Edge
{
    int u,v,w,next;
}edge[N];

void add(int a,int b,int c)
{
    edge[tot].u=a;
    edge[tot].v=b;
    edge[tot].w=c;
    edge[tot].next=head[a];
    head[a]=tot++;
}

void spfa(int s)
{
    int num=0;
    long long sum=0;
    deque<int>q;
    memset(dis,inf,sizeof(dis));
    memset(vis,false,sizeof(vis));
    vis[s]=true;
    dis[s]=0;
    q.push_back(s);
    num++;
    while(!q.empty())
    {
        int from=q.front();
        q.pop_front();
        num--;
        sum-=dis[from];
        while(num&&dis[from]>sum/num)
        {
            q.push_back(from);
            from=q.front();
            q.pop_front();
        }
        vis[from]=false;
        for(int i=head[from];i!=-1;i=edge[i].next)
        {
            int to=edge[i].v;
            if(dis[to]>dis[from]+edge[i].w)
            {
                dis[to]=dis[from]+edge[i].w;
                if(!vis[to])
                {
                    if(!q.empty()&&dis[to]<dis[q.front()])
                        q.push_front(to);
                    else
                        q.push_back(to);
                    vis[to]=true;
                    num++;
                    sum+=dis[to];
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&n+m)
    {
        int a,b,c;
        tot=0;
        memset(head,-1,sizeof(head));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        spfa(1);
        cout<<dis[n]<<'\n';
    }
    return 0;
}