BFS主要思想

将全部邻接点入队列，以FIFO原则，依次访问所有未访问节点

模版题及其实现

最小花费

在n个人中，某些人的银行账号之间可以互相转账。
这些人之间转账的手续费各不相同。
给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。

输入格式

第一行输入两个正整数n,m，分别表示总人数和可以互相转账的人的对数。
以下m行每行输入三个正整数x,y,z，表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。
最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。

输出格式

输出A使得B到账100元最少需要的总费用。精确到小数点后8位。

样例输入

3 3
1 2 1
2 3 2
1 3 3
1 3

样例输出

103.07153164

数据范围及时空限制

1<=n<=2000
1000ms
40960kb

代码实现

#include <bits/stdc++.h>
using namespace std;

struct side //边
{
    int next_node; //该边所对邻接点
    double value;  //值
};

struct node //点
{
    bool visited;
    //是否访问过
    double rate;
    //最后获得转账的剩余倍率
    vector<side> sides;
    //邻接边数组
    node()
    {
        visited = 0;
        rate = -1;
    } //初始化：未访问且倍率为-1(保证最小)
};

node nodes[200010]; //点数组
int n_node, n_side, source, destination;
//分别是： 点数 边数 源头 目标

int main()
{
    cin >> n_node >> n_side;

    for (int i = 1; i <= n_side; i++)
    {
        int node_, _node;
        double value;

        cin >> node_ >> _node >> value;
        //读取边数据

        side tmp;

        tmp.next_node = _node;
        //边的正向赋值(从node_到_node)
        tmp.value = 1 - value * 0.01;
        //将对应权值化为0.97,0.99等用于相乘

        nodes[node_].sides.push_back(tmp);
        //边的正向赋值(从node_到_node)

        tmp.next_node = node_;

        //边的反向赋值(从_node到node_)
        nodes[_node].sides.push_back(tmp); //边的反向赋值(从_node到node_)
    }

    queue<int> node_queue; //定义访问队列(FIFO)

    //从这里看起来是广搜,广搜队列深搜栈

    cin >> source >> destination;

    node_queue.push(source); //将源头入队

    nodes[source].rate = 1; //源头倍率为1

    nodes[source].visited = true; //源头已经访问

    while (!node_queue.empty()) //如果队列非空
    {
        int now_node = node_queue.front();
        node_queue.pop();
        //取出队头元素为当前节点

        nodes[now_node].visited = false; //设置取出的节点尚未访问

        for (unsigned int i = 0; i < nodes[now_node].sides.size(); i++)
        //访问该点所相邻的所有边
        {
            if (nodes[now_node].rate * nodes[now_node].sides[i].value >
                nodes[nodes[now_node].sides[i].next_node].rate)
            //如果当前节点的倍率*当前的边的倍率
            //(如果从这个点沿着这条边走过去到达的点的倍率)
            ////本来没有访问过的都是-1,
            ////这个倍率越大最后用100除以这个倍率时候得到的值越小，即花费越小
            //大于
            //到达的点的当前倍率
            //==>保证对面的点倍率最高
            {
                nodes[nodes[now_node].sides[i].next_node].rate =
                    nodes[now_node].rate * nodes[now_node].sides[i].value;
                //则将(如果从这个点沿着这条边走过去,到达的点的倍率)赋值给到达的节点的倍率
                if (!nodes[nodes[now_node].sides[i].next_node].visited)
                //如果沿这条边到达的点没有访问过
                {
                    nodes[nodes[now_node].sides[i].next_node].visited = true;
                    //就把它访问了
                    node_queue.push(nodes[now_node].sides[i].next_node);
                    //并且把它的所有邻接点入队
                }
            }
        }
    }

    printf("%.8lf\n", 100 / nodes[destination].rate);
    //100除以最后的倍率为最开始应该支付的费用
    return 0;
}