算法简介：
迪杰斯特拉算法是一种高效的处理非负边权的“单源最短路”问题的算法，即存在一个源点，让我们求出所有点到源点的最短距离，是图论中最重要的算法，需要注意的是，弗洛伊德算法可以看成由多个源点构成的迪杰斯特拉算法。堆优化版本的时间复杂度为O（nlogn）
准备工作:
1.int d[N];准备一个整型数组，d[i]表示点i距离源点的最短距离
2.准备一个bool型数组标记点是否走过（我们采用STL中的bitset）
3.准备一个优先队列作为堆
4.定义结点结构体，按照边权降序，在优先队列中边权最小的作为堆顶
基本思想：
1.算法的基本思想是贪心，即由于我们每次更新距离的时候都是和之前的路径比较过才将点入队的，所以同一个点不可能走两次，即第一次走得到的时候得到的距离一定是最短距离
2.数组要初始化为无穷，然后才能不断更新

struct Node {
	ll x, w;//x为结点编号，w表示源点到x的最短距离
	bool operator<(const Node& u)const
	{
		return w == u.w ? x < u.x:w>u.w;
	}
};

算法模板：

void dijkstra(int st)
{
	for (int i = 1; i <= n; i++)
		d[i] = inf;
	bitset<N>vis;
	priority_queue<Node>pq;
	pq.push({ st,d[st] = 0 });
	while (pq.size())
	{
		ll x = pq.top().x;
		ll w = pq.top().w;
		pq.pop();
		if (vis[x])continue;
		vis[x] = true;
		//拓展路径
		for (const auto& t : g[x])
		{
			ll y = t.x;
			ll dw = t.w;
			if (d[x] + dw < d[y])
			{
				d[y] = d[x] + dw;
				pq.push({ y,d[y]});
			}
		}
	}
}

例题示意：

这是一道模板题直接套用模板即可
代码示意：

#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
using ll = long long;
const ll N = 3e5 + 5, inf = 1e10;
using namespace std;
struct Node {
	ll x, w;
	bool operator<(const Node& u)const
	{
		return w == u.w ? x < u.x:w>u.w;
	}
};
vector<Node>g[N];
ll d[N];
int n, m;
void dijkstra(int st)
{
	for (int i = 1; i <= n; i++)
		d[i] = inf;
	bitset<N>vis;
	priority_queue<Node>pq;
	pq.push({ st,d[st] = 0 });
	while (pq.size())
	{
		ll x = pq.top().x;
		ll w = pq.top().w;
		pq.pop();
		if (vis[x])continue;
		vis[x] = true;
		//拓展路径
		for (const auto& t : g[x])
		{
			ll y = t.x;
			ll dw = t.w;
			if (d[x] + dw < d[y])
			{
				d[y] = d[x] + dw;
				pq.push({ y,d[y]});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio, cin.tie(0), cout.tie(0);
	cin >> n >> m;
	while (m--)
	{
		int x, y, w;
		cin >> x >> y >> w;
		g[x].push_back({ y,w });//读入单向边
	}
	dijkstra(1);
	for (int i = 1; i <= n; i++)
	{
		cout << (d[i] >= inf ? -1 : d[i]) << ' ';
	}
	return 0;
}

运行结果：