城市中的最短路径
2024-09-22 08:51:20
发布于:广东
#include <bits/stdc++.h>
#include <windows.h>
using namespace std;
struct ljb{
int place;
int km;
};
struct node{
int place;
int km;
int num;
};
struct pl{
int km;
int tjd[1005];
};
int n;
pl p_t_p[1005];
vector<ljb>v[1005];
int tt[1005];
void bfs(int u){
queue<node>q;
q.push({u,0,0});
tt[0] = u;
while(!q.empty()){
auto t = q.front();
q.pop();
for(auto it : v[t.place]){
if(p_t_p[it.place].km==-1 or t.km + it.km < p_t_p[it.place].km){
q.push({it.place,t.km+it.km,t.num+1});
p_t_p[it.place].km = t.km + it.km;
tt[t.num+1] = it.place;
for(int i=0;i<=t.num+1;i++){
p_t_p[it.place].tjd[i] = tt[i];
}
}
}
}
}
int main(){
cout << "一共有多少条路:";
cin >> n;
cout << "输入格式:起点 终点 路程 是否单行" << endl;
while(n--){
int u,vv,w;
bool is_a;
cin >> u >>vv >> w >> is_a;
if(is_a){
v[u].push_back({vv,w});
}else{
v[u].push_back({vv,w});
v[vv].push_back({u,w});
}
}cout << "你要询问几次:" ;
int q;
cin >> q;
cout << "输入格式 起点 终点"<< endl;
while(q--){
int u,vv;
memset(p_t_p,-1,sizeof p_t_p);
cin >>u >> vv;
if(u==vv){
cout << "最短路径为0km" << endl;
continue;
}
bfs(u);
if(p_t_p[vv].km==-1)cout << "无法从地方"<< u << "到达地方" << vv<<endl;
else{
cout << "最短路径为"<<p_t_p[vv].km << "km"<<endl;
int i=1;
cout <<"最短路径是:" <<p_t_p[vv].tjd[0];
while(p_t_p[vv].tjd[i]>0){
cout << " -> ";
cout << p_t_p[vv].tjd[i];
i++;
}cout << endl;
}
}
return 0;
}
这里空空如也
有帮助,赞一个