【单源最短路径1】题解

题干信息解读
给定一个可能存在重边的有向图，要求计算从指定起点出发，到图中所有其他节点的最短路径长度。若无法到达某个节点，则该节点的最短路径长度输出为 - 1。

整体做题思路
本题采用 Dijkstra 算法求解单源最短路径问题。由于节点数 n 最大可达 1e6，边数 m 最大可达 2e6，需使用优先队列（小顶堆）优化 Dijkstra 算法，确保时间复杂度为 O ((m+n) logn)。具体步骤如下：

1.建图：使用邻接表存储图结构，允许重边存在。
2.初始化：将起点的距离设为 0，其余节点的距离设为无穷大。
3.优先队列优化：使用优先队列维护待处理的节点，每次取出距离最小的节点进行扩展。
4.松弛操作：遍历当前节点的所有出边，更新邻接节点的距离值，并将更新后的节点加入队列。
5.标记处理：使用标记数组记录已确定最短路径的节点，避免重复处理。

题目中的难点和注意事项
1.数据规模处理：节点数和边数较大，需使用邻接表和优先队列优化算法。
2.优先队列优化：使用小顶堆维护节点距离，确保每次取出的节点距离最小。
3.重边处理：Dijkstra 算法会自动选择最短的边，因此无需特殊处理重边。
4.不可达节点处理：遍历结束后，未被访问的节点即为不可达节点，输出 - 1。

AC代码（如有雷同，纯属巧合）（改编自@carrotchicken）

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int,int>>G[2000005]; // 邻接表存储图，G[u]存储从u出发的所有边{v, w}
int n,m,s;                        // n:节点数，m:边数，s:起点
int d[2000006];                   // 存储起点到各节点的最短路径长度
bool vis[2000006];                // 标记节点是否已确定最短路径
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q; // 小顶堆，按距离从小到大排序
signed main()
{	
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)         // 读入边信息
	{
		int u,v,x;
		cin>>u>>v>>x;
		G[u].push_back({v,x});    // 添加边到邻接表
	}
	memset(d,0x3f,sizeof d);      // 初始化距离数组为无穷大
	d[s]=0;                       // 起点到自身的距离为0
	q.push({0,s});                // 将起点加入优先队列
	while(!q.empty())             // 队列非空时循环
	{
		int now=q.top().second;   // 取出当前距离最小的节点
        q.pop();
		if(vis[now])continue;     // 跳过已处理的节点
		vis[now]=true;            // 标记当前节点已确定最短路径
		for(int i=0;i<G[now].size();i++) // 遍历当前节点的所有出边
		{
			auto&[nxt,val]=G[now][i];  // 获取邻接节点和边权
			if(d[now]+val<d[nxt])      // 如果通过当前节点到达邻接节点的路径更短
			{
				d[nxt]=d[now]+val;     // 更新邻接节点的距离
				q.push({d[nxt],nxt});  // 将更新后的邻接节点加入队列
			}
		}
	}
	for(int i=1;i<=n;i++)         // 输出结果
	{
        if(!vis[i])               // 如果节点不可达
        {
            cout<<"-1 ";
            continue;
        }
		cout<<d[i]<<" ";          // 输出最短路径长度
	}
	return 0;
}

时间复杂度和空间复杂度
时间复杂度：O ((m+n) log n)，其中 n 为节点数，m 为边数。每次从优先队列中取出节点的时间复杂度为 O (log n)，每条边被遍历一次。
空间复杂度：O (n+m)，主要用于存储邻接表和优先队列。

算法解释
这段代码使用了优先队列优化的 Dijkstra 算法来求解单源最短路径问题。算法的核心思想是贪心策略，每次从队列中取出距离最小的节点进行扩展，确保每个节点的最短路径被最早确定。通过标记数组 vis 避免重复处理节点，提高了算法效率。对于不可达节点，由于其距离值始终为初始的无穷大且未被访问，因此输出 - 1。