WA on line_like05、uni_01、uni_03。Submission
感谢！
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,dis[2][300000],u[300000],v[300000],len,cnt,d[300000],mn = 1e9,ans = 1e9;
vector<int>e[300000];
queue<int>q;
inline void sch(int w){
while(q.size()){
int u = q.front();
q.pop();
for(auto v : e[u]) if(dis[w][v] > dis[w][u] + 1) dis[w][v] = dis[w][u] + 1,q.push(v);
}
return;
}
int main(){
memset(dis,0x3f,sizeof(dis));
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i = 1;i <= m;i ++){
scanf("%d%d",&u[i],&v[i]);
e[u[i]].push_back(v[i]),e[v[i]].push_back(u[i]);
d[u[i]] ++,d[v[i]] ++;
}
dis[0][s] = 0,q.push(s),sch(0);
dis[1][t] = 0,q.push(t),sch(1);
len = dis[0][t];
for(int i = 1;i <= n;i ++) if(dis[0][i] + dis[1][i] == len) cnt ++;
if(cnt > len + 1){
printf("%d",len << 1);
return 0;
}
for(int i = 1;i <= n;i ++){
if(dis[0][i] + dis[1][i] == len + 1){
printf("%d",(len << 1) + 1);
return 0;
}
}
for(int i = 1;i <= n;i ++){
if(dis[0][i] + dis[1][i] == len && i != s && i != t && d[i] >= 3){
printf("%d",len + 1 << 1);
return 0;
}
}
for(int i = 1;i <= n;i ++) if(d[i] >= 3) mn = min(mn,min(dis[0][i],dis[1][i]));
for(int i = 1;i <= n;i ++) e[i].clear();
for(int i = 1;i <= m;i ++){
if(dis[0][u[i]] + dis[1][v[i]] + 1 != len && dis[1][u[i]] + dis[0][v[i]] != len) e[u[i]].push_back(v[i]),e[v[i]].push_back(u[i]);
}
memset(dis,0x3f,sizeof(dis));
dis[0][s] = 0,q.push(s),sch(0);
if(dis[0][t] != 0x3f3f3f3f) ans = min(ans,len + dis[0][t]);
if(mn != 1e9) ans = min(ans,(len + 2 << 1) + (mn << 2));
printf("%d",ans == 1e9 ? -1 : ans);
return 0;
}