#include <iostream> #include <vector> #include <random> #include <algorithm> #include <chrono> #include <queue> #include <cstring> #define all(x) x.begin(), x.end() #define pb push_back #define fi first #define se second #define compact(v) v.erase(unique(all(v)) , v.end()) #define pi pair<int , int> #define vi vector<int> #define eb emplace_back #define FOR(i , l , r) for(int i = l; i <= r; ++ i) #define FORD(i , l , r) for(int i = l; i >= r; -- i) template <class T> bool maximize(T &a , T b){return (a < b ? a = b , true : false);} template <class T> bool minimize(T &a , T b){return (a > b ? a = b , true : false);} using namespace std; typedef long long ll; const int nd = 2e5 + 5 , mod = 1e9 + 7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int> dist(1 , (int)2e9); int add(int a , int b){ a += b; return (a >= mod ? a - mod : a); } int sub(int a , int b){ a -= b; return (a < 0 ? a + mod : a); } int mul(ll a , ll b){return (a * b) % mod;} int xpow(int a , int b){ if(b == 1) return a; int x = xpow(a , b / 2); if(b & 1) return mul(a , mul(x , x)); else return mul(x , x); } vector <pi> adj[nd]; namespace dijs{ int dis[nd]; priority_queue <pi , vector <pi> , greater <pi> > q; void calc(){ memset(dis , 0x3f , sizeof(dis)); while(q.size()){ auto [h , r] = q.top(); q.pop(); if(dis[r] < h) continue; dis[r] = h; for(auto [v , w] : adj[r]) if(dis[v] > w + h){ dis[v] = h + w; q.push({h + w , v}); } } } } namespace dsu{ int par[nd] , sz[nd]; void init(int n){ FOR(i , 1 , n) par[i] = i , sz[i] = 1; } int get(int u){return u == par[u] ? u : par[u] = get(par[u]);} void unite(int u , int v){ u = get(u) , v = get(v); if(u == v) return; if(sz[u] > sz[v]) swap(u , v); par[u] = v; sz[v] += sz[u]; } } struct event{ int u , v , w , id; bool operator<(const event &o)const{ if(w == o.w) return id < o.id; return w > o.w; } }; vector <event> E , query , node; int top[nd] , dow[nd] , ans[nd]; bool rebuild(int n){ bool f = false; E.clear(); dsu::init(n); for(auto [u , v , w , id] : query) if(top[id] >= dow[id]){ f = true; int mid = (top[id] + dow[id]) >> 1; E.pb({u , v , mid , id}); } for(event e : node) E.pb(e); sort(all(E)); return f; } void solve(){ int n , m , q , k; cin >> n >> m; FOR(i , 1 , m){ int l , r , w; cin >> l >> r >> w; adj[l].eb(r , w); adj[r].eb(l , w); } cin >> k; FOR(i , 1 , k){ int u; cin >> u; dijs::q.push({0 , u}); } dijs::calc(); FOR(i , 1 , n){ node.pb({i , 0 , dijs::dis[i] , 0}); } cin >> q; FOR(i , 1 , q){ int u , v; cin >> u >> v; top[i] = 1e8 , dow[i] = ans[i] = 0; query.pb({u , v , 0 , i}); } while(rebuild(n)){ for(auto [u , v , w , id] : E){ if(!id){ for(auto [r , ww] : adj[u]) if(dijs::dis[r] >= w){ dsu::unite(r , u); } } else{ if(dsu::get(u) == dsu::get(v)){ ans[id] = w; dow[id] = w + 1; } else top[id] = w - 1; } } } FOR(i , 1 , q) cout << ans[i] << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); #define task "task" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } solve(); return 0; } /* -. ::. -: .:::::::::: ***##*###**##@%***+###+***+**++******#*******#*******++*****+*+=@*+####%@@@@@%*===#*%@===---**#@@#=*######***@@@#*###=*@%#######: **##*##*+*%#%@**+**##****************#***+***#*+*+***+++******+=@#+*#=:--===-====-*#+@%:#@@%##*#%%#+########+*@%%@#*##+=@%######: #%####*+*%##@#+*+*###**#********##***#++***++#********#***+++++=%@=###==========:#:#+*@######*%##%%#=+###*##*+#@##@%###+=%%#####: #####***%##@%+***#%#++#######*********++***#*#+##%%%##****#####+#@ ###===++++=-=@@#**+#%+*+##+#%##%%#+*######*+%%###@###*=#%####: ##*****####@*+***###+=**#+==*+*###%#%%###%%**%*#=::-+#%####+#=-#+@=-###===+==-#@#*###+=@#+*+##*#%##%##=*######*+@%###%%*#*+%%###: %##***####@#++*+#%+*++=+++=+#**#===-==+*+=:=+@-#+-===-:+#%+:+#:#=@@.#%#----:-###*****#=*@+++***+#%#%#%#+*###*##**@####%@#***%###: *####*@##%@++***##+###+====##+##==========-+*@:%+-=-::::::::=@:#=@%+=##**==#@#####*###+=@%=****#+%##@#%#=####*##+#%#####%##**%##: #**#*#%##@#*#***##**########*+#*-=*+==+===-++@.%=::+@#+=:.=@*#=#=@%#=*@*####**+*********+@*=+*****%#%%*%+*####****@######%%**#%#: ####*####@++*+*#%+*#**********##*####-====:*=@.#-:####%%@@%#####=%%#=+@#=+***++*******+#=%@+++*++=*%#@###=*######+@%######@#+###. ###**%##@#*****#@*##*#**#***+*******##*==##*=@=%#%%##*##*##+*##*-%@%==#@+=*+******#****##+@%+=+***+##%%*##*#**##**+@#######@**##: ###*#%##@++#*+*##*##****##****#*******####*+=@=%+********#*=*##*-#@#*:*@#=+***+**+++***=@=@@@#=++++=@#@#+%***#####+@#######%#+##. ###*#%#%%**##+*%#**#*#**#***********#******+=@=%=*++**#**#*+**++-#@*@-=@#=+***+++*+****=#*@ @@#=*##+*#@%++#**#####*%%#######@+##: ###*###@#**##+*@*************#************#==@+@=+*+++***#+++*++=@@*##:%@#=++++++++++**+*%@@ @@%-=+++##@#=%+*#*#***#%#######%##%: ##*#%##@***##+#%**#***#***#********+***#+*#==@#@:=+++++**@=+++++*#@@*%-+@@==++**+**++**++%@@ @@@=-=+##@%=##+#*#***#%###########. ##*#%##@*#*##=*%**#*******+***********+*+*+=-@#@-=++++=+%*=+***+@. @###:@%%=******+*****=#@@ @@@*:-#@%+=%+#*###+#@###########: :@#*#%##%#**##+#%+************#*****++***+#*+-%%@==+++*=+@=++++==@ @@#%=##%==+*++*+*****=#@@ @@@@#*#@*-@+***##+#%########%%#: #@*##%@#*###*+#%*##****+***++***++**+++++++*-%@@*=++++=%%-==**#@@@@@@##%+#%%-=+++++**+**==@@ @#*+@*=##***##+*@###########: @*%%#%##*##**#%**####*#***********++**+**+*-#@%#-+++=:@=#%##+#@ @@#####@#=++**+******-@= *@@@@@@@@@@@=+#****#*+@###########: @@@%##@#**##*+#%**************+*****+++++++*=#@#@:=+==@@-====*@ @@######@+=+++++++*++=@ @@@@@@@@ +@@=+#****#*=%%##########: #@@%#@##*###+#@***********+*#*++++++***+*+#=*@#%++=:@@==+*++@@ .. @@#####%@-=***+*****=@@@@@@ .@@.@ @#=***#+#*=@@##########: @%#@#*##**+#@#**#*******+*#++****++++*++#=+@##@ :@@*-+==+@@ .: @@#####@@=+++++*++**=@@%@@@ -@@@:*@=*#**+#*+@*@#########: =: ##@**####+#@***********+*#++***+++++*++#+=@##@%@@#:=++*@@ .. #@@#####@#=+**+*+#@@%#@##@@ @ @-=@=****+%*=@-#@%#######: : :@@*@##****+#@*+****#****+*%+*****+++++++#==@###%@@-=*+*@@ -*+ =@@#####@*=+**++#= -@% : @% -@==@=#***+@*=@% +@@######: @@@*+@##**+*+#@#+*******+*++@=+***++**++++**=@##@@*-=+==*. *:: -@@*####%#-++++##=:% @-@@% *@=-@=#***+@+=%@@. @@@%###: +@@#*+*@##*###=#@#=****#****++@*=*+*++++++++*+=@@@%-:==--+@@@@@@@@# @@####%%*-=+++#+=@@ : +@+=@+#**++@+=@#%@%- -##%%: ##%#*#@##**##=#@%+*********+=%#=*++++++*++====@@::-=+##@@@@@@@@@@@@@@ @@@*##%##===++**#@ .. :@*-@%***+*@==@###%@@%####: ###%@%@##****=#@@++*#*******=#@=++++*+*+===#@%-:-##+=#@#===@ ::++ =@@***#*#=-==++=@@ @#=#@*+*=#%==@@%#*###%@##. #*@ @@@#**###=#@%*+*********+=@+=***+-==#@@+---=+++#@@@@@@@@@ @@@*+%##*--=+==@+ . @@+#@*=+=@#==@###%%%#####. **@ @@%****#+#@@#+*********+-@#:====@@#==-===++#@@@@@ @ @@ @@@+*#+**:-==*@ . @@**@+=+*%#=+@###########. ++@: @@%+*#**++@%@=**+++++===-%@@@@@#=-==+=--+#@@@ @@ . . @@@@#=+**=--#@ +@**@+==##*-#@###########: -@@@ @#-======%%@*===*###@@@@#=----==+==-=#@@@@ @@* :@= @@@@@#*#=:#@ @*#@==+%#+*#@%##########: %@@@@@@#%@@@@@@@%@@@@@%##+=---=+=====-=+@@@#=#*@ ::.+@#: :#@@@@#+#@@ @#@@--%%#=#*%###########: %@@ @%@#%##++======------=========#%@@@@=====*=@#%@@%- ... @@@@@@@@# @*@#:=@#**#*@###########. @@%-@*=*#@@@@%#*+*#%@@@@@@@@@@@@@+=--=+***+##@ . . .*% @@@:-@##=#+#@#%#########. @@@**=@++++=:=%%##@@@##%%%##*+==@%==++******+*#@ .. . # @@*:##**##+#%##########%. +@@#***@+***++@####@*@#=-==+++*+=%@@=+*******++#@= . .. =. @@@.:@*#*##+@%########### :%#**#%@=**+=%%###@@+@#%++******=*@@#=********+%@@ . @@.:@**###*+@###*%#######. :#+*##@%+**=%%###*@+##@#%*=*#***+=@%@++******+++@@ @@:.@@=#**#=@@############. ++##%@*++=#@###*%@*##@##%#=+****=#%%#=**+*****+%@ @@.=@@@=*##*=@######%###### #%%@@@++=%@#####@#####@*##%+++**+*@%@*=+******+=@+ . @@.#%#@%=###=#%#%####%###### :@@@-@#==@@####*@*#%####@*##%*=+*+=#@#@*=++****+=%@ @ %@@@##@@++##=-@###%########## +-=@@=+@%####*%%%%%%###%@*##%%==+=#%#%%+=+*****==@ :=-:: @@@@*#%#@=*#+-@########=@##### **%@#*%%####*#@%@*%%#%##@#*##%@*==+%###@*=+*++*+-@@ ::: @@%%#@###%+#=.@%########+%##### #@@########*@@@@%:@%%%###@%####%@+:##@##%*=+*+++==@ :@@%%@####@**-:@%######%*#*###### @%#######**@@#@+=-@%######@######@#=##%##@%==+++==@@ @@ =@@%######@@+ =@%################# =%#######+@@##@#+*=@##%%####@%##############@=======@ @%@-@@@#######@%: @@##########%#*###### .######*%@@%#%@+**=@#######@.@%##########%**#%#=====*@ :. **@@:@@@#####@# +@%#############*###### .#%##+@@@%=#%@#*#**@#%%####@:=%@##%##*######*##@*=-==#@ :=@@: @ -##-@@@###%-=@%############*##+%##### :#=*@@#*=+=%%#**#+#@#@#####@-==%@**#%#*****##**##%*:--#@ :+%@@@* : @@@#*###################+%##### @@###+*#*#@%##*#+%%%@*%###@=++=%@#*#%%#*+********##*-:=@+ @@@@#: +@ *@@@#############**######*#### #####***+@@**##**%@@-#%###@=***-%@%***@%#++***#++**###-=%@ @ .-+#%@@@@@@@@@@@@@@ #@@@%#############*#*#####** ####%*#*#@#**##*#%@::@%###@=#+#=-##@*+*#@@#*=++##=+**##*=*@% @@ :::::::. #@ @@%###@@ @@@@#########**##******** .#####**#@#*####+#@@ #@##%@@=#=%=+=#*@@@@%+%@@@@%*#@===+**+#%@@ @%:.::::::--:: @@ =@*#=#*@@@@ +@@@#*#*******###*###** #####**%#**##***@@= @%##@:#+%=@++=#*@* @@@@#* @@@@#@@+=+****@@@+ : @@ +@#=:%#@ @@@% @@@%#######**#**+*** .####**%%**###**%@@ @%#@@ #%#=##==#*@@ @@@@@ @@@@@@@+==+*#@@@@@=: :#@@@ @@ =@#=-###@ #@@@@ @@@@#************* ####*#%*#####+#@@ =@%%@ @+@#=+#==#*@* . +@@@@ *@@@*=++==#@@@@@@@: @@:-@#=-*##@= @@#@@@ #@@@#*********** .#######**###**@@= @@@@+ ##@#=+#*=##@ ::. :@@@@@@@- :@*@@@@@@= : -@@=#+==+##*@@: %==@@@@ @@@@#****++++ ######*##*##*@@# *@@@= @#@@#=++@+##@ +#= @@@@#+-*%@@@@@@@@@%. %@@@@@@%= @=@#+===##++=%@:@=:#@@@@ -@@@@%#**** #####**##*+*#@% =@%@@.*@@ @%+++=#*@@ . @@@==@@@@@@- .@@@@@+===*+@=## @@@#-+%*@@@: =@@@*++ ####***#*+*#@@ :@#@@+ %#@ @@#+++*#@@ -. @@@##@@@# @@@+====@.#@= @@%==#**@@@- :=:::. @@*+ ##*+*##*++@@@ #@#@@@ @#@ @@#++=*%@ *@%%@@@ . @@#===#=:@@@ @@@%@@@@@@@@= .-: #@* .##**#****%@@. @@*@@= .@#@ @@@+=++@ @@%@@@ ......:: #@@===@ @@@@ ::#@@= . .:-. @@ #+***++#%@@ @##@@ %@#@ *: @@@+=*@@@@@@ .... . ..::. @@+-*@ @@@. ... . # *#****##%% +@*#@% .: @@#@ :@@@#@@@@ ... .. .:. @@#=#@ - ....... **++##### @##@@: ::: =@#@ .: @@@ ......... . .. .. @%#*@: # : .=**=:.. ..:. ++*####**#**@@ :::: @@@@ @@@: .:.......... ... . . .: -@#+#@ : .:::..:=#%@@@@= ......... +######*+*@@* ::::::: @@@@@@@@ ..:....... ..... . ... . . %+**%@ .. # -** . . ..:... ##**#*+=#@@: ::::::::. . :...:........... . .. .. ##-=#@ . =@@= . ...... ####*+#@@* :::-::::: ==-=: .::.:::.. ... .. .... ... ##=-=@ :#+. .::. ...:::: */

plan.cpp: In function 'int main()':
plan.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~