Description
在一条边上求一个点,使得这个点到所有点的最长的最短距离 最短. (n leqslant 10^5)
Sol
Dijkstra+扫描线+单调队列.
这个好像叫什么最小直径生成树?不过变成了在一个边上...
对于一个点,我们可以求出当分割点在哪个位置的时候,它应该到 (A) ,什么时候它应该到 (B) .
(dis_A(i)+t leqslant dis_B(j)+(dis_{AB}-t))
移项得 (tleqslant frac{dis_B(i)-dis_A(i)+dis_{AB}}{2})
这样就把线段 (AB) 分成了几个区间,枚举区间,然后分别用两个单调队列维护一下到分割点左右到 (A,B) 距离的最大值.
对于一个区间,我们可以 (O(1)) 的求出在这个区间应该选择哪个点作为分割点,因为两边的点都是确定的最大距离也知道,然后统计答案就可以了.
Code
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define mpr(a,b) make_pair(a,b)
#define debug(a) cout<<#a<<"="<<a<<" "
#define Fst first
#define Sec second
typedef long long LL;
typedef pair< LL,int > pr;
const int N = 100005;
LL T,n,m,k,A,B,X;
vector<pr> g[N];
LL ds[N],dt[N];
pair< double,int > p[N];double lm[N];
pair< double,double > ans;
int q1[N],q2[N],h1,h2,t1,t2;
priority_queue<pr,vector<pr>,greater<pr> > q;
inline LL in(LL x=0,char ch=getchar()){ while(ch>'9' || ch<'0') ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x; }
void clr(){
t1=t2=0,h1=h2=1;ans=mpr(1e18,-1);
for(int i=0;i<N;i++) g[i].clear();
}
void Up(int i,int j){
double l=max(min((X+ds[j]+dt[i])/2.0-ds[j],lm[j]),lm[i]),tmp=max(ds[j]+l,X-l+dt[i]);
// debug(i),debug(j),debug(dt[i]),debug(ds[j]),debug((X+ds[j]+dt[i])/2.0-dt[i]),debug(lm[i]),debug(lm[j]),debug(l),debug(tmp)<<endl;
if(tmp < ans.Fst||(tmp == ans.Fst && l<ans.Sec)) ans=mpr(tmp,l);
}
void Dijkstra(int s,LL *d){
static bool b[N];memset(b,0,sizeof(b));for(int i=1;i<=n;i++) d[i]=1000000000000000000LL;
d[s]=0,q.push(mpr(0,s));
for(int u;!q.empty();){
u=q.top().Sec,q.pop();if(b[u]) continue;b[u]=1;
for(int i=0;i<g[u].size();i++){
LL p=g[u][i].Fst;int v=g[u][i].Sec;
if(d[u]+p < d[v]) d[v]=d[u]+p,q.push(mpr(d[v],v));
}
}
}
int main(){
for(T=in();T--;){
clr();
n=in(),m=in(),k=in();
for(int i=1,u,v,x;i<=m;i++){
u=in(),v=in(),x=in();
g[u].push_back(mpr(x,v)),g[v].push_back(mpr(x,u));
if(i == k) A=u,B=v,X=x;
}
Dijkstra(A,ds),Dijkstra(B,dt);
// cout<<X<<endl;
// for(int i=1;i<=n;i++) cout<<ds[i]<<" ";cout<<endl;
// for(int i=1;i<=n;i++) cout<<dt[i]<<" ";cout<<endl;
for(int i=1;i<=n;i++) p[i]=mpr((dt[i]-ds[i]+X)/2.0,i),lm[i]=(dt[i]-ds[i]+X)/2.0;
sort(p+1,p+n+1);
// for(int i=1;i<=n;i++) printf("%lf %d
",p[i].Fst,p[i].Sec);
for(int i=1;i<=n;i++){
while(h2<=t2 && ds[q2[t2]] <= ds[p[i].Sec]) t2--;
q2[++t2]=p[i].Sec;
}
// cout<<ds[q2[h2]]+X<<endl;
ans=mpr(ds[q2[h2]],0);
for(int i=1,r;i<=n;i=r+1){
r=i;
while(p[r].Fst == p[r+1].Fst) r++;
/// debug(r)<<endl;
for(int j=i;j<=r;j++){ while(h1<=t1 && dt[q1[t1]] <= dt[p[j].Sec]) t1--;q1[++t1]=p[j].Sec; }
for(int j=i;j<=r;j++) if(q2[h2] == p[j].Sec) h2++;
// debug(q1[h1]),debug(q2[h2])<<endl;
Up(q1[h1],q2[h2]);
}
if(dt[q1[h1]]<ans.Fst) ans=mpr(dt[q1[h1]],X);
printf("%.5lf %.5lf
",ans.Sec,ans.Fst);
}
return 0;
}