使用 BFS 从给定节点查找所有节点的最短路径
finding shortest path of all nodes from a given node using BFS
当我增加或减少 INF 值时,输出行为异常..
我认为 INF 不应该对输出有任何影响..
每条边的长度是 6
输入
1个
4 2
1 2
1 3
1个
输出是 6 6 -1
当我将 INF 更改为 1e8 时,输出为 0 0 0
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define MAX 2000
#define INF 1000000
vector<int> adj[MAX];
int d[MAX];
bool visited[MAX];
void initialise(){
for(int i=0;i<=MAX;i++){
visited[i]=false;
}
}
void shortestPathBfs(int start){
queue<int> q;
q.push(start);
visited[start]=true;
d[start]=0;
while(!q.empty()){
int p=q.front();
q.pop();
for(int i=0;i<adj[p].size();i++){
int v=adj[p][i];
if(!visited[v] && d[v]>d[p]+6){
d[v]=d[p]+6;
q.push(v);
visited[v]=true;
}
}
}
}
int main(){
int T,N,M,S,x,y;
cin>>T;
while(T--){
cin>>N>>M;
for(int i=0;i<M;i++){
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
cin>>S;
initialise();
memset(d,INF,sizeof(d));
shortestPathBfs(S);
for(int i = 1; i <=N; i++) {
if(i == S)
continue;
if(d[i] >= INF)
cout<<"-1"<<" ";
else
cout<<d[i]<<" ";
}
}
}
问题在于
memset(d,INF,sizeof(d));
memset()
仅用 byte 值填充内存。在这里它最终会用 int
值 INF
的最低有效字节填充数组。要修复它,请创建一个明确的 for
循环或使用 std::fill()
代替。
当我增加或减少 INF 值时,输出行为异常.. 我认为 INF 不应该对输出有任何影响.. 每条边的长度是 6 输入 1个 4 2 1 2 1 3 1个 输出是 6 6 -1 当我将 INF 更改为 1e8 时,输出为 0 0 0
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define MAX 2000
#define INF 1000000
vector<int> adj[MAX];
int d[MAX];
bool visited[MAX];
void initialise(){
for(int i=0;i<=MAX;i++){
visited[i]=false;
}
}
void shortestPathBfs(int start){
queue<int> q;
q.push(start);
visited[start]=true;
d[start]=0;
while(!q.empty()){
int p=q.front();
q.pop();
for(int i=0;i<adj[p].size();i++){
int v=adj[p][i];
if(!visited[v] && d[v]>d[p]+6){
d[v]=d[p]+6;
q.push(v);
visited[v]=true;
}
}
}
}
int main(){
int T,N,M,S,x,y;
cin>>T;
while(T--){
cin>>N>>M;
for(int i=0;i<M;i++){
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
cin>>S;
initialise();
memset(d,INF,sizeof(d));
shortestPathBfs(S);
for(int i = 1; i <=N; i++) {
if(i == S)
continue;
if(d[i] >= INF)
cout<<"-1"<<" ";
else
cout<<d[i]<<" ";
}
}
}
问题在于
memset(d,INF,sizeof(d));
memset()
仅用 byte 值填充内存。在这里它最终会用 int
值 INF
的最低有效字节填充数组。要修复它,请创建一个明确的 for
循环或使用 std::fill()
代替。