这是一个模板

题目见LG P4779 【模板】单源最短路径（标准版）。

还有一道简单版：LG P3371 【模板】单源最短路径（弱化版）（双倍经验！！！）。

弱化版DJ（只加链式前向星）和SPFA都能过，但是标准版会把SPFA卡掉（真恶心），而且DJ也要加链式前向星和堆优化。

这里我们只介绍DJ+链式前向星+堆优化（优先队列）的做法。

如果你想了解最短路的全部做法（除了Johnson），请拐弯至最短路。

想了解Johnson，请拐弯至Johnson。

不知道Dijkstra是什么的小伙伴请移步Dijkstra。

以下是DJ的最普通做法（其实已经足够应付普及组难度的题目了）：

void dijkstra()
{
    memset(dis,127/3,sizeof(dis));//初始化
    v[1]=1;
    dis[1]=0;
    for(int i=1;i<=n;++i)
    {
        int k=0;
        for(int j=1;j<=n;++j)//找出距离最近的点
            if(!v[j]&&(k==0||dis[j]<dis[k]))
                k=j;
        v[k]=1;//加入集合
        for(int j=1;j<=n;++j)//松弛
            if(!v[j]&&dis[k]+a[k][j]<dis[j])
                dis[j]=dis[k]+a[k][j];
    }
}//传载于最短路

由以上代码可知，改算法的时间复杂度为O（n²），但这在n较大的情况下仍无法拿到满分，接下来我们看看怎么优化吧：

①因为我们要找出距离最近的点，因为每次都要找一遍距离最近的点，所以我们可以用堆优化，但其过程有些繁琐，这时我们可以使用优先队列代替（STL大法好）。

②我们在松弛的过程中，将每条边都查询了一遍，然而我们其实只需要查询与距离最近的点相连的点即可。这时，我们便需要引用一个新的存储边的方法——链式前向星（概念和在本题中的用法）

完整AC代码：

#include<cstdio>
#include<cstring>
#include<queue>//不想打万能头 
using namespace std;
const int N=2e5+5;//数据范围 
struct edge{//存储边 
    int u,v,w,next;//u为起点，v为终点，w为权值，next为前继 
};
edge e[N];
int head[N],dis[N],n,m,s,cnt;//head为链中最上面的，dis表示当前答案，n为点数，m为边数，s为起点，cnt记录当前边的数量 
bool vis[N];//vis表示这个点有没有走过 
struct node{
    int w,to;//w表示累加的权值，to表示到的地方 
    bool operator <(const node &x)const{//重载“<”号 
        return w>x.w;
    }
};
priority_queue<node>q;//优先队列（堆优化） 
void add(int u,int v,int w){
    ++cnt;//增加边的数量 
    e[cnt].u=u;//存起点 
    e[cnt].v=v;//存终点 
    e[cnt].w=w;//存权值 
    e[cnt].next=head[u];//存前继 
    head[u]=cnt;//更新链最上面的序号 
}//链式前向星（加边） 
void Dijkstra(){
    memset(dis,127,sizeof(dis));//初始化，为dis数组附一个极大值，方便后面的计算 
    dis[s]=0;//起点到自己距离为0 
    q.push(node{0,s});//压入队列 
    while(!q.empty()){//队列不为空 
        node x=q.top();//取出队列第一个元素 
        q.pop();//弹出 
        int u=x.to;//求出起点 
        if(vis[u]) continue;//已去过就不去了 
        vis[u]=true;//标记已去过 
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].v;//枚举终点 
            if(dis[v]>dis[u]+e[i].w){//若中转后更优，就转 
                dis[v]=dis[u]+e[i].w;//更新 
                q.push(node{dis[v],v});//压入队列
            }
        }
    }
}
int main(){
    int u,v,w;
    scanf("%d%d%d",&n,&m,&s);//输入 
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        //add(v,u,w);如果是双向边再加上这句 
    }
    Dijkstra();//DJ 
    for(int i=1;i<=n;++i)//输出 
        printf("%d ",dis[i]);
    return 0;
}

 谢谢大家的观看，如有疑问或意见欢迎在评论区指出！！！