题目 3230: 蓝桥杯2024年第十五届省赛真题-星际旅行
时间限制: 2s 内存限制: 512MB 提交: 1290 解决: 149
题目描述
小明国庆节准备去某星系进行星际旅行，这个星系里一共有 n 个星球，其中布置了 m 道双向传送门，第 i 道传送门可以连接 ai，bi 两颗星球（ai , bi 且任意两颗星球之间最多只有一个传送门）。
他看中了一款 “旅游盲盒”，一共有 Q 个盲盒，第 i 个盲盒里的旅行方案规定了旅行的起始星球 xi 和最多可以使用传送门的次数 yi。只要从起始星球出发，使用传送门不超过规定次数能到达的所有星球都可以去旅行。
小明关心在每个方案中有多少个星球可以旅行到。小明只能在这些盲盒里随机选一个购买，他想知道能旅行到的不同星球的数量的期望是多少。
输入格式
输入共 m + Q + 1 行。
第一行为三个正整数 n，m，Q。
后面 m 行，每行两个正整数 ai，bi。
后面 Q 行，每行两个整数 xi，yi。
输出格式
输出共一行，一个浮点数（四舍五入保留两位小数）。
样例输入复制
3 2 3
1 2
2 3
2 1
2 0
1 1
样例输出复制
2.00
提示
【样例说明】
第一个盲盒可以旅行到 1, 2, 3。
第二个盲盒可以旅行到 2。
第三个盲盒可以旅行到 1, 2。
所以期望是 (3 + 1 + 2)/3 = 2.00。
【评测用例规模与约定】
对于 20% 的评测用例，保证 n ≤ 300。
对于 100% 的评测用例，保证 n ≤ 1000，m ≤ min{n(n−1)/2, 5n}，Q ≤ 50000，0 ≤ yi ≤ n。
1.分析
这里用宽搜找到每个起点的距离，坑点在四舍五入保留2位小数。
2.代码
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
const int MAX = 1010;
typedef long long LL;
int n, m, q;
int s, num,idx[MAX],dis[MAX][MAX], sum;
vector<int> v[MAX];
void bfs(int x) {
memset(idx, 0, sizeof idx);
idx[x] = 1;
dis[x][x] = 0;
queue<int> q;
q.push(x);
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = 0; i < v[t].size(); i++) {
int to = v[t][i];
if (!idx[to]) {
idx[to] = 1;
q.push(to);
dis[x][to] = dis[x][t] + 1;
}
}
}
}
int main() {
cin >> n >> m >> q;
while (m--) {
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
memset(dis, 0x3f, sizeof dis);
for (int i = 1; i <= n; i++) {
bfs(i);
}
for (int k = 0; k < q;k++) {
cin >> s >> num;
for (int i = 1; i <= n; i++) {
if (dis[s][i] <= num) {
sum++;
}
}
}
double re = sum*1.0/ q;
re = round(re * 100) / 100;
printf("%.2f", re);
return 0;
}