暴力—时间复杂度O(n^2)

int ne[N],h[N],idx,e[N],wt[N];//wt[]表示边权

void add(int u,int v,int w) //链式前向星存图
{
    idx++;
    e[idx]=v;
    wt[idx]=w; //边权
    ne[idx]=h[u];
    h[u]=idx;
}

int vis[N]; //vis[i]表示i点是否在s集合中
int d[N]; //d[i]表示 s->i 的最短路径

int p[N]; //p[i]表示i点是从哪个点过来的

void dijkstra(int s)
{
    for(int i=1;i<=n;i++)
    {
        d[i]=INF;
        //如果多次求d
        //要更新vis[]
        //要更新p[]
    }
    d[s]=0;
    //执行n次把点从t集合到s集合
    for(int i=1;i<=n;i++)
    {
        //1,找到最短路u
        int u;
        int minn=INF;
        for(int j=1;j<=n;j++)
        {
            //s集合与t集合的最短边
            if(d[j]<minn&&vis[j]==0)
            {
                u=j;
                //把最小值的下标给u
                minn=d[j];
                //把最小值给minn
            }
        }

        //2,把u移到s集合中
        vis[u]=1; //移到s集合中

        //3,在t集合中,跟u相邻的点进行松弛操作
        for(int j=h[u];j;j=ne[j])
        {
            int v=e[j];
            int w=wt[j];
            if(vis[v]==0&&d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                p[v]=u;//到达v的路径是从u来的
            }
        }
    }
}

优先队列—时间复杂度O(mlogm)

struct node 
{
    int to;
    int we;
};
vector<node >g[N];

bool vis[N];
int d[N];

//点u,d[u]

struct vnode
{
    int p;//点
    int d;//距离
    bool operator< (const vnode&b)  const//小顶堆——重载运算符
    {
        return d>b.d;
    }
};

void dijkstra(int s)
{
    priority_queue<vnode > q; 
    for(int i=1;i<=n;i++)
    {
        d[i]=INF;
    }
    d[s]=0;
    q.push({s,0});
    while(!q.empty())
    {
        int u=q.top().p;//找顶堆元素
        q.pop();
        if(vis[u])  //如果已经找到了，就不用再操作了
        {
            continue;
        }
        //如果在s集合中，就不用操作了，只有在t集合中，我们才拿进去，然后松弛
        vis[u]=1;
        for(auto e:g[u])
        {
            int v=e.to;
            int w=e.we;
            if(vis[v]==0&&d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                q.push({v,d[v]});
            }
        }
    }
}