Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using pii = pair<int, int>;
- template <typename T> using MinHeap = std::priority_queue<T, vector<T>, greater<T>>;
- #define eb emplace_back
- #define ee emplace
- template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
- const int INF = INT_MAX >> 1;
- int main() {
- cin.tie(0)->sync_with_stdio(0);
- int N, M, Q; cin >> N >> M >> Q;
- vector<array<int, 3>> edges(M);
- for (auto &[u, v, w] : edges) cin >> u >> v, w = -1;
- for (int W = (1<<2); W <= (1<<18); W <<= 2) {
- cout << "? " << W << "\n" << flush;
- string ret; cin >> ret;
- for (int i = 0; i < M; ++i) {
- if (edges[i][2] == -1 and ret[i] == '0') edges[i][2] = W / 2;
- }
- }
- for (int i = 0; i < M; ++i) {
- if (edges[i][2] == -1) edges[i][2] = (1 << 19);
- }
- vector<vector<pii>> adj(N+1);
- for (auto [u, v, w] : edges) adj[u].eb(v, w);
- vector<int> dis(N+1, INF);
- MinHeap<pii> pq; pq.ee(dis[1] = 0, 1);
- while (size(pq)) {
- auto [d, now] = pq.top(); pq.pop();
- if (d > dis[now]) continue;
- for (auto [x, w] : adj[now]) { if (chmin(dis[x], d + w)) pq.ee(dis[x], x); }
- }
- cout << "! " << dis[N] << "\n" << flush;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
