1350: 分糖果-c++直接上模板

解题思路:
传递糖果的方式是广搜，

先定义一个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;
}