Codeforces1307D. Cow and Fields
2024-10-08 13:02:47
对于本题,最短路,考虑bfs,那么我们可以跑2次bfs,求出每个点到1与n的最短路,设为x_a, x_b,那我们可以把问题转换成max(min{x_a+y_b,x_b+y_a}+1)(x,y属于1到n),我们假设x_a+y_b<=x_b+y_a,那我们就是求出x_a+y_b的最大值,不等式转换一下,x_a-x_b<=y_a-y_b,那我们可以根据该式sort一下,每次更新一下最大的x_a,然后x_a+y_b+1就是最大值
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long LL;
typedef pair<int,int> pii; const int maxn = 2e5+; vector<int> G[maxn];
int d1[maxn], d2[maxn];
bool ks[maxn]; void bfs(int *dist, int s) {
dist[s] = ;
queue<int> q;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto v : G[u]) {
if(dist[v] == -) {
q.push(v);
dist[v] = dist[u] + ;
}
}
}
} void run_case() {
int n, m, k;
cin >> n >> m >> k;
memset(d1, -, sizeof(d1)), memset(d2, -, sizeof(d2));
for(int i = ; i < k; ++i) {
int t; cin >> t;
ks[t] = true;
}
for(int i = ; i < m; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
bfs(d1, );
bfs(d2, n);
vector<pii> v;
for(int i = ; i <= n; ++i) if(ks[i]) v.emplace_back(d1[i], d2[i]);
sort(v.begin(), v.end(), [&](const pii &a, const pii &b) {
return a.first - a.second < b.first - b.second;
});
int ans = , mx = v[].first;
for(int i = ; i < v.size(); ++i) {
ans = max(ans, mx++v[i].second);
mx = max(mx, v[i].first);
}
cout << min(ans, d1[n]);
} int main() {
ios::sync_with_stdio(false), cin.tie();
//cout.setf(ios_base::showpoint);cout.precision(10);
//int t; cin >> t;
//while(t--)
run_case();
cout.flush();
return ;
}
最新文章
- JavaScript学习笔记(1))——————call,apply方法
- 欧拉计划之题目9:找出唯一的满足a + b + c = 1000的毕达哥拉斯三元组{a, b, c}
- qtp 设置等待时间
- 在iOS App的图标上显示版本信息
- File List()列出文件目录
- 关于String的hashCode
- 字符串(LCT,后缀自动机):BZOJ 2555 SubString
- 《STL源代码剖析》---stl_alloc.h阅读笔记
- MSSQL:修改tempdb设置增加DW性能
- EasyUI的后台界面
- Building Your First EDM
- PHP+nginx 线上服务研究(一)
- Java_循环
- RabbitMQ 学习笔记
- noj 算法 八数码问题
- week7
- MyEclipse2015优化
- 使用Webupload上传图片到FastDFS分布式文件系统
- windows清空电脑的DNS缓存
- [LeetCode] 704. Binary Search_Easy tag: Binary Search