#include<iostream> #include<cstdio> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; typedef pair<int,int> P; const int maxn=1005; const int Inf=0x3f3f3f3f; struct Edge{ int to,w; Edge(int _to,int _w):to(_to),w(_w){} }; vector<Edge> G[maxn]; int dist[maxn]; bool vis[maxn]; void Dijkstra(int s){ memset(dist,Inf,sizeof(dist)); memset(vis,false,sizeof(vis)); dist[s]=0; priority_queue<P,vector<P>,greater<P> > min_pq; min_pq.push(make_pair(dist[s],s)); while(!min_pq.empty()){ int u=min_pq.top().second; min_pq.pop(); if(vis[u]) continue; vis[u]=true; for(int i=0;i<G[u].size();i++){ int v=G[u][i].to,w=G[u][i].w; if(dist[v]>dist[u]+w){ dist[v]=dist[u]+w; min_pq.push(make_pair(dist[v],v)); } } } } int main(){ int n,m,s; scanf("%d%d%d",&n,&m,&s); for(int i=0;i<m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); G[u].push_back(Edge(v,w)); } Dijkstra(s); for(int i=1;i<=n;i++){ if(dist[i]==Inf) printf("INF "); else printf("%d ",dist[i]); } return 0; }解释这段代码
时间: 2024-04-20 20:23:55 浏览: 16
这段代码也是实现了Dijkstra算法来求解单源最短路径问题。与之前的代码相比,有以下几点不同之处:
1. 使用了`typedef`来定义了一个类型别名`P`,表示一个节点和距离的对。
2. 改用了`scanf`和`printf`来进行输入输出,而不是使用`cin`和`cout`。
3. 使用了`Inf`表示无穷大,而不是`INF`。
4. 优先队列的定义方式稍有不同,使用了`greater<P>`来将距离小的节点放在队列的前面。
5. 输出结果时,如果距离为无穷大,则输出"INF",否则输出距离值。
除了上述几点不同之处,这段代码与之前的代码实现了相同的功能,都是通过Dijkstra算法求解单源最短路径问题。
相关问题
#include<bitslstdc++.h>
#include<bits/stdc++.h>是一个万能头文件,它包含了许多常用的C++标准库头文件。它相当于以下代码的总和:
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <cctype>
使用#include<bits/stdc++.h>可以简化我们的代码,不需要逐个引入标准库的头文件。然而,需要注意的是,这种写法并不是标准的C++写法,它只在一些编译器上支持。所以,如果你的编译器不支持这种写法,你需要手动引入具体的标准库头文件。
提示:你可以问一些与头文件相关的问题,例如其他常用的C++头文件是什么?C++标准库中的算法头文件是哪个?等等。
#include<bits/stdc++.h>
#include<bits/stdc++.h> 是一个万能头文件,相当于包含了很多常用的头文件。它包含了以下代码的总和:
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <cctype>
这个头文件可以方便地包含很多常用的标准库头文件,减少了我们在编写代码时需要逐个包含这些头文件的麻烦。然而,这个头文件并不是标准C++的一部分, 它是一些编译器(如GCC)自己的实现,所以在一些特定的编译环境中并不一定能够使用。例如在Visual Studio中,如果要使用#include<bits/stdc .h>,则需要手动添加头文件stdc .h,因为Visual Studio不自带这个头文件。