WA on#7求调

#include <bits/stdc++.h>
using namespace std;
int n,m,k,s1,s2,t1,t2,dis[5010][5010],U,V,mn=0x3f3f3f3f,L1=0x3f3f3f3f,L2=0x3f3f3f3f;
vector<int >edge[5010];
bool vis[5010];
queue<int >q;
void bfs(int x){
	memset(vis,0,sizeof(vis));
	q.push(x);
	vis[x]=1;
	dis[x][x]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<edge[u].size();i++){
			int v=edge[u][i];
			if(!vis[v]){
				q.push(v);
				dis[x][v]=dis[x][u]+1;
				vis[v]=1;
			}
		}
	}
}
double calc(int x,int len){
	int a=x/len;
	int b=x%len;
	return (len-b)*1.0/(a+1)+b*1.0/(a+2);
}
double f(int x){
	if(L1==0&&L2==0)
		return 0;
	if(L1==0)
		return calc(x,L2)*2;
	if(L2==0)
		return calc(k-x,L1);
	return calc(k-x,L1)+calc(x,L2)*2;
}
int main(){
	memset(dis,0x3f,sizeof(dis));
	cin>>n>>m>>k;
	while(m--){
		int x,y;
		cin>>x>>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
		bfs(i);
	cin>>s1>>t1>>s2>>t2;
	if(s1==t1&&s2==t2){
		cout<<"0.000000000";
		return 0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(i==j)
				continue;
			long long Dis=dis[s1][i]+dis[s2][i]+dis[i][j]*2+dis[j][t1]+dis[j][t2];
			if(mn>Dis){
				mn=Dis;
				U=i;
				V=j;
				L1=dis[s1][U]+dis[s2][U]+dis[V][t1]+dis[V][t2];
				L2=dis[U][V];
			}
			Dis=dis[s1][i]+dis[s2][j]+dis[i][j]*2+dis[j][t1]+dis[i][t2];
			if(mn>Dis){
				mn=Dis;
				U=i;
				V=j;
				L1=dis[s1][U]+dis[s2][V]+dis[V][t1]+dis[U][t2];
				L2=dis[U][V];
			}
		}
	int l=0,r=k;//cout<<U<<" "<<V<<" "<<L1<<" "<<L2<<"\n";	
	while(l<=r){//cout<<l<<" "<<r<<"\n";
		int mid1=l+(r-l)/3,mid2=r-(r-l)/3;
		if(f(mid1)>f(mid2)){
			l=mid1+1;
		}
		else{
			r=mid2-1;
			
		}
			
		/*if(r-l<=10){
			double ans=0x3f3f3f3f;
			for(int i=l;i<=r;i++){
				ans=min(ans,f(i));
			}
			printf("%.9lf",ans);
			return 0;
		}*/
	}
	printf("%.15lf",min(f(l),calc(k,dis[s1][t1]+dis[s2][t2])));
}