解题思路

问题分析：

我们需要选择两个枢纽$H1$和$H2$，并将所有其他节点分配到$H1$或$H2$。

对于任意两个节点$A$和$B$，旅行距离为：$A$到$H1$ + $H1$到$H2$ + $H2$到$B$（如果$A$和$B$的枢纽不同），否则为 $A$到$H1$ + $H1$到$B$（如果$A$和$B$的枢纽相同）。

目标是找到$H1$、$H2$和分配方案，使得所有节点对的平均旅行距离最小。

关键步骤：

使用Floyd-Warshall算法计算所有节点对之间的最短路径，因为城市规模较小（$n$ <= $100$）。

枚举所有可能的枢纽对$H1$和$H2$（$H1$ < $H2$）。

对于每个枢纽对，尝试将所有节点分配到$H1$或$H2$，计算所有节点对的旅行距离的总和。

选择使总和最小的枢纽对和分配方案。如果有多个解，选择字典序最小的方案。

优化：

由于$n$较小，可以暴力枚举所有可能的$H1$和$H2$组合（共$C$($n$, $2$)种）。

对于每个$H1$和$H2$，计算所有节点的分配方案（每个节点分配到$H1$或$H2$），并计算总距离。

解题方法

Floyd-Warshall算法：

初始化距离矩阵$d$，$d[i][j]$表示节点i到节点j的最短距离。

对于每个中间节点$k$，更新所有$i$和$j$的最短距离。

枚举枢纽对：

对于所有$H1$和$H2$（$H1$ < $H2$），计算所有节点分配到$H1$或$H2$的总距离。

分配规则：

对于节点i，分配到H1或H2中距离更近的枢纽（因为这样能最小化旅行距离）。

选择最佳方案：

记录最小的总距离和对应的枢纽对及分配方案。

如果多个方案总距离相同，选择H1和H2编号较小的，且分配方案字典序最小的。

C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

const int INF = 1e9;

void floydWarshall(vector<vector<int> >& dist, int n) {
	for (int k = 1; k <= n; ++k) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (dist[i][k] + dist[k][j] < dist[i][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
				}
			}
		}
	}
}

void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int> > dist(n + 1, vector<int>(n + 1, INF));
	for (int i = 1; i <= n; ++i) {
		dist[i][i] = 0;
	}
	for (int i = 0; i < m; ++i) {
		int a, b, d;
		cin >> a >> b >> d;
		if (d < dist[a][b]) {
			dist[a][b] = dist[b][a] = d;
		}
	}
	floydWarshall(dist, n);
	
	double min_avg = INF;
	vector<int> best_assignment(n + 1, 0);
	int best_h1 = 1, best_h2 = 2;
	
	for (int h1 = 1; h1 <= n; ++h1) {
		for (int h2 = h1 + 1; h2 <= n; ++h2) {
			vector<int> assignment(n + 1);
			assignment[h1] = 0;
			assignment[h2] = 0;
			
			for (int i = 1; i <= n; ++i) {
				if (i == h1 || i == h2) continue;
				double cost_h1 = 0;
				double cost_h2 = 0;
				for (int j = 1; j <= n; ++j) {
					if (j == i) continue;
					int hj = (j == h1 || j == h2) ? j : assignment[j];
					if (hj == 0) hj = (j == h1) ? h1 : h2;
					int d1;
					if (hj == h1) {
						d1 = dist[i][h1] + dist[h1][j];
					} else {
						d1 = dist[i][h1] + dist[h1][h2] + dist[h2][j];
					}
					cost_h1 += d1;
					
					int d2;
					if (hj == h2) {
						d2 = dist[i][h2] + dist[h2][j];
					} else {
						d2 = dist[i][h2] + dist[h2][h1] + dist[h1][j];
					}
					cost_h2 += d2;
				}
				if (cost_h1 <= cost_h2) {
					assignment[i] = h1;
				} else {
					assignment[i] = h2;
				}
			}
			
			double total = 0;
			int count = 0;
			for (int i = 1; i <= n; ++i) {
				for (int j = 1; j <= n; ++j) {
					if (i == j) continue;
					count++;
					int hi = (i == h1 || i == h2) ? i : assignment[i];
					int hj = (j == h1 || j == h2) ? j : assignment[j];
					int d;
					if (hi == hj) {
						d = dist[i][hi] + dist[hi][j];
					} else {
						d = dist[i][hi] + dist[hi][hj] + dist[hj][j];
					}
					total += d;
				}
			}
			double avg = total / count;
			if (avg < min_avg) {
				min_avg = avg;
				best_h1 = h1;
				best_h2 = h2;
				best_assignment = assignment;
			} else if (avg == min_avg) {
				if (h1 < best_h1 || (h1 == best_h1 && h2 < best_h2)) {
					best_h1 = h1;
					best_h2 = h2;
					best_assignment = assignment;
				}
			}
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		if (i == best_h1 || i == best_h2) {
			cout << 0;
		} else {
			cout << best_assignment[i];
		}
		if (i < n) cout << " ";
	}
	cout << endl;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}