题解 | #【模板】单源最短路1# Dijkstra

【模板】单源最短路1

https://www.nowcoder.com/practice/f24504c9ff544f7c808f76693cc34af8

#include <iostream>  
#include <vector>  
#include <queue>  
#include <cstring>  
using namespace std;  
  
const int MAXN = 5005;  
const int INF = 0x3f3f3f3f;  
  
struct Edge {  
    int to, cost;  
    Edge(int t, int c) : to(t), cost(c) {}  
};  
  
vector<Edge> graph[MAXN];  
int dist[MAXN];  
bool visited[MAXN];  
  
void dijkstra(int start) {  
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  
    pq.push(make_pair(0, start));  
    dist[start] = 0;  
  
    while (!pq.empty()) {  
        int u = pq.top().second;  
        pq.pop();  
  
        if (visited[u]) continue;  
        visited[u] = true;  
  
        for (auto &edge : graph[u]) {  
            int v = edge.to;  
            if (dist[v] > dist[u] + edge.cost) {  
                dist[v] = dist[u] + edge.cost;  
                pq.push(make_pair(dist[v], v));  
            }  
        }  
    }  
}  
  
int main() {  
    int n, m;  
    cin >> n >> m;  
  
    for (int i = 0; i < m; i++) {  
        int u, v;  
        cin >> u >> v;  
        graph[u].push_back(Edge(v, 1));  
        graph[v].push_back(Edge(u, 1));  
    }  
  
    memset(dist, INF, sizeof(dist));  
    memset(visited, false, sizeof(visited));  
  
    dijkstra(1);  
  
    if (dist[n] == INF) {  
        cout << "-1" << endl;  
    } else {  
        cout << dist[n] << endl;  
    }  
  
    return 0;  
}

这段代码实现了Dijkstra算法，用于计算带权有向图的最短路径。Dijkstra 算法是一种常用的单源最短路径算法，用于在加权有向图或无向图中查找从源节点到其他节点的最短路径。

首先，代码包含了一些头文件和命名空间声明。其中iostream用于输入输出流操作，vector用于定义向量容器，queue用于定义队列，cstring用于字符串操作，std命名空间表示使用标准库的函数和类。

接下来定义了一些常量和一个结构体Edge，用于表示有向边。结构体包含两个成员变量，to表示边的目标节点，cost表示边的权值。

然后定义了一个二维向量数组graph，用于存储图的结构。其中graph[i]表示节点i的出边列表。

接下来定义了一个一维数组dist，用于记录每个节点到起点的最短距离，初始值为正无穷大。

然后定义了一个一维布尔数组visited，用于标记每个节点是否已经被访问过，初始值为false。

接下来是dijkstra函数的实现。该函数使用Dijkstra算法计算起点到其他节点的最短距离。

在函数内部，首先创建了一个优先队列pq，用于存储节点和它们到起点的距离的配对。然后初始化队列，将起点入队，并将起点的距离设为0。

接下来进入循环，直到队列为空。在每次循环中，首先取出队列中的节点u，然后检查该节点是否已经被访问过，如果是，则跳过该节点。

然后对于节点u的每个出边，计算目标节点v的距离。如果v的距离的当前值大于起点到u再到v的距离的累加值，则更新v的距离的值为累加值，并将v入队。

循环结束后，dist数组中存储的就是起点到其他节点的最短距离。

最后在main函数中，首先读取输入的节点数和边数，然后通过循环读取每条边的起点和终点，并将边加入到图中。

接下来使用memset函数将dist和visited数组初始化为0或false。

然后调用dijkstra函数计算最短路径，其中起点为1。

最后根据计算结果输出结果，如果起点到终点的距离为正无穷大，则输出-1，否则输出距离值。

dijkstra(1) 是一个函数调用，它执行 Dijkstra 算法，并从节点 1 开始计算最短路径。在上面的代码中，dijkstra(1) 函数调用将执行 Dijkstra 算法，并从节点 1 开始计算最短路径。在算法的每个迭代中，它会选择当前距离起点最近的节点，并更新到该节点的最短路径。最终，它会计算从起点到所有其他节点的最短路径，并将结果存储在 dist 数组中。

0x3f3f3f3f 是一个经常用于表示无穷大的数值，在算法竞赛中常用来初始化距离数组为一个较大的值。它的十六进制表示为 0x3f3f3f3f，对应的十进制值为 1061109567。

这个特定的值被选择是因为它满足以下两个条件：