// 根据prev构建最短路径 vector<string> path; string curr = end; while (curr != start) { path.push_back(curr); curr = prev[curr]; } path.push_back(start); reverse(path.begin(), path.end()); return path;添加中文注释
时间: 2024-04-17 20:25:46 浏览: 39
```cpp
// 根据prev构建最短路径
vector<string> path; // 存储最短路径的站点名称
string curr = end; // 当前站点初始化为结束站点
while (curr != start) // 当前站点不是起始站点时继续循环
{
path.push_back(curr); // 将当前站点添加到最短路径中
curr = prev[curr]; // 获取当前站点的前驱站点作为下一个要处理的站点
}
path.push_back(start); // 将起始站点添加到最短路径中
reverse(path.begin(), path.end()); // 反转最短路径,使其按照起始到结束的顺序排列
return path; // 返回构建的最短路径
```
这段代码是根据保存最短路径上每个站点的前驱站点的`prev`数组,从结束站点逆向构建最短路径。在循环中,将当前站点添加到最短路径中,并更新当前站点为其前驱站点,直到当前站点为起始站点。最后,将起始站点添加到最短路径中,并使用`reverse`函数将其顺序反转,使其按照起始到结束的顺序排列。最终,返回构建的最短路径。
相关问题
用py写一段代码 <div class="page"><b>1</b><a href="/dongman/index_2.htm">2</a><a href="/dongman/index_3.htm">3</a><a href="/dongman/index_4.htm">4</a><a href="/dongman/index_5.htm">5</a><a href="/dongman/index_6.htm">6</a><a href="/dongman/index_7.htm">7</a><a href="/dongman/index_8.htm">8</a><span class="slh">…</span><a href="/dongman/index_116.htm">116</a><a href="/dongman/index_2.htm" class="prev">下一页></a></div> 这是我的思路 取所有htm|\"(.*?)</然后输出最大的数
你使用正则表达式来提取字符串中的数字找到其中的最大值。以下是Python实现的代码示例:
```
import re
html_string = '<div class="page"><b>1</><a href="/dongman/index_2.htm">2</a><a href="/dongman/index_3.htm">3</aa href="/dongman/index_4.htm">4</a><a href="/dongman/index_5.htm">5</a><a href="/dongman/index_6.htm">6</a><a href="/dongman/index_7.htm">7</a><a href="/dongman/index_8.htm">8</a><span class="slh">…</span><a href="/dongman/index_116.htm">116</a><a href="/dongman/index_2.htm" class="prev">下一页></a></div>'
numbers = re.findall(r'\d+', html_string)
max_number = max(map(int, numbers))
print(max_number)
```
这段代码会输出数字中的最大值,即116。它首先使用正则表达式`r'\d+'`匹配字符串中的所有数字,然后将这些数字转换为整数并找到其中的最大值,最后打印出来。
#include<iostream> #include<vector> #include<iterator> #include<limits.h> #include<string> using namespace std; int n; //顶点个数 vector<vector<int> >g; //g:图(graph)(用邻接矩阵(adjacent matrix)表示) int s; //s:源点(source) vector<bool>known; //known:各点是否知道最短路径 vector<int>dist; //dist:源点 s 到各点的最短路径长度 vector<int>pre; //prev 各点的最短路径的前一顶点 void Dijkstra() { //贪心算法 known.assign(n,false); dist.assign(n,INT_MAX); pre.resize(n); //初始化 known、dist、prev dist[s]=0; //初始化源点 s 到自身的路径 for(;;) { int min=INT_MAX,v=s; for(int i=0; i<n; ++i) if(!known[i]&&min>dist[i]) min=dist[i],v=i; //寻找未知的最短路径的顶点 v if(min==INT_MAX)break; //如果找不到,退出 known[v]=true; for(int w=0; w<n; ++w) //遍历所有 v 指向的顶点 w if(!known[w]&&g[v][w]<INT_MAX && dist[w]>dist[v]+g[v][w]) //调整顶点 w 的最短路径长度 dist 和最短路径的前一顶点 prev dist[w]=dist[v]+g[v][w],pre[w]=v; } } void Print_SP(int v) { if(v!=s)Print_SP(pre[v]); cout<<v<<" "; } int main() { n=5; g.assign(n,vector<int>(n,INT_MAX)); //构建图 g[0][1]=10; g[0][3]=30; g[0][4]=100; g[1][2]=50; g[2][4]=10; g[3][2]=20; g[3][4]=60; s=0; Dijkstra(); copy(dist.begin(),dist.end(),ostream_iterator<int>(cout," ")); cout<<endl; for(int i=0; i<n; ++i) if(dist[i]!=INT_MAX) { cout<<s<<"->"<<i<<":"; Print_SP(i); cout<<endl; } return 0; }每行代码什么意思
这段代码实现了Dijkstra算法,用于求解带权图中单源最短路径问题。下面是每行代码的具体意思:
```c++
#include<iostream>
#include<vector>
#include<iterator>
#include<limits.h>
#include<string>
```
头文件的引入。
```c++
using namespace std;
```
使用标准命名空间。
```c++
int n; //顶点个数
vector<vector<int> >g; //g:图(graph)(用邻接矩阵(adjacent matrix)表示)
int s; //s:源点(source)
vector<bool>known; //known:各点是否知道最短路径
vector<int>dist; //dist:源点 s 到各点的最短路径长度
vector<int>pre; //prev 各点的最短路径的前一顶点
```
定义了顶点个数、图、源点、各点是否知道最短路径、源点到各点的最短路径长度、各点的最短路径前一顶点等变量。
```c++
void Dijkstra() { //贪心算法
known.assign(n,false);
dist.assign(n,INT_MAX);
pre.resize(n); //初始化 known、dist、prev
dist[s]=0; //初始化源点 s 到自身的路径
for(;;) {
int min=INT_MAX,v=s;
for(int i=0; i<n; ++i)
if(!known[i]&&min>dist[i])
min=dist[i],v=i; //寻找未知的最短路径的顶点 v
if(min==INT_MAX)break; //如果找不到,退出
known[v]=true;
for(int w=0; w<n; ++w) //遍历所有 v 指向的顶点 w
if(!known[w]&&g[v][w]<INT_MAX && dist[w]>dist[v]+g[v][w]) //调整顶点 w 的最短路径长度 dist 和最短路径的前一顶点 prev
dist[w]=dist[v]+g[v][w],pre[w]=v;
}
}
```
Dijkstra算法函数的实现。首先对known、dist、prev进行初始化,然后进行循环,每次找到未知的最短路径的顶点v,将其标记为已知,再遍历所有v指向的顶点w,调整顶点w的最短路径长度和最短路径的前一顶点prev。
```c++
void Print_SP(int v) {
if(v!=s)Print_SP(pre[v]);
cout<<v<<" ";
}
```
输出最短路径的函数实现。递归输出前一顶点的最短路径,然后输出当前顶点v。
```c++
int main() {
n=5;
g.assign(n,vector<int>(n,INT_MAX)); //构建图
g[0][1]=10;
g[0][3]=30;
g[0][4]=100;
g[1][2]=50;
g[2][4]=10;
g[3][2]=20;
g[3][4]=60;
s=0;
Dijkstra();
copy(dist.begin(),dist.end(),ostream_iterator<int>(cout," "));
cout<<endl;
for(int i=0; i<n; ++i)
if(dist[i]!=INT_MAX) {
cout<<s<<"->"<<i<<":";
Print_SP(i);
cout<<endl;
}
return 0;
}
```
主函数的实现。初始化图,设置源点,调用Dijkstra函数求解最短路径,输出源点到各点的最短路径长度,逐个输出源点到每个顶点的最短路径及其长度。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>图书商城-图书列表</title> <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"> <script src="https://cdn.bootcss.com/vue/2.5.16/vue.min.js"></script> <script src="https://unpkg.com/axios/dist/axios.min.js"></script> </head> <body> 0">
{{bk.bookName}} ¥{{bk.bookPrice}} <iframe src="footer.html" frameborder="0" scrolling="no" width="100%" height="245px"></iframe> <script src="/BookShopSystem_war/layui/layui.js"></script>这是完整的html代码,请结合你给出的分页功能整合出完整的代码
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)