个人网站建站_晋江文学_自己接单的平台_丹东网站seo

文章目录

1. 题目描述
2. 实现
3. 该问题的详细分析
- 3.1 整体结构与功能
- 3.2 函数定义及参数解释
- 3.3 代码执行过程分析
- 3.4主函数部分分析
4. 时间复杂度分析

1. 题目描述

在这里插入图片描述

2. 实现

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>using namespace std;int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<pair<int, int>>> graph(n);for (const auto& time : times) {graph[time[0] - 1].push_back({time[1] - 1, time[2]});}vector<int> dist(n, INT_MAX);dist[k - 1] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;pq.push({0, k - 1});while (!pq.empty()) {int u = pq.top().second;pq.pop();for (const auto& neighbor : graph[u]) {int v = neighbor.first;int weight = neighbor.second;if (dist[u]!= INT_MAX && dist[u] + weight < dist[v]) {dist[v] = dist[u] + weight;pq.push({dist[v], v});}}}int maxTime = 0;for (int time : dist) {if (time == INT_MAX) return -1;maxTime = max(maxTime, time);}return maxTime;
}

3. 该问题的详细分析

3.1 整体结构与功能

这段 C++ 代码的目的是计算在一个局域网中，从一台初始被病毒感染的电脑开始，感染整个网络所需的最少时间。如果存在无法被感染的电脑，则返回 -1。

3.2 函数定义及参数解释

int networkDelayTime(vector<vector>& times, int n, int k)：

times是一个二维向量，存储了局域网中电脑之间的连接信息，每一个子向量 {i, j, t} 表示电脑 i 感染电脑 j 需要时间 t。
n表示局域网中电脑的总数。
k表示初始被病毒感染的电脑编号。
函数返回值是感染整个网络所需的最少时间，如果有电脑无法被感染则返回 -1。

3.3 代码执行过程分析

构建图的邻接表表示：

vector<vector<pair<int, int>>> graph(n); 创建一个大小为 n 的二维向量 graph，用于存储图的邻接表表示。
for (const auto& time : times) 遍历输入的连接信息向量 times。
graph[time[0] - 1].push_back({time[1] - 1, time[2]}) 将每条连接信息转换为邻接表的形式存储在 graph 中。例如，对于 {i, j, t}，将电脑 i - 1 到电脑 j - 1 的连接以及时间 t 存储在 graph[i - 1] 中，这里的 i 和 j 减一是因为电脑编号从 0 开始，而输入的编号从 1 开始。

初始化距离向量和优先队列：

vector dist(n, INT_MAX); 创建一个大小为 n 的距离向量 dist，初始值都设为无穷大 INT_MAX，表示从初始电脑到其他电脑的初始距离未知。
dist[k - 1] = 0; 将初始被感染电脑的距离设为 0，因为它已经被感染。
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 创建一个优先队列 pq，用于存储待处理的节点和其距离。优先队列按照距离从小到大排序，以便每次取出距离最小的节点进行处理。这里使用 greater<pair<int, int>> 是为了让优先队列按照距离升序排列。
pq.push({0, k - 1}); 将初始被感染电脑加入优先队列，其距离为 0，编号为 k - 1。

使用优先队列进行 Dijkstra 算法：

while (!pq.empty()) 当优先队列不为空时，循环取出距离最小的节点进行处理。
int u = pq.top().second; 取出优先队列顶部的节点编号 u。
pq.pop(); 弹出优先队列顶部的元素。
for (const auto& neighbor : graph[u]) 遍历当前节点 u 的相邻节点。
int v = neighbor.first; 获取相邻节点的编号 v。
int weight = neighbor.second; 获取从当前节点 u 到相邻节点 v 的权值（感染时间）。
if (dist[u]!= INT_MAX && dist[u] + weight < dist[v]) 如果当前节点 u 的距离不是无穷大，并且通过当前节点 u 到达相邻节点 v 的距离比已知的距离更短。
dist[v] = dist[u] + weight; 更新相邻节点 v 的距离为通过当前节点 u 到达的距离。
pq.push({dist[v], v}); 将更新后的相邻节点 v 及其距离加入优先队列，以便后续处理。

计算感染整个网络的最少时间：

int maxTime = 0; 创建一个变量 maxTime，用于存储感染整个网络所需的最少时间。
for (int time : dist) 遍历距离向量 dist。
if (time == INT_MAX) return -1; 如果发现有电脑的距离为无穷大，说明该电脑无法被感染，返回 -1。
maxTime = max(maxTime, time); 否则，更新 maxTime 为当前距离和已有的最大距离中的较大值。
return maxTime; 返回感染整个网络所需的最少时间。

3.4主函数部分分析

输入处理：

int n, m; 定义电脑数量 n 和连接数量 m。
cout << “输入电脑数量：”; cin >> n; 从用户输入获取电脑数量。
cout << “输入连接的数量：”; cin >> m; 从用户输入获取连接数量。
vector<vector> times(m, vector(3)); 创建一个大小为 m 的二维向量 times，用于存储连接信息。
cout << “输入连接信息（i j t）：” << endl; for (int i = 0; i < m; i++) { cin >> times[i][0] >> times[i][1] >> times[i][2]; } 从用户输入读取每条连接信息（电脑 i 感染电脑 j 需要时间 t）并存储在 times 中。
int k; cout << “输入初始被感染的电脑编号：”; cin >> k; 从用户输入获取初始被感染的电脑编号。