对于本题,最短路,考虑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 ;
}

最新文章

  1. JavaScript学习笔记(1))——————call,apply方法
  2. 欧拉计划之题目9:找出唯一的满足a + b + c = 1000的毕达哥拉斯三元组{a, b, c}
  3. qtp 设置等待时间
  4. 在iOS App的图标上显示版本信息
  5. File List()列出文件目录
  6. 关于String的hashCode
  7. 字符串(LCT,后缀自动机):BZOJ 2555 SubString
  8. 《STL源代码剖析》---stl_alloc.h阅读笔记
  9. MSSQL:修改tempdb设置增加DW性能
  10. EasyUI的后台界面
  11. Building Your First EDM
  12. PHP+nginx 线上服务研究(一)
  13. Java_循环
  14. RabbitMQ 学习笔记
  15. noj 算法 八数码问题
  16. week7
  17. MyEclipse2015优化
  18. 使用Webupload上传图片到FastDFS分布式文件系统
  19. windows清空电脑的DNS缓存
  20. [LeetCode] 704. Binary Search_Easy tag: Binary Search

热门文章

  1. The Preliminary Contest for ICPC Asia Xuzhou 2019 J Random Access Iterator (树形DP)
  2. PTA的Python练习题(十七)
  3. Etcd Learning Notes
  4. dp(小猪存钱罐)
  5. IE浏览器清浮动
  6. python学习之HTML
  7. ES6:字面量的增强写法
  8. SSH 维持权限(好用)
  9. EAP认证
  10. webpack原理类型问题