Changsha Marathon

Question

Problem Description
　　Changsha is a beautiful city surrounded by mountains and rivers, forming a charming scenery. There are many tourist attractions in Changsha: Yuelu Academy, the predecessor of Hunan University, which is one of the four most famous academies in China. It was established in 976A.D. in Northern Song Dynasty. Juzizhou Island (Orange Isle) is the world's longest inland river isle which lies in Xiangjiang River and it is famous for the famous poet Qinyuanchun-Changsha written by Chairman Mao. Mawangdui is a famous archaeological site that contains the tombs of three people from the Western Han Dynasty. The tomb of Xin Zhui is best preserved among the three with a complete cosmetic set, lacquered pieces and finely woven silk garments. Huogongdian represents the Huxiang culture and Chuwu culture, Hunan’s geography culture and Hunan’s distinctive food culture. Tourists can have a taste of typical Hunan cuisine in it.
　　Every year the city holds a marathon. When planning the route, the organizers wish to go pass some tourist attractions to make it more enjoyable to attract more athletes and audience. Changsha can be treated as a graph consisted of N intersections and many bidirectional roads. A road connects two intersections i and j with length Wi,j. However, to reduce the impact to the daily traffic, only N-1 roads specified by the local government which can connect all N intersections are allowed to be used as the route. And the intersections with only one adjacent intersection are on the west bank of Xiangjiang River and there are ferries only at these intersections. The marathon starts at the intersection called Red East Square (marked as S) in Hunan University by convention. The organizers do not want the route pass any road twice, so the marathon has to be separated into two sections, the first section and the second section. Two different points have to be selected from intersections on the bank to act as the half end point S1 and the half starting point S2. The first section starts from S and end in S1. The second section starts from S2 and end in S. The organizer will use ferryboats to transport athletes from S1 to S2 as required by the government.
　　Considering the safety, some supply points are to be set on some intersections on each half section and there must be a supply point set on S, S1 and S2.
According to scientific research, the most suitable distance between two adjacent supply points is L and the organizers want to minimize the evaluation of the route. For each section, the evaluation from the starting point to rest point i is marked as Ei, and where j is the previous supply point on the route,　　means the sum of the roads’ length on the route from intersection j to i. The evaluation of the starting point is zero. The evaluation of a section equals to the evaluation from its starting point to end point.
　　Your task is to select S1, S2, and the supply points to minimize the total evaluation of both sections.

Input
　　There are multiple test cases.
　　For each test case the first line contains two integers, N, L. (1<=N<=20000, 1<=L<=109)
　　The next N-1 lines with 3 integers, U, V, W, describes that a bidirectional road connects intersection U and V with distance W. (1<=U, V<=N, 1<=W<=103)
Red East Square (S) is always numbered 1. The input will finish with the end of file.

Output
　　For each case the output contains only one line, the evaluation of the best plan rounded to the second digit after the decimal point. If there is no solution, output -1.

Sample Input
7 4
1 2 2
1 3 7
1 4 3
2 5 6
2 6 5
3 7 8

Sample Output
7.00

Answer 1

/*from:  https://blog.csdn.net/spark_007/article/details/9017511*/
#include <iostream>

#include <cassert>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <vector>

#include <map>

using namespace std;

#define inf 9e99

#define eps 1e-9

#define x first

#define y second

#define pb push_back

#define sz(a) int(a.size())

#define rep(i,a,b) for(int i=a;i<=b;i++)

template<class T> inline void gmin(T&a,T b) {if(a>b)a=b;}

template<class T> inline T sqr(T a) {return a*a;}



#define N 20020

vector<int> to[N],len[N];

int col[N],n;

double sum[N],L;

#define is_leaf(x) sz(to[x])==1 && sum[to[x][0]]<sum[x]



void pre_dfs(int x) {

    rep(i,0,sz(to[x])-1) {

        int y=to[x][i];

        if (sum[y]<0) {

            col[y]=x==1?y:col[x];

            sum[y]=sum[x]+len[x][i];

            pre_dfs(y);

        }

    }

}



vector<int> path,tmp[N];

double dp1[N],ans1[N];

double dp2[N],ans2[N];



double Y1(int j) {return dp1[j]+sqrt(dp1[j])+sqr(sum[j])+2.0*sum[j]*L;}

double Y2(int j) {return dp2[j]+sqrt(dp2[j])+sqr(sum[j])-2.0*sum[j]*L;}

double slope1(int j,int k) {return (Y1(j)-Y1(k))/(sum[j]-sum[k]);}

double slope2(int j,int k) {return (Y2(j)-Y2(k))/(sum[j]-sum[k]);}

double calc(double Ej,double sum) {return Ej+sqrt(Ej)+sum*sum;}



struct Queue {

    map<double,int> q;

    void clear() {q.clear();}

    int size() {return q.size();}

    int front() {return sz(q)?q.begin()->y:0;}

    int front2() {return sz(q)?(++q.begin())->y:0;}

    int back() {return sz(q)?q.rbegin()->y:0;}

    int back2() {return sz(q)?(++q.rbegin())->y:0;}

