摧毁 做题记录
因为边权为 \(1\)，所以两条路最多只有一条交集。因为 \(n \le 3000\)，所以我们跑出全源最短路，枚举交集的端点，然后计算即可。时间复杂度 \(O(n(n+m))\)。
点击查看代码
int n,m;
int l1,s1,t1,l2,s2,t2;
vector<int>G[maxn];
int dis[maxn][maxn];
bool vis[maxn];
void bfs(int st) {
m0(vis);
queue<pair<int,int> >q;
q.push({st,0});
while(!q.empty()) {
auto [u,d]=q.front(); q.pop();
if(vis[u]) continue;
vis[u]=1; dis[st][u]=d;
for(auto v:G[u]) {
if(!vis[v])
q.push({v,d+1});
}
}
}
signed main() {
mem(dis,0x3f);
in2(n,m);
For(i,1,n) dis[i][i]=0;
For(i,1,m) {
int u,v;
in2(u,v);
pb(G[u],v);
pb(G[v],u);
}
in3(s1,t1,l1);
in3(s2,t2,l2);
// For(k,1,n) For(i,1,n) For(j,1,n) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
For(i,1,n) {
bfs(i);
}
int ans=1e9;
if(dis[s1][t1]<=l1&&dis[s2][t2]<=l2) ans=dis[s1][t1]+dis[s2][t2];
// For(i,1,n) For(j,1,n) cout<<dis[i][j]<<(j==n?'\n':' ');
For(i,1,n) For(j,1,n) {
int d1=dis[i][j]+min(dis[s1][i]+dis[j][t1],dis[s1][j]+dis[i][t1]);
int d2=dis[i][j]+min(dis[s2][i]+dis[j][t2],dis[s2][j]+dis[i][t2]);
if(d1<=l1&&d2<=l2&&d1+d2-dis[i][j]<ans) {
ans=d1+d2-dis[i][j];
// cout<<d1<<' '<<d2<<' '<<i<<' '<<j<<'\n';
}
}
cout<<(ans==1e9?-1:m-ans);
}