解题思路:
传递糖果的方式是广搜,
先定义一个node结构体
struct node { int num;//节点编号 int step;//访问步数 };
然后直接上广搜模板
void bfs() { node tmp; tmp.num = start; tmp.step = 1; q.push(tmp);//q是node类型的队列 now++;//now是已经访问的节点数 while(!q.empty()) { int v = q.front().num; int step0 = q.front().step; for(int i = 0; i < g[v].size(); i++) { if(now == n+1)//n是总节点数 { cout << q.back().step+eat << endl; return; } if(vis[g[v][i]]) continue; tmp.num = g[v][i]; tmp.step = step0+1; q.push(tmp); vis[tmp.num] = true;//标记已经给过糖果 now++; } q.pop();//队首出队 } }
再加一个输入程序
void read() { memset(vis,false,sizeof(vis)); cin >> n >> m >> start >> eat; now = 0; int x,y; for(int i = 1; i > x >> y; g[x].push_back(y); g[y].push_back(x); } }
注意事项:
从1开始计数
完整代码:
#include <bits/stdc++.h> using namespace std; struct node { int num; int step; }; int n,m,start,eat,now; vector g[1001];//定义邻接表 queue q;//广搜的队列 bool vis[10005];//是否访问过 void read() { memset(vis,false,sizeof(vis)); cin >> n >> m >> start >> eat; now = 0; int x,y; for(int i = 1; i > x >> y; g[x].push_back(y); g[y].push_back(x); } } void bfs() { node tmp; tmp.num = start; tmp.step = 1; q.push(tmp); now++; while(!q.empty()) { int v = q.front().num; int step0 = q.front().step; for(int i = 0; i < g[v].size(); i++) { if(now == n+1) { cout << q.back().step+eat << endl; return; } if(vis[g[v][i]]) continue; tmp.num = g[v][i]; tmp.step = step0+1; q.push(tmp); vis[tmp.num] = true; now++; } q.pop(); } } int main() { read();//输入 bfs();//广搜 return 0; }
0.0分
1 人评分
【出圈】 (C语言代码)浏览:556 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:667 |
剪刀石头布 (C语言代码)不知道怎么直接在scanf中用枚举变量浏览:1307 |
WU-小九九 (C++代码)浏览:1684 |
C语言训练-亲密数 (C语言描述,反正怎么都能对)浏览:2165 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:760 |
简单的a+b (C语言代码)浏览:582 |
求圆的面积 (C语言代码)浏览:657 |
简单的a+b (C语言代码)浏览:657 |
字符逆序 (C语言代码)求大神指出错处,运行结果尝试了也与要求一样,但就是说结果错误,不知错在哪里浏览:436 |