热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

洛谷——P3906Geodetic集合

P3906Geodetic集合题目描述图G是一个无向连通图,没有自环,并且两点之间至多只有一条边。我们定义顶点v,u最短路径就是从v到u经过边最少的路径。所有包含在v-u的最短路径

 

P3906 Geodetic集合

题目描述

图G是一个无向连通图,没有自环,并且两点之间至多只有一条边。我们定义顶点v,u最短路径就是从v到u经过边最少的路径。所有包含在v-u的最短路径上的顶点被称为v-u的Geodetic顶点,这些顶点的集合记作I(v, u)。

我们称集合I(v, u)为一个Geodetic集合。

例如下图中,I(2, 5)={2, 3, 4, 5},I(1, 5)={1, 3, 5},I(2, 4)={2, 4}。

技术分享图片

给定一个图G和若干点对v,u,请你分别求出I(v, u)。

输入输出格式

输入格式:

 

输入文件geo.in,第一行为两个整数n,m,分别表示图G的顶点数和边数(顶点编号1-n,n≤40)。下接m行,每行两个整数a,b表示顶点a和b之间有一条无向边。

第m+2行有一个整数k,表示给定的点对数。下接k行,每行两个整数v,u。。

 

输出格式:

 

输出文件geo.out,共k行,每行对应输入文件中每一个点对v,u,按顶点编号升序输出I(v, u)。同一行的每个数之间用空格分隔。

 

输入输出样例



输入样例#1: 复制

5 6
1 2
1 3
2 3
2 4
3 5
4 5
3
2 5
5 1
2 4


输出样例#1: 复制

2 3 4 5
1 3 5
2 4



解题报告:


题目大意:给你一个无向连通图,询问两点之间最短路径上的点


spfa 跑最短路,记录到达每个节点最短路径上的的前驱即可,不过前驱可能有好几个,vectorG[N]存储即可


此题有个坑点,一定要去重!!!


#include
#define N 101001
using namespace std;
int n,m,head[N],tot;
bool pvis[N];
struct nod {
int to,next;
} e[N];
void add(int u,int v) {
e[
++tot].to=v,e[tot].next=head[u],head[u]=tot;
}
int q,d[N];
bool vis[N];
queue
<int>Q;
vector
<int>G[50];
void spfa(int x) {
while(!Q.empty()) Q.pop();
Q.push(x);
for(int i=1; i<=n; i++) G[i].clear();
memset(vis,
0,sizeof(vis));
memset(d,
0x3f,sizeof(d));
vis[x]
=1,d[x]=0;
while(!Q.empty()) {
int u=Q.front();
Q.pop();
vis[u]
=0;
for(int i=head[u]; i; i=e[i].next) {
int v=e[i].to;
if(d[v]>d[u]+1) {
d[v]
=d[u]+1;
if(!vis[v]) {
G[v].clear();
G[v].push_back(u);
Q.push(v);
vis[v]
=1;
}
}
else if(d[v]==d[u]+1) {
G[v].push_back(u);
}
}
}
}
int an[N],tpt;
void dg(int u,int a) {
int sz=G[u].size();
an[
++tpt]=u;
for(int i=0; i) {
int v=G[u][i];
if(v==a) continue;
dg(v,a);
}
}
int main() {
scanf(
"%d%d",&n,&m);
for(int a,b,i=1; i<=m; i++) {
scanf(
"%d%d",&a,&b);
add(a,b),add(b,a);
}
scanf(
"%d",&q);
for(int a,b,i=1; i<=q; i++) {
scanf(
"%d%d",&a,&b);
// memset(pvis,0,sizeof(pvis));
spfa(a);
memset(an,
0,sizeof(an));
tpt
=0;
dg(b,a);
an[
++tpt]=a;
sort(an
+1,an+1+tpt);
for(int j=1; j<=tpt; j++){
if(an[j]!=an[j+1]) printf("%d ",an[j]);
}
puts(
"");
}
return 0;
}

 


