Question

求解释C++代码，本人没看懂，主要是队列容器什么的

#include<cstring>
#include<cstdio>
#include<vector>
#include<iterator>
#include<queue>
using namespace std;
const int MAX=1010;
int len[MAX];
bool visited[MAX];
int n,m,p,q,a,b,d;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int> > > dq;
struct Node{
Node(int num,int dis):num(num),dis(dis){}
int num,dis; };
void Dijkstra(vector<vector<Node> >& g) {
pair<int,int> tp;
while(!dq.empty()){
tp=dq.top();dq.pop();
if(tp.second==q-1) return;
if(tp.first!=len[tp.second]) continue;
visited[tp.second]=true;
for(int j=0;j!=g[tp.second].size();++j)
if(tp.first+g[tp.second][j].dis<len[g[tp.second][j].num]){
len[g[tp.second][j].num]=tp.first+g[tp.second][j].dis;
dq.push(make_pair(len[g[tp.second][j].num],g[tp.second][j].num));} } }
int main(){
int t;
cin>>t;
while(t--){
while(!dq.empty()) dq.pop();
cin>>n>>m>>p>>q;
vector<vector<Node> > g(m);
for(int i=0;i!=g.size();i++) len[i]=INT_MAX;
for(int i=0;i!=n;i++){
cin>>a;
len[a-1]=0;
dq.push(make_pair(0,a-1)); }
for(int i=0;i!=p;++i){
scanf("%d%d%d",&a,&b,&d);
g[a-1].push_back(Node(b-1,d));
g[b-1].push_back(Node(a-1,d)); }
Dijkstra(g);
cout<<len[q-1]<<endl;
memset(len,0,sizeof(len));
memset(visited,0,sizeof(visited)); } }
1、priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int> > > dq;2、struct Node{Node(int num,int dis):num(num),dis(dis){}3、void Dijkstra(vector<vector<Node> >& g) {pair<int,int>tp;4、vector<vector<Node> > g(m);

Answer 1

就是用迪杰斯特拉算法求最短路径

追问

我补充问题了，麻烦看一下，解释一下

追答

你可以找c语言的迪杰斯特拉算法
然后对比看看和这个用容器实现的有什么区别 就知道了

追问

不是算法问题，是语法不懂，不明白其原理

追答

priority_queue, vector>, greater > > dq;

这是一个优先队列 其中三个模版参数
第一个pair是一个双值对,有first和second,用于优先队列的优先级,实际存储的应该是两个点去和来两个的优先级(距离)
第二个vector>,是一个双值的容器,存储两个点互相的距离
第三个是用于标识这个优先队列排序的,greater是从小到大
struct Node{Node(int num,int dis):num(num),dis(dis){}

这个是定义一个struct,里面的构造函数自动调用了num(num)和dis(dis)进行初始化
void Dijkstra(vector >& g) {pairtp;

这个是迪杰斯特拉算法主函数,
参数vector >& g和vector > gm一样,是一个容器的容器
存储的是所有的点到其他点的距离(N*N)
就是说这个容器里面的元素还是一个容器,内层的容器存的是某个点到所有点的距离
外层的容器就存的是(某个点到所有点的距离)的集合

Answer 2

你想解释啥内，麻烦把你的问题描述清楚，你不是要别人把你这一大段代码一句一句的解释一下把。

追问

我补充问题了，麻烦看一下