dijkstra最短路算法（堆优化）

这个算法不能处理负环情况，请转到Floyd算法或SPFA算法（SPFA不能处理负环，但能判断负环）

SPFA(SLF优化)：https://www.cnblogs.com/yifan0305/p/16391419.html

代码很长，耐下心来看完，存储方法为链式前向星存储。

(如果内存放得下的话，建议稠密图用邻接矩阵(或者跑floyd)，稀疏图用邻接表,只是建议)

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;//cnt 计数器 有cnt条边（从1开始存） 
struct edge
{
    int u,v,w,nxt;
    /*u 起点 （不需要的话可以删掉） 
      v 目标点 w 边权 
      nxt 指向这条边的上一条边的标号（上一条边是从同一起点发出的边，不要搞混了） */
};
edge e[20020];
int h[2010];//存储第x个点发出的最后一条边的编号 
struct nod//存储点 
{
    int s,w;//s 这个点的标号 w 起点到这个点的最短路径值 
};
struct cmp//结构体的比较函数（优先队列要用，看不懂去搜一下，毕竟这里不是它的主场） 
{
    bool operator()(nod a,nod b)
    {
        return a.w<b.w;
    }
};
nod dis[2010];//存点（毕竟不好处理点的标号和最短路径值相匹配，如果你有更好的方法，忽略这种存法） 
bool f[2010];// 标记点是否被染色（看不懂染色的往下看。。。懒得再敲一遍了） 
priority_queue<nod,vector<nod>,cmp> q;//定义一个优先队列（存点） 
void add(int,int,int);
void dij()//堆优化 
{
    for(int i=1;i<=n;++i)//初始化 
    {
        dis[i].s=i;//将编号输入 
        dis[i].w=0x3f3f3f;//将值设为一个很大的值，理由是便于后续使用（废话） 
    }
    dis[1].w=0;//起点到起点的距离是0（该题起点为1，根据题目来） 
    q.push(dis[1]);//该点入队 
    while(!q.empty())
    {
        nod top=q.top();//取出队首元素 
        int u=top.s,w=top.w;//u 该点的编号 w 起点到点u的最短路径值 
        f[u]=1;//标记已经被染过色了
        //（染色不懂，就理解为这个点已经用过了，标记一下，不能再用了，跟搜索回溯的原理差不多） 
        q.pop();//出队 
        for(int i=h[u];i;i=e[i].nxt)//邻接表遍历 
        {
            int v=e[i].v;//v 目标点 
            if(dis[v].w>w+e[i].w)//松弛操作 
            {
                dis[v].w=w+e[i].w;//更新起点到点v的最短路径值 
                q.push(dis[v]);//入队 
            }
            if(f[v])    continue;//如果已被染色（看不懂按上面的理解），跳过
            //这里松弛和染色不会冲突，松弛操作是更新最优值，染色是为了防止后面扫到该点的非优值(2022.5.15修改)
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);//输入，根据题目来 
    for(int a,b,c,i=1;i<=m;++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);//加边 
        add(b,a,c);//加边，如果是有向图，忽略这一步操作 
    }
    dij();//调用函数 
    if(dis[n].w>=0x3f3f3f-1)    printf("-1");
    //这里是输出操作，如果起点到点n的值大于0x3f3f3f-1，就说明压根就没更新到，也说明起点和点n不连接
    //（题目要求，根据题目来） 
    else    printf("%d",dis[n].w);
    return 0;
}
void add(int u,int v,int w)//加边操作 
{
    e[++cnt].v=v;//记录该条边的目标点 
    e[cnt].w=w;//记录边权 
    e[cnt].nxt=h[u];//记录上一条边 
    h[u]=cnt;//更新从点u发出的最后一条边的边号 
}

重载运算符版本

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,g;//cnt 计数器 有cnt条边（从1开始存）s起点 
struct edge
{
    int u,v,w,nxt;
    /*u 起点 （不需要的话可以删掉） 
      v 目标点 w 边权 
      nxt 指向这条边的上一条边的标号（上一条边是从同一起点发出的边，不要搞混了） */
};
edge e[20020];
int h[2010];//存储第x个点发出的最后一条边的编号 
struct nod//存储点 
{
    int s,w;//s 这个点的标号 w 起点到这个点的最短路径值 
    bool operator < (const nod &a) const
    {
        return w>a.w;
    }//运算符重载 
};
nod dis[2010];//存点（毕竟不好处理点的标号和最短路径值相匹配，如果你有更好的方法，忽略这种存法） 
bool f[2010];// 标记点是否被染色 
priority_queue<nod> q;//定义一个优先队列（存点） 
void add(int,int,int);
void dij()//堆优化 
{
    memset(f,0,sizeof f);//初始化数组 
    for(int i=1;i<=n;++i)//初始化 
    {
        dis[i].s=i;//将编号输入 
        dis[i].w=0x3f3f3f;//将值设为一个很大的值 
    }
    dis[g].w=0;//起点到起点的距离是0 
    q.push(dis[g]);//该点入队 
    while(!q.empty())
    {
        nod top=q.top();//取出队首元素 
        int u=top.s,w=top.w;//u 该点的编号 w 起点到点u的最短路径值 
        q.pop();//出队
        if(f[u])    continue;//如果该点已经染过色了，跳过 
        f[u]=1;//染色  
        for(int i=h[u];i;i=e[i].nxt)//邻接表遍历 
        {
            int v=e[i].v;//v 目标点 
            if(!f[v]&&dis[v].w>w+e[i].w)//松弛操作 
            {
                dis[v].w=w+e[i].w;//更新起点到点v的最短路径值 
                q.push(dis[v]);//入队 
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&g);//输入，根据题目来 
    for(int a,b,c,i=1;i<=m;++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);//加边 
        add(b,a,c);//加边，如果是有向图，忽略这一步操作 
    }
    dij();//调用函数 
    if(dis[n].w>=0x3f3f3f-1)    printf("-1");
    //这里是输出操作，如果起点到点n的值大于0x3f3f3f-1，就说明压根就没更新到，也说明起点和点n不连接 
    else    printf("%d",dis[n].w);
    return 0;
}
void add(int u,int v,int w)//加边操作 
{
    e[++cnt].v=v;//记录该条边的目标点 
    e[cnt].w=w;//记录边权 
    e[cnt].nxt=h[u];//记录上一条边 
    h[u]=cnt;//更新从点u发出的最后一条边的边号 
}