推荐阅读
  • 基于layUI的图片上传前预览功能的2种实现方式
    本文介绍了基于layUI的图片上传前预览功能的两种实现方式:一种是使用blob+FileReader,另一种是使用layUI自带的参数。通过选择文件后点击文件名,在页面中间弹窗内预览图片。其中,layUI自带的参数实现了图片预览功能。该功能依赖于layUI的上传模块,并使用了blob和FileReader来读取本地文件并获取图像的base64编码。点击文件名时会执行See()函数。摘要长度为169字。 ... [详细]
  • 本文内容为asp.net微信公众平台开发的目录汇总,包括数据库设计、多层架构框架搭建和入口实现、微信消息封装及反射赋值、关注事件、用户记录、回复文本消息、图文消息、服务搭建(接入)、自定义菜单等。同时提供了示例代码和相关的后台管理功能。内容涵盖了多个方面,适合综合运用。 ... [详细]
  • Mac OS 升级到11.2.2 Eclipse打不开了,报错Failed to create the Java Virtual Machine
    本文介绍了在Mac OS升级到11.2.2版本后,使用Eclipse打开时出现报错Failed to create the Java Virtual Machine的问题,并提供了解决方法。 ... [详细]
  • 在说Hibernate映射前,我们先来了解下对象关系映射ORM。ORM的实现思想就是将关系数据库中表的数据映射成对象,以对象的形式展现。这样开发人员就可以把对数据库的操作转化为对 ... [详细]
  • 本文介绍了在SpringBoot中集成thymeleaf前端模版的配置步骤,包括在application.properties配置文件中添加thymeleaf的配置信息,引入thymeleaf的jar包,以及创建PageController并添加index方法。 ... [详细]
  • 本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用,包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]
  • 1,关于死锁的理解死锁,我们可以简单的理解为是两个线程同时使用同一资源,两个线程又得不到相应的资源而造成永无相互等待的情况。 2,模拟死锁背景介绍:我们创建一个朋友 ... [详细]
  • 后台获取视图对应的字符串
    1.帮助类后台获取视图对应的字符串publicclassViewHelper{将View输出为字符串(注:不会执行对应的ac ... [详细]
  • 《数据结构》学习笔记3——串匹配算法性能评估
    本文主要讨论串匹配算法的性能评估,包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库,可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n),通过随机取出长度为m的子串作为模式P,在文本T中进行匹配,统计平均复杂度。对于成功和失败的匹配分别进行测试,分析其平均复杂度。详情请参考相关学习资源。 ... [详细]
  • 本文介绍了通过ABAP开发往外网发邮件的需求,并提供了配置和代码整理的资料。其中包括了配置SAP邮件服务器的步骤和ABAP写发送邮件代码的过程。通过RZ10配置参数和icm/server_port_1的设定,可以实现向Sap User和外部邮件发送邮件的功能。希望对需要的开发人员有帮助。摘要长度:184字。 ... [详细]
  • 在project.properties添加#Projecttarget.targetandroid-19android.library.reference.1..Sliding ... [详细]
  • 本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值,函数可以作为变量自由传递,也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性,为程序开发带来了便利。 ... [详细]
  • 本文讨论了如何优化解决hdu 1003 java题目的动态规划方法,通过分析加法规则和最大和的性质,提出了一种优化的思路。具体方法是,当从1加到n为负时,即sum(1,n)sum(n,s),可以继续加法计算。同时,还考虑了两种特殊情况:都是负数的情况和有0的情况。最后,通过使用Scanner类来获取输入数据。 ... [详细]
  • 本文介绍了OC学习笔记中的@property和@synthesize,包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]
  • 猜字母游戏
    猜字母游戏猜字母游戏——设计数据结构猜字母游戏——设计程序结构猜字母游戏——实现字母生成方法猜字母游戏——实现字母检测方法猜字母游戏——实现主方法1猜字母游戏——设计数据结构1.1 ... [详细]
author-avatar
手机用户2502902033
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有