File size: 1,524 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 | #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;
if (n <= 1) {
cout << "!" << "\n" << flush;
continue;
}
vector<vector<int>> dist(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
cout << "? " << i << " " << j << "\n" << flush;
int d;
if (!(cin >> d)) return 0;
dist[i][j] = dist[j][i] = d;
}
}
vector<tuple<int,int,int>> edges;
edges.reserve(n - 1);
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
bool isEdge = true;
int dij = dist[i][j];
for (int k = 1; k <= n; ++k) {
if (k == i || k == j) continue;
if (dist[i][k] + dist[k][j] == dij) {
isEdge = false;
break;
}
}
if (isEdge) {
edges.emplace_back(i, j, dij);
}
}
}
cout << "!";
for (auto &e : edges) {
int u, v, w;
tie(u, v, w) = e;
cout << " " << u << " " << v << " " << w;
}
cout << "\n" << flush;
}
return 0;
} |