File size: 1,888 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 | #include <bits/stdc++.h>
using namespace std;
long long query(int u, int v) {
cout << "? " << u << " " << v << endl;
cout.flush();
long long d;
if (!(cin >> d)) exit(0);
return d;
}
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 << "! " << endl;
cout.flush();
continue;
}
const long long INF = (1LL<<62);
vector<long long> best(n+1, INF);
vector<int> from(n+1, -1);
vector<char> in(n+1, 0);
vector<tuple<int,int,long long>> edges;
int start = 1;
in[start] = 1;
for (int v = 1; v <= n; ++v) {
if (v == start) continue;
long long d = query(start, v);
best[v] = d;
from[v] = start;
}
for (int iter = 1; iter <= n - 1; ++iter) {
int w = -1;
long long md = INF;
for (int v = 1; v <= n; ++v) {
if (!in[v] && best[v] < md) {
md = best[v];
w = v;
}
}
if (w == -1) break;
in[w] = 1;
edges.emplace_back(from[w], w, best[w]);
for (int v = 1; v <= n; ++v) {
if (!in[v]) {
long long d = query(w, v);
if (d < best[v]) {
best[v] = d;
from[v] = w;
}
}
}
}
cout << "! ";
for (auto &e : edges) {
int u, v;
long long w;
tie(u, v, w) = e;
cout << u << " " << v << " " << w << " ";
}
cout << endl;
cout.flush();
}
return 0;
} |