    void pop_front() {q.erase(q.begin());}

    void pop_back() {q.erase(--q.end());}

    void insert(int x,int y) {q[x]=y;}



    void merge(Queue *b) {

        while (b->size()) {

            int cur=b->front();

            b->pop_front();

            if (q.find(sum[cur])!=q.end()) {

                int j=cur,k=q[sum[cur]];

                if (Y2(j)>=Y2(k)) continue;

            }

            q[sum[cur]]=cur;

            if (sz(q)<=2) continue;



            map<double,int>::iterator i=q.find(sum[cur]),l1,l2,r1,r2;

            if (i!=q.begin() && i!=(--q.end())) {

                l1=i, l1--;

                r1=i, r1++;

                if (slope2(l1->y,i->y)>=slope2(i->y,r1->y)) {

                    q.erase(i);

                    continue;

                }

            }

            while (i!=q.begin() && i!=(++q.begin())) {

                l1=i, l1--;

                l2=l1, l2--;

                if (slope2(l2->y,l1->y)<=slope2(l1->y,i->y)) break;

                q.erase(l1);

            }

            while (i!=(--q.end()) && i!=(--(--q.end()))) {

                r1=i, r1++;

                r2=r1, r2++;

                if (slope2(i->y,r1->y)<=slope2(r1->y,r2->y)) break;

                q.erase(r1);

            }

        }

    }

} q1,*q2[N];



void first_run(int x) {

    rep(i,0,sz(to[x])-1) {

        int y=to[x][i];

        if (sum[y]<=sum[x]) continue;

        path.pb(y);



        tmp[x].clear();

        while (sz(q1)>=2 && slope1(q1.front(),q1.front2())<=2.0*sum[y] ) {

            tmp[x].pb(q1.front());

            q1.pop_front();

        }

        dp1[y]=calc(dp1[q1.front()],sum[y]-sum[q1.front()]-L);



        while (sz(q1)>=2 && slope1(q1.back2(),q1.back())>=slope1(q1.back(),y) ) {

            tmp[x].pb(q1.back());

            q1.pop_back();

        }

        q1.insert(sum[y],y);



        first_run(y);



        q1.pop_back();

        rep(i,0,sz(tmp[x])-1)

            q1.insert(sum[tmp[x][i]],tmp[x][i]);

        path.pop_back();

    }

    if (is_leaf(x)) {

        gmin(ans1[col[x]],dp1[x]);

    }

}



void merge(Queue *&a,Queue *&b) {

    if (b->size() < a->size()) {

        a->merge(b);

    } else {

        b->merge(a);

        a=b;

    }

}



double get_val(Queue *q,int x) {

    while (q->size()>=2 && slope2(q->back(),q->back2())>=2.0*sum[x]) q->pop_back();

    dp2[x]=calc(dp2[q->back()],sum[q->back()]-sum[x]-L);

    while (q->size()>=2 && slope2(q->front2(),q->front())<=slope2(q->front(),x) ) q->pop_front();

    return dp2[x];

}



void second_run(int x) {

    q2[x]=new Queue;

    rep(i,0,sz(to[x])-1){

        int y=to[x][i];

        if (sum[y]<=sum[x]) continue;

        second_run(y);

        if (x==1) {

            gmin(ans2[y],get_val(q2[y],x));

        } else {

            merge(q2[x],q2[y]);

        }

    }

    if (x!=1) {

        dp2[x]=is_leaf(x)?0:get_val(q2[x],x);

        q2[x]->insert(sum[x],x);

    }

}



double get_answer() {

    vector<int> part;

    rep(i,2,n) if (col[i]==i) part.pb(i);



    double min1=inf,min2=inf;

    int pos1;

    rep(i,0,sz(part)-1) {

        if (min1>ans2[part[i]]) {

            min2=min1;

            min1=ans2[part[i]];

            pos1=i;

        } else

        if (min2>ans2[part[i]]) {

            min2=ans2[part[i]];

        }

    }

    double res=inf;

    rep(i,0,sz(part)-1)

        gmin(res,ans1[part[i]]+(pos1==i?min2:min1));

    return res;

}



int main() {

    //freopen("Marathon.in","r",stdin);

    //freopen("testMarathon.out","w",stdout);

    while (~scanf("%d%lf",&n,&L)) {

        rep(i,1,n) {

            to[i].clear();

            len[i].clear();

        }

        rep(i,1,n-1) {

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            to[u].pb(v);

            to[v].pb(u);

            len[u].pb(w);

            len[v].pb(w);

        }

        if (sz(to[1])<2) {

            puts("-1");

            continue;

        }



        fill(sum+2,sum+n+1,-1);

        pre_dfs(1);



        fill(dp1+2,dp1+n+1,inf);

        fill(dp2+1,dp2+n+1,inf);

        fill(ans1,ans1+n+1,inf);

        fill(ans2,ans2+n+1,inf);



        path.clear();

        path.pb(1);

        q1.clear();

        q1.insert(0,1);



        first_run(1);

        second_run(1);

        printf("%.2lf\n",get_answer());

    }

    return 0;

}