#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define ar array #define int long long template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} template <class T> using ste = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; const long long inf = 3e18 + 7; const int mod = 1000000007; const int md = 998244353; const int N = 3e5 + 5; struct Bit { vector<int> b, b2; int n; Bit(int n) { this->n = n + 1; b.assign(n + 1, 0); b2.assign(n+1, 0); } void add(vector<int>&b, int idx, int x){ while(idx <= n){ b[idx] += x; idx += idx & -idx; } } void upd(int l, int r, int x){ if(r < l)return; add(b, l, x); add(b, r+1, -x); add(b2, l, x*(l-1)); add(b2, r+1, -x*r); } int sum(vector<int>&b, int idx){ int res = 0; while(idx > 0){ res += b[idx]; idx -= idx & -idx; } return res; } int pref(int idx){ return sum(b, idx) * idx - sum(b2, idx); } int get(int l, int r){ return pref(r) - pref(l-1); } }; int n,m,k; vector<ar<int,2>>g[N]; vector<int>baty(N), sz(N), order[N]; int find_baty(int x){ if(baty[x] == x)return x; return baty[x] = find_baty(baty[x]); } void unin(int a, int b){ a = find_baty(a); b = find_baty(b); if(a == b)return; if(sz[a] < sz[b])swap(a, b); baty[b] = a; sz[a] += sz[b]; } void solve(){ cin >> n >> m; for(int i = 1;i<=m;i++){ int a,b,c; cin >> a >> b >> c; g[a].pb({b, c}); g[b].pb({a, c}); } cin >> k; priority_queue<ar<int,2>, vector<ar<int,2>>, greater<ar<int,2>>>qss; vector<int>w(n + 1, inf); for(int i = 1;i<=k;i++){ int a; cin >> a; qss.push({0, a}); w[a] = 0; } while(!qss.empty()){ auto [c, x] = qss.top(); qss.pop(); if(c > w[x])continue; for(auto [to, cost] : g[x]){ if(umin(w[to], w[x] + cost)){ qss.push({w[to], to}); } } } int q; cin >> q; vector<ar<int,2>>qs(q + 1), arr(q + 1); vector<int> ans(q + 1); for(int i = 1;i<=q;i++){ int a,b; cin >> a >> b; arr[i] = {a, b}; } set<int>st; for(int i = 1;i<=n;i++){ st.insert(w[i]); } vector<int>vs; for(auto to : st)vs.pb(to); sort(all(vs)); reverse(all(vs)); int cnt = 0; vector<int>id(n + 1); map<int,int>mp; for(auto to : vs){ mp[to] = cnt++; } for(int i = 1;i<=n;i++){ order[mp[w[i]]].pb(i); id[i] = mp[w[i]]; } for(int i = 1;i<=q;i++){ qs[i] = {0, vs.size()-1}; } //~ for(int i = 0;i<vs.size();i++){ //~ cout << vs[i] << " : \n"; //~ for(auto to : order[i]){ //~ cout << to << " "; //~ } //~ cout << "\n"; //~ } //~ return; // for(int ll = 1;ll<=30;ll++){ for(int i = 1;i<=n;i++){ baty[i] = i; sz[i] = 1; } vector<int>op[vs.size() + 5], val(q + 5, -1); for(int i = 1;i<=q;i++){ if(qs[i][0] > qs[i][1])continue; int mid = (qs[i][0] + qs[i][1]) / 2; op[mid].pb(i); } for(int i = 0;i<vs.size();i++){ for(auto x : order[i]){ for(auto [to, cost] : g[x]){ if(id[to] <= i) unin(x, to); } } for(auto ind : op[i]){ int a = arr[ind][0], b = arr[ind][1]; if(find_baty(a) == find_baty(b)){ val[ind] = 1; } else val[ind] = 0; } } for(int i = 1;i<=q;i++){ if(qs[i][0] > qs[i][1])continue; int mid = (qs[i][0] + qs[i][1]) / 2; if(val[i] == 1){ ans[i] = mid; qs[i][1] = mid - 1; } else qs[i][0] = mid + 1; } } for(int i = 1;i<=q;i++){ cout << vs[ans[i]] << "\n"; } } /* 9 12 1 9 4 1 2 5 2 3 7 2 4 3 4 3 6 3 6 4 8 7 10 6 7 5 5 8 1 9 5 7 5 4 12 6 8 2 2 4 7 5 1 6 5 3 4 8 5 8 1 5 */ signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1;//cin >> tt; while(tt--)solve(); }

plan.cpp: In function 'void solve()':
plan.cpp:148:38: warning: narrowing conversion of '(vs.std::vector<long long int>::size() - 1)' from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  148 |                 qs[i] = {0, vs.size()-1};
      |                             ~~~~~~~~~^~