解题思路:
传递糖果的方式是广搜,
先定义一个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 人评分
printf基础练习2 (C语言代码)浏览:594 |
【回文数(二)】 (C语言代码)浏览:731 |
【亲和数】 (C语言代码)浏览:859 |
C语言训练-排序问题<1> (C语言代码)浏览:601 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:601 |
简单的a+b (C语言代码)浏览:599 |
WU-判定字符位置 (C++代码)浏览:1406 |
核桃的数量 (C语言代码)浏览:872 |
蛇行矩阵 (C语言代码)浏览:507 |
C语言程序设计教程(第三版)课后习题10.7 (用指针求解)浏览:1476 |