Codeforces 266D BerDonalds

奇怪的題目名字，應該是學 Mcdonalds 的吧

如果他說只能在點上，就好辦了

直接做一次Floyd，就可以得到答案了

但！問題就在於你可以位於其中的無限多個點的其中一個

前面都很無腦，接下來就需要用到好腦袋惹～
（要了解很簡單，但要想到有點難＝＝）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

其實可以這樣想，先想對於一個邊你要到所有人的最短距離

就是，這邊的兩端為 a, b，min( x + dis[ a ][ i ], c - x + dis[ b ][ i ] )對所有 i 的max要最小

直接做枚舉可能答案的動作，是最簡單也是最方便的（比起二分搜或三分搜）

所以就先朝著枚舉答案的方向思考（也就是哪些中間點要試放看看這樣）

假設所有點的集合是這樣（a, b, c, d, e...），將他分成兩個集合A, B

A代表要讓這個邊的 a 去連會是min， B代表要讓這個邊的 b 去連會是min

也就是我們假定對A集合min(剛剛那團) 會是 a 的比較小，B也是同樣的道理

而若是這麼一回事的話，拿A的最大值，B的最大值，就可以組出想要的 x 了。

枚舉A的最大值，然後求B（補集）的最大值，弄出所有可能的X，再取最小的即可。

//By momo
#include
#include
#include
#define N 210
#define INF 999999999
using namespace std;

double ans = INF;
int n, m, dis[N][N];
int a[N*N], b[N*N], c[N*N];
struct pairr{ int a, b; }d[N];
bool comp(pairr x, pairr y){ return x.a > y.a; }

int main (){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) dis[i][j] = INF;
        dis[i][i] = 0;
    }
    for(int i = 0; i < m; i++){
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        a[i]--, b[i]--;
        dis[a[i]][b[i]] = dis[b[i]][a[i]] = c[i];
    }
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dis[i][j] = min(dis[i][j],
                            dis[i][k] + dis[k][j]);
    for(int i = 0; i < m; i++){
        int C = c[i];
        for(int j = 0; j < n; j++){
            d[j].a = dis[a[i]][j];
            d[j].b = dis[b[i]][j];
        }
        sort(d, d+n, comp);
        int M = d[0].b; ans = min(ans, 1.0*d[0].a);
        for(int j = 1; j < n; j++){
            double val;
            if(d[j].a > M - C && M + C > d[j].a)
                val = (d[j].a+M+C) / 2.0;
            else val = max(d[j].a, M);
            ans = min(ans, val);
            M = max(M, d[j].b);
        }
    }
    printf("%lf\n", ans);
}