首页 > 代码库 > zzuoj 找最佳通路
zzuoj 找最佳通路
校内的OJ,得把题目粘上来
Description
有 n 个 城市,它们之间的交通情况已知。现在要求根据一个出发点Cs和一个到达点Cd,请编程序,由计算机找到从城市Cs 到 Cd 的一条路径,要求经过城市最少。
Input
输入由若干行组成,第一行有四个整数,n(1≤n≤50)、m(1≤m≤n*n)和s(1≤s≤n)、e(1≤e≤n);n表示城市数,m表示道路数,s和e表示出发点和到达点。
第 2至m+1行是m 条边的 信息,每行两个整数,为边的起点和终点。
Output
一个整数,经过城市的个数(包括起点和终点)
Sample Input
6 6 1 5
1 3
2 6
3 6
3 2
6 4
4 5
Sample Output
5
题解:这是今天讲的使用BFS来找最短路径的问题,有关DFS和BFS我还是单独写一篇来讲一下我的感悟。
这道题是典型的BFS问题,这里直接上代码。
顺手又用DFS撸了一遍
BFS
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<queue> 5 #define maxn 52 6 using namespace std; 7 8 bool path[maxn][maxn]; 9 int ctm[maxn]; 10 bool city[maxn]; 11 int n,pn,s,v,num; 12 13 queue<int> q; 14 15 void init() 16 { 17 for(int i=1;i<=n;i++) 18 for(int j=1;j<=n;j++) 19 path[i][j]=false; 20 21 memset(city,true,sizeof(city)); 22 23 } 24 25 void bfs(int s,int v) 26 { 27 int now; 28 q.push(s); 29 ctm[s]=1; 30 city[s]=false; 31 while(!q.empty()){ 32 now=q.front(); 33 q.pop(); 34 for(int i=1;i<=n;i++){ 35 if(city[i]&&path[now][i]){ 36 city[i]=false; 37 q.push(i); 38 ctm[i]=ctm[now]+1; 39 if(i==v){ 40 num=ctm[i]; 41 return ; 42 } 43 } 44 } 45 } 46 } 47 48 int main() 49 { 50 scanf("%d%d%d%d",&n,&pn,&s,&v); 51 52 init(); 53 54 int u,v; 55 for(int i=1;i<=pn;i++){ 56 57 scanf("%d %d",&u,&v); 58 path[u][v]=true;path[v][u]=true; 59 } 60 61 bfs(s,v); 62 63 printf("%d\n",num); 64 65 return 0; 66 }
BFS
#include<cstdio> #include<cstring> #define INF 999999999 #define maxn 53 using namespace std; bool path[maxn][maxn]; bool f[maxn]; int n,pn,s,v,mi,des,num; void init() { memset(path,false,sizeof(path)); memset(f,true,sizeof(f)); f[s]=false; mi=INF;des=1; } void dfs(int s,int v) { for(int i=1;i<=n;i++){ if(f[i]&&path[s][i]){ des++; if(i==v){ if(des<mi){ mi=des; num=des; } } f[i]=false; dfs(i,v); des--; f[i]=true; } } } int main() { scanf("%d%d%d%d",&n,&pn,&s,&v); init(); int u,l; for(int i=0;i<pn;i++){ scanf("%d%d",&u,&l); path[u][l]=true; } dfs(s,v); printf("%d",num); return 0; }
zzuoj 找最佳通路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。