题解:
二分+bfs,二分最长距离,这个题在bfs时使用堆来处理会变得比较简单,优先去走油量较多的那个点(某个点当前能量最大一定“有利于”接下来点的转移),每当遇到特殊点的时候,把油量加满即可。
走到终点即返回true。没走到返回false即可。
代码:
/*Keep on going Never give up*/
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#include<iostream>
//#include<string>
//#include<cmath>
//#include<vector>
//#include<algorithm>
//#include<queue>
//#include<string.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+10;
const int mo=1000;
bool isvis[maxn];
int head[maxn<<1];
struct node{
int to,next;
}edge[maxn<<1];
int cnt=0;
inline void add(int u,int v){
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int s,t;int n,m,k;
int dis[maxn];
struct xx{
int first,second;
bool operator < (const xx & b) const{
return first<b.second;
}
};
bool bfs(int x){
//memset(visited,false,sizeof visited);
memset(dis,-1,sizeof dis);
priority_queue<xx> q;
dis[s]=x;
q.push({s,x});
while(!q.empty()){
auto temp=q.top();q.pop();
if(temp.second==0) continue;
for(int i=head[temp.first];~i;i=edge[i].next){
int to=edge[i].to;
int w=temp.second-1;
if(to==t) return true;
if(isvis[to]) w=x;
if(dis[to]<w){
dis[to]=w;
q.push({to,dis[to]});
}
}
}
// for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
// cout<<endl;
return false;
}
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
signed main(){
memset(isvis,false,sizeof isvis);
memset(head,-1,sizeof head);
cin>>n>>m>>k;
for(int i=0;i<k;i++){
int x;
x=read();
isvis[x]=true;
}
for(int i=0;i<m;i++){
int u,v;
u=read(),v=read();
add(u,v);add(v,u);
}
cin>>s>>t;
//cout<<bfs(3)<<endl;
int l=1,r=2e5+10,ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(bfs(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
//cout<<mid<<endl;
}
cout<<ans<<endl;
}

京公网安备 11010502036488号