Minimum Diameter Spanning Tree (MDST) - SPOJ - http://www.spoj.com/problems/MDST/

mdst.cc

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN    1000+1
#define INF     100000000

int N;

bool Graph[MAXN][MAXN];
int dist[MAXN][MAXN];

int convex[MAXN];
int temp[MAXN];

int U;

bool cmp(const int A, const int B) {
    return dist[U][A] < dist[U][B];
}

void solve() {
    scanf("%d", &N);

    for (int i = 1; i <= N; ++ i) {
        for (int j = 1; j <= N; ++ j) {
            Graph[i][j] = false;
            dist[i][j] = INF;
        }
        dist[i][i] = 0;
    }

    for (int i = 1; i <= N; ++ i) {
        int x, l;
        scanf("%d%d", &x, &l);
        while (l --) { 
            int y;
            scanf("%d", &y);
            Graph[x][y] = Graph[y][x] = true;
            dist[x][y] = dist[y][x] = 2;
        }
    }

    if (N == 1) {
        printf("0\n");
        return;
    }

    for (int k = 1; k <= N; ++ k)
        for (int i = 1; i <= N; ++ i)
            for (int j = 1; j <= N; ++ j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    int diameter = INF;

    for (int w = 1; w <= N; ++ w)
        temp[w - 1] = w;
    for (int u = 1; u < N; ++ u) {
        U = u;
        sort(temp, temp + N, cmp);
        for (int v = u + 1; v <= N; ++ v) {
            if (!Graph[u][v]) continue;
            int ptr = 0;
            for (int i = 0; i < N; ++ i) {
                while (ptr && dist[v][convex[ptr - 1]] <= dist[v][temp[i]]) -- ptr;
                if (ptr && dist[u][convex[ptr - 1]] == dist[u][temp[i]] && dist[v][convex[ptr - 1]] >= dist[v][temp[i]]) continue;
                convex[ptr] = temp[i]; ++ ptr;
            }
            diameter = min(diameter, dist[v][convex[0]]);
            diameter = min(diameter, dist[u][convex[ptr - 1]]);

            for (int i = 1; i < ptr; ++ i)
                diameter = min(diameter, (2 + dist[u][convex[i - 1]] + dist[v][convex[i]]) >> 1);
        }
    }

    printf("%d\n", diameter);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T --) solve();
    return 0;
}