这是我的第 1 版代码:
#include<bits/stdc++.h>
#define N (int)(3e3+1e1)
using namespace std;
int n,m,dis1[N],dis2[N],dis3[N],u,v,s1,t1,s2,t2,ans=-1;
bool vis1[N],vis2[N],vis3[N];
vector<int> G[N];
struct D{int at,d;};
void bfs1(int x){
memset(dis1,-1,sizeof(dis1));
queue<D> q;
q.push({x,0});
vis1[x]=true;
while(!q.empty()){
D t=q.front();
q.pop();
dis1[t.at]=t.d;
for(int i=0;i<G[t.at].size();i++){
if(!vis1[G[t.at][i]]){
vis1[G[t.at][i]]=true;
q.push({G[t.at][i],t.d+1});
}
}
}
}
void bfs2(int x){
memset(dis2,-1,sizeof(dis2));
queue<D> q;
q.push({x,0});
vis2[x]=true;
while(!q.empty()){
D t=q.front();
q.pop();
dis2[t.at]=t.d;
for(int i=0;i<G[t.at].size();i++){
if(!vis2[G[t.at][i]]){
vis2[G[t.at][i]]=true;
q.push({G[t.at][i],t.d+1});
}
}
}
}
void bfs3(int x){
memset(dis3,-1,sizeof(dis3));
queue<D> q;
q.push({x,0});
vis3[x]=true;
while(!q.empty()){
D t=q.front();
q.pop();
dis3[t.at]=t.d;
for(int i=0;i<G[t.at].size();i++){
if(!vis3[G[t.at][i]]){
vis3[G[t.at][i]]=true;
q.push({G[t.at][i],t.d+1});
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
cin>>s1>>t1>>s2>>t2;
bfs1(1);
bfs2(s1);
bfs3(s2);
for(int i=1;i<=n;i++){
if(dis1[i]+dis2[i]<=t1 && dis1[i]+dis3[i]<=t2) ans=max(ans,m-(dis2[i]+dis3[i]+dis1[i]));
}
cout<<ans<<endl;
return 0;
}
(bfs是从某题抄过来的
然后WA,20pts。
但是——
#include<bits/stdc++.h>
#define N (int)(3e3+1e1)
using namespace std;
int n,m,dis1[N],dis2[N],dis3[N],u,v,s1,t1,s2,t2,ans=-1;
bool vis1[N],vis2[N],vis3[N];
vector<int> G[N];
struct D{int at,d;};
void bfs1(int x){
memset(dis1,0x3f,sizeof(dis1));
queue<D> q;
q.push({x,0});
vis1[x]=true;
while(!q.empty()){
D t=q.front();
q.pop();
dis1[t.at]=t.d;
for(int i=0;i<G[t.at].size();i++){
if(!vis1[G[t.at][i]]){
vis1[G[t.at][i]]=true;
q.push({G[t.at][i],t.d+1});
}
}
}
}
void bfs2(int x){
memset(dis2,0x3f,sizeof(dis2));
queue<D> q;
q.push({x,0});
vis2[x]=true;
while(!q.empty()){
D t=q.front();
q.pop();
dis2[t.at]=t.d;
for(int i=0;i<G[t.at].size();i++){
if(!vis2[G[t.at][i]]){
vis2[G[t.at][i]]=true;
q.push({G[t.at][i],t.d+1});
}
}
}
}
void bfs3(int x){
memset(dis3,0x3f,sizeof(dis3));
queue<D> q;
q.push({x,0});
vis3[x]=true;
while(!q.empty()){
D t=q.front();
q.pop();
dis3[t.at]=t.d;
for(int i=0;i<G[t.at].size();i++){
if(!vis3[G[t.at][i]]){
vis3[G[t.at][i]]=true;
q.push({G[t.at][i],t.d+1});
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
cin>>s1>>t1>>s2>>t2;
bfs1(1);
bfs2(s1);
bfs3(s2);
for(int i=1;i<=n;i++){
if(dis1[i]+dis2[i]<=t1 && dis1[i]+dis3[i]<=t2) ans=max(ans,m-(dis2[i]+dis3[i]+dis1[i]));
}
cout<<ans<<endl;
return 0;
}
我们只要把初始化的 −1 改成 0x3f 就能过!
但是鉴于我用的是 BFS 求最短路所以初始化成什么应该没有区别吧。。。非常玄学,求大佬解答