File size: 2,132 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 | #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';
cout.flush();
continue;
}
const long long INF = (1LL << 60);
vector<long long> key(n + 1, INF);
vector<int> parent(n + 1, -1);
vector<char> inMST(n + 1, false);
vector<tuple<int, int, long long>> edges;
int root = 1;
inMST[root] = true;
int inCount = 1;
// Initial queries from root to all other vertices
for (int v = 1; v <= n; ++v) {
if (v == root) continue;
cout << "? " << root << " " << v << '\n';
cout.flush();
long long d;
if (!(cin >> d)) return 0;
key[v] = d;
parent[v] = root;
}
// Prim's algorithm on complete graph defined by distance oracle
while (inCount < n) {
int u = -1;
long long best = INF;
for (int v = 1; v <= n; ++v) {
if (!inMST[v] && key[v] < best) {
best = key[v];
u = v;
}
}
if (u == -1) break; // safety
inMST[u] = true;
inCount++;
edges.emplace_back(parent[u], u, key[u]);
for (int v = 1; v <= n; ++v) {
if (inMST[v] || v == u) continue;
cout << "? " << u << " " << v << '\n';
cout.flush();
long long d;
if (!(cin >> d)) return 0;
if (d < key[v]) {
key[v] = d;
parent[v] = u;
}
}
}
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;
} |