回顾一下最短路径的算法：

• 所有顶点间的最短路径算法 --- Floyd
• 单源最短路径算法 --- Dijkstra
• 判断负权回路最短路径算法 --- Bellman-Ford
• 带负权边最短路径算法 --- SPFA

最短路径：在带权有向图中 $A$ 点（源点）到 $B$ 点（终点）的多条路径中，寻找一条各边权值最小的路径，即最短路径。

可以用 Dijkstra 算法解决单源最短路径问题。

基本思想：

将图中所有顶点分成两组：已知确定最短路 $S$、尚未确定最短路 $V-S$不断从第 $2$ 组中选择路径长度最短的点放入第 $1$ 组并扩展。

若顶点序列 ${V_0,V_1,......,V_n}$ 是从 $V_0$ 到 $V_n$ 的最短路，则序列 ${V_0,V_1,......,V_{n-1}}$ 必为从 $V_0$ 到 $V_{n-1}$ 的最短路。

其本质为：贪心算法，且只能用于正权图。

可以用优先队列 $priority\_queue$ 和邻接表来优化。

注意：本题要开 $long\ long$。

#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef long long ll;
const int N = 5e5 + 10;
int h[N], vtx[2 * N], nxt[2 * N], wt[2 * N], idx;
int dis[N], pre[N], vis[N];
int n, m, s, tu, tv, tw;

struct node {
	int u, v, w;
	friend bool operator < (node a, node b) {
		if (a.w >= b.w) {
			return 1;
		} else {
			return 0;
		}
	}
};
priority_queue<node> q;

void addEdge(int a, int b, int c) {
	vtx[idx] = b;
	nxt[idx] = h[a];
	wt[idx] = c;
	h[a] = idx++;
}

void dijkstra(int s) {
	dis[s] = 0;
	node tmp;
	tmp.u = s;
	tmp.v = s;
	tmp.w = 0;
	q.push(tmp);
	while (!q.empty()) {
		tmp = q.top();
		q.pop();
		int nid = tmp.v;
		if (vis[nid] == 1) {
			continue;
		}
		vis[nid] = 1;
		int p = h[nid];
		while (p != -1) {
			if (vis[vtx[p]] == 0) {
				if (dis[nid] + wt[p] < dis[vtx[p]]) {
					dis[vtx[p]] = dis[nid] + wt[p];
					pre[vtx[p]] = nid;
					tmp.u = nid;
					tmp.v = vtx[p];
					tmp.w = dis[vtx[p]];
					q.push(tmp);
				}
			}
			p = nxt[p];
		}
	}
}
signed main() {
	memset(h, -1, sizeof(h));
	cin >> n >> m >> s;
	for (int i = 1; i <= n; i++) {
		dis[i] = 3e18;
	}
	while (m--) {
		cin >> tu >> tv >> tw;
		if (tu != tv) {
			addEdge(tu, tv, tw);
		}
	}
	dijkstra(s);
	for (int i = 1; i <= n; i++) {
		if (s == i) {
			cout << 0 << " "; 
		} else {
			cout << dis[i] << " ";
		}
	}
	return 0;
}

#include<bits/stdc++.h>
#define MaxN 100010
#define MaxM 500010
#define ll long long
#define inf 114514191981019260817
using namespace std;
struct edge
{
    ll to, dis, next;
};
edge e[MaxM];
ll head[MaxN], dis[MaxN], cnt;
bool vis[MaxN];
ll n, m, s;
inline void add_edge( int u, int v, int d )
{
    cnt++;
    e[cnt].dis = d;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
struct node
{
    ll dis;
    ll pos;
    bool operator <( const node &x )const
    {
        return x.dis < dis;
    }
};
priority_queue < node > q;
inline void dijkstra()
{
    dis[s] = 0;
    q.push( ( node ){0, s} );
    while( !q.empty() )
    {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if( vis[x] )
            continue;
        vis[x] = 1;
        for(ll i = head[x]; i; i = e[i].next)
        {
            ll y = e[i].to;
            if( dis[y] > dis[x] + e[i].dis )
            {
                dis[y] = dis[x] + e[i].dis;
                if( !vis[y] )
                {
                    q.push( ( node ){dis[y], y} );
                }
            }
        }
    }
}
int main()
{
    scanf( "%lld%lld%lld", &n, &m, &s );
    for(int i = 1; i <= n; ++i) dis[i] = inf;
    for(ll i = 0; i < m; ++i )
    {
        ll u, v, d;
        scanf( "%lld%lld%lld", &u, &v, &d );
        add_edge( u, v, d );
    }
    dijkstra();
    for( int i = 1; i <= n; i++ )
        printf( "%lld ", dis[i] );
    return 0;
}

友情提示： 该题须开long long，且对设置的INF有较大要求，须开到极大

#include<bits/stdc++.h>
#define MaxN 100010
#define MaxM 500010
#define ll long long
#define inf 114514191981019260817
using namespace std;
struct edge
{
    ll to, dis, next;
};
edge e[MaxM];
ll head[MaxN], dis[MaxN], cnt;
bool vis[MaxN];
ll n, m, s;
inline void add_edge( int u, int v, int d )
{
    cnt++;
    e[cnt].dis = d;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
struct node
{
    ll dis;
    ll pos;
    bool operator <( const node &x )const
    {
        return x.dis < dis;
    }
};
priority_queue < node > q;
inline void dijkstra()
{
    dis[s] = 0;
    q.push( ( node ){0, s} );
    while( !q.empty() )
    {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if( vis[x] )
            continue;
        vis[x] = 1;
        for(ll i = head[x]; i; i = e[i].next)
        {
            ll y = e[i].to;
            if( dis[y] > dis[x] + e[i].dis )
            {
                dis[y] = dis[x] + e[i].dis;
                if( !vis[y] )
                {
                    q.push( ( node ){dis[y], y} );
                }
            }
        }
    }
}
int main()
{
    scanf( "%lld%lld%lld", &n, &m, &s );
    for(int i = 1; i <= n; ++i) dis[i] = inf;
    for(ll i = 0; i < m; ++i )
    {
        ll u, v, d;
        scanf( "%lld%lld%lld", &u, &v, &d );
        add_edge( u, v, d );
    }
    dijkstra();
    for( int i = 1; i <= n; i++ )
        printf( "%lld ", dis[i] );
    return 0;
}