File size: 2,563 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
while (T--) {
int n;
if (!(cin >> n)) return 0;
vector<long long> D;
D.assign(1LL * n * n, 0);
auto idx = [n](int i, int j) { return 1LL * (i - 1) * n + (j - 1); };
// Read full n x n distance matrix
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
long long x;
cin >> x;
D[idx(i, j)] = x;
}
}
vector<int> order(n);
iota(order.begin(), order.end(), 1);
sort(order.begin(), order.end(), [&](int a, int b){
return D[idx(1, a)] < D[idx(1, b)];
});
vector<char> inserted(n + 1, false);
inserted[order[0]] = true; // root
vector<tuple<int,int,long long>> edges;
for (int t = 1; t < n; ++t) {
int v = order[t];
long long dv = D[idx(1, v)];
int best = -1;
long long bestd = -1;
for (int k = 0; k < t; ++k) {
int u = order[k];
if (!inserted[u]) continue;
long long du = D[idx(1, u)];
long long duv = D[idx(u, v)];
if (du + duv == dv) {
if (du > bestd) {
bestd = du;
best = u;
}
}
}
if (best == -1) {
// Fallback: connect to closest previous node if invariant fails
long long mn = LLONG_MAX;
int ubest = order[0];
for (int k = 0; k < t; ++k) {
int u = order[k];
if (!inserted[u]) continue;
long long duv = D[idx(u, v)];
if (duv < mn) {
mn = duv;
ubest = u;
}
}
best = ubest;
}
long long w = D[idx(best, v)];
edges.emplace_back(best, v, w);
inserted[v] = true;
}
// Output in one line with '!' prefix as described
cout << "!";
for (auto &e : edges) {
int u, v; long long w;
tie(u, v, w) = e;
cout << " " << u << " " << v << " " << w;
}
cout << "\n";
cout.flush();
}
return 0;
} |