题意:存在有n个地方, 有两个人分别从1和n号地点出发,问在最短的时间里他们在哪个地点能能够相遇,如果有多个地点则输出多个节点。然后给了m个集合,每个集合中的所有地点之间距离为t。
题解:该题很容易想到最短路然后枚举所有可能相遇的点取max后取min,难点在于建图,如果暴力建图的话会出现n^2复杂度,所以我们把每个集合当成一个源点,源点到集合中点的距离为t,集合中点到该源点的距离为0,这样建图就是O(n)了。然后分别跑1和n的最短路,枚举各点即可。
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define met(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;}
ll qPow(ll base, ll n) {ll res = 1; while(n) {
if(n & 1) res *= base; base *= base; n >>= 1;} return res;}
int T, n, m, Head[maxn << 1], edgesNum = 0, t, s, d;
int dis[10][101000];
struct EDGE {
int to, from, w, nex;
} edges[maxn << 2];
void init() {edgesNum = 0; met(Head, -1); for(int i = 0; i <= n + m; i++) dis[0][i] = dis[1][i] = inf;}
void addEdge(int u, int v, int w) {
edges[edgesNum].from = u;
edges[edgesNum].to = v;
edges[edgesNum].w = w;
edges[edgesNum].nex = Head[u];
Head[u] = edgesNum++;
}
void spfa(int s);
int main() {
int cas = 1;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
init();
rep(i, 1, m + 1) {
scanf("%d%d", &t, &s);
rep(j, 0, s) {
scanf("%d", &d);
addEdge(n + i, d, t);
addEdge(d, n + i, 0);
}
}
spfa(1);
spfa(n);
int MIN = inf;
vector<int> v;
v.clear();
rep(i, 1, n + 1) {
// printf("dis[%d] = %d\n", i, dis[0][i]);
// printf("dis[%d] = %d\n", i, dis[1][i]);
int t = max(dis[0][i], dis[1][i]);
if(t < MIN && t != inf) {
v.clear();
MIN = t;
v.pb(i);
} else if(t == MIN && t != inf) {
v.pb(i);
}
}
//sort(v.begin(), v.end());
int len = v.size();
if(MIN != inf) {
printf("Case #%d: %d\n", cas++, MIN);
rep(i, 0, len) {
printf("%d", v[i]);
if(i != len - 1) printf(" ");
}
puts("");
} else {
printf("Case #%d: Evil John\n", cas++);}
}
return 0;
}
void spfa(int s) {
int pos = (s == 1 ? 0 : 1);
bool vis[maxn];
met(vis, false);
dis[pos][s] = 0;
vis[s] = true;
queue<int> q;
while(!q.empty()) q.pop();
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false;
for(int e = Head[u]; ~e; e = edges[e].nex) {
int v = edges[e].to;
if(dis[pos][v] > dis[pos][u] + edges[e].w) {
dis[pos][v] = dis[pos][u] + edges[e].w;
if(!vis[v]) {
q.push(v);
vis[v] = true;
}
}
}
}
}
文章浏览阅读1w次,点赞14次,收藏63次。2019之前的工程是SDK开发的, 在2019上没有launch sdk这个选项, 而是在tools/Vitis下1 升级工程这里要升级忽略2 report ip检查状态,然后升级 IP3 生产bit流这个过程有点久, 等待弹窗出来就OK4 Export Hardware5 tools/ launch vitis 启动vitis6 导入SDK环境选择eclips选择工程目录, 点击finish..._vivado2019没有sdk
文章浏览阅读1.2k次。项目需求是将线上服务器生成的日志信息实时导入kafka,采用agent和collector分层传输,app的数据通过thrift传给agent,agent通过avro sink将数据发给collector,collector将数据汇集后,发送给kafka,拓扑结构如下:现将调试过程中遇到的问题以及解决方法记录如下:1、 [ERROR - org.apache.thrift.server.Abstr..._ubuntu发送flume文件夹到节点一直处于发送状态
文章浏览阅读1.4k次,点赞4次,收藏26次。清洗数据是数据预处理的一个重要步骤,Pandas 提供了许多功能和方法来帮助您进行数据清洗。以下是一般情况下使用 Pandas 清洗数据的常见步骤:_数据清洗和准备(pandas)字符串操作
文章浏览阅读2k次。不到三个月,我在CSDN的第一个一万
文章浏览阅读3.2w次,点赞5次,收藏12次。在做图片语义分割的项目,对图片数据标注后,又对数据进行扩增,然后倒入图片,进行模型训练,但是读图片的时候提示如下错误。 image = cv2.cvtColor(cv2.imread(path,-1), cv2.COLOR_BGR2RGB)cv2.error: OpenCV(3.4.3) /io/opencv/modules/imgproc/src/color.hpp:255: err..._> invalid number of channels in input image: > 'vscn::contains(scn)' > where
文章浏览阅读1.4k次。Dedecms5.7数据结构说明文档1、dede_addonarticle:附加文章表 表名:dede_addonarticle(ENGINE=MyISAM/CHARSET=utf8)说明:附加文章表 字段名说明描述具体参数aid文章ID_数据结构说明文件
文章浏览阅读215次。Spinner下拉列表一般使用非常简单。直接上代码1.布局文件 1 <LinearLayout ="http://schemas.android.com/apk/res/android" 2 xmlns:tools="http://schemas.android.com/tools" 3 android:layout..._setdropdownviewresource怎样自定义主题
文章浏览阅读80次。在centos上安装JDK,我安装的是JDK11。 查看centos上是否已经安装了JAVA: rpm -qa | grep java 如果已经安装了java,就卸载掉: rpm -e --nodeps 包名 接下来下载jdk包,下载地址:https://www.oracle.com/java/technologies/javase-jdk11-downloads.html 解压jdk: # 找到文件存放的目录,我的目录是/u...
文章浏览阅读3w次,点赞13次,收藏42次。本文总结了几种常用的MFC字符串分割的方法,以方便自己以后查阅,也希望能帮助到有需要帮助的人。1、CString 自带的函数Tokenize1CStringT Tokenize( _In_ PCXSTR pszTokens, _Inout_ int& iStart ) const_cstring分割字符串cstringarray存储
文章浏览阅读1.9k次,点赞2次,收藏5次。第一期1.雨中龙猫考查base64编码和图片源码隐写题目给出答案格式whalectf{xxx},将whalectf进行base64编码:d2hhbGVjdGY=notepad++打开源码搜索,发现并不能搜索到因为base64编码过程会重新以6位分组,所以whalectf后面的字母可能会对whalectf的编码影响,所以搜索前几位d2hhbGVj得到d2hhbGVjdGZ7TG进行解..._00000000.png ctf
文章浏览阅读4.1k次。在python中处理字符串中的空格和换行符 string中提供了很多方法处理字符串,有空格和换行符往往影响我们观看文本,下面介绍一种处理方法。 一、去除空格 strip() " xyz ".strip() # returns "xyz" " xyz ".lstrip()_python 解析带换行符的字符串
文章浏览阅读5.0k次,点赞2次,收藏18次。EasyMock是Apache许可下发布的Java开源测试框架,它可以和jUnit很好的继承在一起。该框架允许为测试驱动开发(TDD)或行为驱动开发(BDD)创建测试双重对象1。使用EasyMock只需导入相应的jar包即可,本篇用到的所有jar包和代码都可以在我的Github下载。 在这里我们用一个进行用户验证的servlet代码作为被测代码,这段代码来自我之前看过的一篇EasyMock教程2_使用easymock+junit对附件中的loginservlet进行测试: