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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#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;
}