首先，我们概括一下大致思想（转载于Korpse——最短路径：Dijkstra算法）

注：Dijkstra算法适用于边权为正的无向和有向图，不适用于有负边权的图！（原因）

用途：
    用于求图中指定两点之间的最短路径，或者是指定一点到其它所有点之间的最短路径。实质上是贪心算法。

基本思想：
    1.将图上的初始点看作一个集合S，其它点看作另一个集合

    2.根据初始点，求出其它点到初始点的距离d[i] （若相邻，则d[i]为边权值；若不相邻，则d[i]为无限大）

    3.选取最小的d[i]（记为d[x]），并将此d[i]边对应的点（记为x）加入集合S

    （实际上，加入集合的这个点的d[x]值就是它到初始点的最短距离）

    4.再根据x，更新跟 x 相邻点 y 的d[y]值：d[y] = min{ d[y], d[x] + 边权值w[x][y] }，因为可能把距离调小，所以这个更新操作叫做松弛操作。

    （仔细想想，为啥只更新跟x相邻点的d[y]，而不是更新所有跟集合 s 相邻点的 d 值？ 因为第三步只更新并确定了x点到初始点的最短距离，集合内其它点是之前加入的，也经历过第 4 步，所以与 x 没有相邻的点的 d 值是已经更新过的了，不会受到影响）

    5.重复3，4两步，直到目标点也加入了集合，此时目标点所对应的d[i]即为最短路径长度。

    （注：重复第三步的时候，应该从所有的d[i]中寻找最小值，而不是只从与x点相邻的点中寻找。想想为什么？）

    图解：（动图很快，不容易理解，最好结合上面的步骤自己画一个图，一步一步消化）

    原理：这里不进行严格证明，Dijkstra的大致思想就是，根据初始点，挨个的把离初始点最近的点一个一个找到并加入集合，集合中所有的点的d[i]都是该点到初始点最短路径长度，由于后加入的点是根据集合S中的点为基础拓展的，所以也能找到最短路径。
原文链接：https://blog.csdn.net/kprogram/java/article/details/81225176

模板题：https://www.luogu.com.cn/problem/P4779

 下面对little_sun的题解进行解释

#include<bits/stdc++.h>//万能头不解释 

const int MaxN = 100010, MaxM = 500010;//表示不可改变数值的int常量。 

struct edge
{
    int to, dis, next;
    //to是此边的子节点
    //dis是此边的权值 
    //next是与此边父节点相同的最近的边(的编号)
    //即为上一条从此边的父节点引出的边(的编号) 
};

edge e[MaxM];
int head[MaxN], dis[MaxN], cnt;
//head数组指：以某点为父节点引出的最新一条边(的编号) 
bool vis[MaxN];
int n, m, s;

inline void add_edge( int u, int v, int d )
{
    cnt++;//新增一条边，编号要+1 
    e[cnt].dis = d;
    e[cnt].to = v;//这条边通向节点v，所以v是此边的一个子节点 
    e[cnt].next = head[u];
    //由于该边是新增的一条边，且父节点是u
    //那么上一条从u引出的边(的编号，即head[u])就是新增的这条边的next值 
    head[u] = cnt;
    //新增的这条边是从u引出的 ，那么这条边(的编号)自然是u的最新一条边 
}

struct node
{
    int dis;//距离 
    int pos;//表示从起点到达的点 
    bool operator <( const node &x )const
    {
        return x.dis < dis;
    }
    //重载运算符，对node类型的变量以dis为依据排序
    //这里重载的小于号 
};

std::priority_queue<node> q;
//定义优先队列(堆优化，类型是node类型) 

inline void dijkstra()
{
    dis[s] = 0;//s是起点 
    //定义从起点到点s的距离是0 
    q.push( ( node ){0, s} );
    //强制类型转换，定义node中的dis=0，pos=s
    //即定义，这一条边从起点到点s，距离是0 
    while( !q.empty() )//如果堆不空 
    {
        node tmp = q.top();//设置一个node型变量表示堆顶元素 
        q.pop();//因为已经用tmp存了，可以直接将堆顶元素删掉 
        int x = tmp.pos, d = tmp.dis;
        //x表示此边的来源(父节点)，d表示距离(权值) 
        if( vis[x] )
            continue;
        //如果vis[x]被访问过，直接continue 
        vis[x] = 1;//如果没被访问过，标记为已访问 
        for( int i = head[x]; i; i = e[i].next )
        {
            //i从父节点为x的最新(后)一条边开始遍历
            //每次都等于与此边有相同父节点的上一条边，直到没有
            //e[i].next就是与正在进行遍历的这条边有相同的父节点的上一条边
            //例如节点5先后有1,2,3三条边，那么就从3开始，遍历3,2,1
            int y = e[i].to;
            //定义y是这条边通向的节点 
            if( dis[y] > dis[x] + e[i].dis )
            {
                //e[i].dis就是从节点x到节点y的各边的权值
                //因为在这个循环内我们定义的i就是从x引出的边 
                dis[y] = dis[x] + e[i].dis;
                //更新从起点到点y的最小值 
                if( !vis[y] )
                {
                    //如果节点y没被访问过 
                    q.push( ( node ){dis[y], y} );
                    //定义从起点到节点y的距离是dis[y] 
                }
            }
        }
    }
}

int main()
{
    scanf( "%d%d%d", &n, &m, &s );
    //给定一个n个点，m条有向边的带非负权图，请计算从s出发，到每个点的距离 
    for(int i = 1; i <= n; ++i)dis[i] = 0x7fffffff;
    //先把所有边的权值设为无穷大(在这里设为2147483647) 
    for( register int i = 0; i < m; ++i )
    {
        register int u, v, d;
        //表示从u到v有一条权值为d的有向边 
        scanf( "%d%d%d", &u, &v, &d );
        add_edge( u, v, d );
        //新增这条边，并存入e数组 
    }
    dijkstra();
    //调用函数寻找起点到每点的最小值 
    for( int i = 1; i <= n; i++ )
        printf( "%d ", dis[i] );
    //输出 
    return 0;
}