ACM 吝啬的国度
#include<cstdio> #include<cstring> #include<iostream> #include<stdio.h> #include<algorithm> #include<cstdlib> #include<vector> #include<deque> #include<utility> #define MAX 100020 using namespace std; vector<int> city[MAX]; int way[MAX]; int n, s; int bfs() { deque<int> dq;//建立队列 dq.push_back(s);//从最开先的位置开始 while (!dq.empty()) { int temp = dq.front(); dq.pop_front(); for (int i = 0;i < city[temp].size();i++) { if(way[city[temp][i]]==0) { dq.push_back(city[temp][i]); way[city[temp][i]] = temp; } } } return 0; } int main(int argc, char *argv[]) { //freopen("data.in", "r", stdin); int M; scanf("%d", &M); while (M--) { memset(city, 0, sizeof(city)); memset(way, 0, sizeof(way)); scanf("%d%d", &n, &s); way[s] = -1; for(int i=1;i<n;i++) { int a, b; scanf("%d%d", &a, &b); city[a].push_back(b); city[b].push_back(a); } bfs(); for(int i=1;i<n+1;i++) { printf("%d ", way[i]); } printf("\n"); } }
发布日期:2021-09-21 12:44:41
浏览次数:6
分类:技术文章
本文共 2391 字,大约阅读时间需要 7 分钟。
吝啬的国度
时间限制: 1000 ms | 内存限制: 65535 KB
难度: 3
- 描述
- 在一个吝啬的国度里有N个城市,这N个城市间只有N-1条路把这个N个城市连接起来。现在,Tom在第S号城市,他有张该国地图,他想知道如果自己要去参观第T号城市,必须经过的前一个城市是几号城市(假设你不走重复的路)。
- 输入
- 第一行输入一个整数M表示测试数据共有M(1<=M<=5)组 每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000),N表示城市的总个数,S表示参观者所在城市的编号 随后的N-1行,每行有两个正整数a,b(1<=a,b<=N),表示第a号城市和第b号城市之间有一条路连通。 输出
- 每组测试数据输N个正整数,其中,第i个数表示从S走到i号城市,必须要经过的上一个城市的编号。(其中i=S时,请输出-1) 样例输入
-
110 11 91 88 1010 38 61 210 49 53 7
样例输出 -
-1 1 10 10 9 8 3 1 1 8
上面是题目大概意思就是一个简单的遍历 从所在城市出发下一个到达的城市的前一个城市就是所在城市 所以一次入队出队就完了
#include<cstdio>
#include<cstring>#include<iostream>#include<stdio.h>#include<algorithm>#include<cstdlib>#include<vector>#include<deque>#include<utility>
#define MAX 100020
using namespace std;
vector<int> city[MAX];//存储城市矩阵int way[MAX];int n, s;int bfs(){ 写的不好见谅
吝啬的国度
时间限制: 1000 ms | 内存限制: 65535 KB
难度: 3
- 描述
- 在一个吝啬的国度里有N个城市,这N个城市间只有N-1条路把这个N个城市连接起来。现在,Tom在第S号城市,他有张该国地图,他想知道如果自己要去参观第T号城市,必须经过的前一个城市是几号城市(假设你不走重复的路)。
- 输入
- 第一行输入一个整数M表示测试数据共有M(1<=M<=5)组 每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000),N表示城市的总个数,S表示参观者所在城市的编号 随后的N-1行,每行有两个正整数a,b(1<=a,b<=N),表示第a号城市和第b号城市之间有一条路连通。 输出
- 每组测试数据输N个正整数,其中,第i个数表示从S走到i号城市,必须要经过的上一个城市的编号。(其中i=S时,请输出-1) 样例输入
-
110 11 91 88 1010 38 61 210 49 53 7
样例输出 -
-1 1 10 10 9 8 3 1 1 8
#include<cstdio>
#include<cstring>#include<iostream>#include<stdio.h>#include<algorithm>#include<cstdlib>#include<vector>#include<deque>#include<utility>
#define MAX 100020
using namespace std;
vector<int> city[MAX];int way[MAX];int n, s;int bfs(){转载地址:https://blog.csdn.net/Dog_dream/article/details/78730074 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月12日 00时53分32秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Jacoco探针源码解析(0.8.5 版本)
2019-04-27
Java的Instrumentation类原理分析
2019-04-27
"org.jacoco.agent.rt" 在 maven 中找不到
2019-04-27
计算机中的dump到底是什么意思?
2019-04-27
JaCoCo探针策略原理及案例总结
2019-04-27
阿里三面:说说线程封闭与ThreadLocal的关系
2019-04-27
看完让你吊打面试官-@Autowired注解到底怎么实现的?
2019-04-27
MySQL的行锁、表锁、间隙锁详解
2019-04-27
和阿里面试官扯了半小时ArrayBlockingQueue源码
2019-04-27
远离996,PDMan开源免费的国产数据库建模工具!
2019-04-27
现代操作系统的存储器结构
2019-04-27
深度揭秘年薪60W的阿里P7简历制作过程!
2019-04-27
可能是全网最全的SpringBoot启动流程源码分析(基于 2.1.5 版本)
2019-04-27
BAT华为等一线大厂工程师都在用的优秀 IDEA 插件
2019-04-27
屏幕录制和编辑神器ScreenFlow轻松上手
2019-04-27
防止Java序列化/反射破坏单例模式的解决方案
2019-04-27
面试/工作必备的vim基础及快捷键操作
2019-04-27
@SpringBootApplication注解到底做了什么,你真的了解吗?
2019-04-27
Java生态中性能最强数据库连接池HikariCP
2019-04-27
Restful Web Service设计规范
2019-04-27