#include #include #ifndef IO_HPP #define IO_HPP #include #include #include #include #include #include #include #include #include using namespace std; templateistream &operator>>(istream&,pair&); templateistream &operator>>(istream&,tuple&a); templateistream &operator>>(istream&is,vector&a); templateistream &operator>>(istream&is,array&a); template istream &operator>>(istream&is,pair&a){ is>>a.first>>a.second; return is; } template void read_tuple(istream&is,tuple&a){ if constexpr(pos>::value){ is>>get(a); read_tuple(is,a); } } template istream &operator>>(istream&is,tuple&a){ read_tuple<0>(is,a); return is; } template istream &operator>>(istream&is,vector&a){ for(T&x:a)is>>x; return is; } template istream &operator>>(istream&is,array&a){ for(T&x:a)is>>x; return is; } templateostream &operator<<(ostream&os,const pair&); templateostream &operator<<(ostream&os,const tuple&); templateostream &operator<<(ostream&os,const vector&); templateostream &operator<<(ostream&os,priority_queue); templateostream &operator<<(ostream&os,queue); templateostream &operator<<(ostream&os,deque); templateostream &operator<<(ostream&os,stack); templateostream &operator<<(ostream&os,const array&); templateostream &operator<<(ostream&os,const map&); templateostream &operator<<(ostream&os,const unordered_map&); templateostream &operator<<(ostream&os,const set&); templateostream &operator<<(ostream&os,const multiset&); templateostream &operator<<(ostream&os,const unordered_set&); template ostream &operator<<(ostream&os,const pair&a){ os< void write_tuple(ostream&os,const tuple&a){ if constexpr(pos>::value){ if constexpr(pos>0)os<<' '; os<(a); write_tuple(os,a); } } template ostream &operator<<(ostream&os,const tuple&a){ write_tuple<0>(os,a); return os; } template ostream &operator<<(ostream&os,const vector&a){ os<<'{'; for(int i=0;i<(int)a.size();i++){ os< ostream &operator<<(ostream&os,priority_queuea){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,queuea){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,dequea){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,stacka){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,const array&a){ os<<'{'; for(int i=0;i<(int)a.size();i++){ os< ostream &operator<<(ostream&os,const map&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<"{["<first<<","<second<<']'; while(++itr!=a.end())os<<",["<first<<','<second<<']'; os<<'}'; return os; } template ostream &operator<<(ostream&os,const unordered_map&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<"{["<first<<","<second<<']'; while(++itr!=a.end())os<<",["<first<<','<second<<']'; os<<'}'; return os; } template ostream &operator<<(ostream&os,const set&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<'{'<<*itr; while(++itr!=a.end())os<<','<<*itr; os<<'}'; return os; } template ostream &operator<<(ostream&os,const multiset&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<'{'<<*itr; while(++itr!=a.end())os<<','<<*itr; os<<'}'; return os; } template ostream &operator<<(ostream&os,const unordered_set&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<'{'<<*itr; while(++itr!=a.end())os<<','<<*itr; os<<'}'; return os; } #endif using namespace std; using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templatevoid operator++(pair&a,int){a.first++,a.second++;} templatevoid operator--(pair&a,int){a.first--,a.second--;} templatevoid operator++(vector&a,int){for(auto &i:a)i++;} templatevoid operator--(vector&a,int){for(auto &i:a)i--;} using vref=typename vector::reference; vref operator|=(vref a,bool b){a=a|b;return a;} vref operator&=(vref a,bool b){a=a&b;return a;} vref operator^=(vref a,bool b){a=a^b;return a;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template inline int fkey(vector&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include #define SWITCH(a,b) (a) #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define SWITCH(a,b) (b) #endif struct Timer{ clock_t start; Timer(){ start=clock(); ios::sync_with_stdio(false); cin.tie(nullptr); cout<>testcase; for(int i=0;i struct Edge{ int from,to; T weight; int index; Edge(int from_,int to_,T weight_=T(),int index_=-1):from(from_),to(to_),weight(weight_),index(index_){} Edge():from(-1),to(-1),weight(),index(-1){} friend std::ostream &operator<<(std::ostream &os,const Edge&e){ os<<'['; os<<"from:"< struct Graph{ private: int n; std::vector>edge; std::vector>g; std::vectorptr; bool directed; struct graph_range{ using iterator=typename std::vector>::iterator; iterator l,r; iterator begin()const{return l;} iterator end()const{return r;} int size()const{return r-l;} Edge &operator[](int i)const{return l[i];} }; struct const_graph_range{ using iterator=typename std::vector>::const_iterator; iterator l,r; iterator begin()const{return l;} iterator end()const{return r;} int size()const{return r-l;} const Edge &operator[](int i)const{return l[i];} }; public: Graph(int n_,bool dir_):n(n_),directed(dir_){} Graph():n(0){} Graph(int n_,bool dir_,const std::vector>&e):n(n_),directed(dir_),edge(e){build();} template void read(int m){ edge.reserve(m); for(int i=0;i>u>>v; T w; if constexpr(index)u--,v--; if constexpr(weighted)std::cin>>w; else w=1; edge.emplace_back(u,v,w,i); } build(); } void add_edge(int u,int v){ assert(0<=u&&ue){ edge.emplace_back(e); } void build(){ std::vectorcnt(n+1,0); for(const Edge&e:edge){ cnt[e.from+1]++; if(!directed)cnt[e.to+1]++; } for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1]; ptr=cnt; g.resize(cnt[n]); for(const Edge&e:edge){ g[cnt[e.from]++]=e; if(!directed)g[cnt[e.to]++]=Edge(e.to,e.from,e.weight,e.index); } } void reverse(){ if(directed){ for(Edge&e:edge)std::swap(e.from,e.to); build(); } } inline void to_directed(){ directed=true; build(); } inline void to_undirected(){ directed=false; build(); } void reserve(int m){edge.reserve(m);} graph_range operator[](int i){return graph_range{g.begin()+ptr[i],g.begin()+ptr[i+1]};} const_graph_range operator[](int i)const{return const_graph_range{g.begin()+ptr[i],g.begin()+ptr[i+1]};} const Edge& get_edge(int i)const{return edge[i];} std::vector>get_edges()const{return edge;} inline bool is_directed()const{return directed;} inline int size()const{return n;} inline int edge_size()const{return edge.size();} typename std::vector>::iterator begin(){return edge.begin();} typename std::vector>::iterator end(){return edge.end();} typename std::vector>::const_iterator begin()const{return edge.begin();} typename std::vector>::const_iterator end()const{return edge.end();} }; constexpr ll inf=2e18; void SOLVE(){ int n,m,q; cin>>n>>m>>q; vectors(n); cin>>s; Graphg(n,false); rep(i,1,m+1){ int u,v; ll w; cin>>u>>v>>w; u--,v--; if(i<=60&&(w<=(inf>>i))){ g.add_edge(u,v,w<>>table(n); vectorvis(n,-1); vectordst(n,inf); minque>que; rep(i,n){ auto yaru=[&](int v,ll d)->void { if(vis[v]!=i){ vis[v]=i; dst[v]=d; que.emplace(d,v); } else if(chmin(dst[v],d))que.emplace(d,v); }; yaru(i,0); while(!que.empty()){ auto [d,x]=que.top();que.pop(); if(dst[x]!=d)continue; table[i].emplace_back(x,d); for(auto e:g[x])yaru(e.to,d+e.weight); } } map,ll>mp; auto query=[&](int a,int b)->ll { if(a>b)swap(a,b); if(mp.contains({a,b}))return mp[{a,b}]; ll&res=mp[{a,b}]; res=inf; for(auto [u,du]:table[a]){ if(u==b)chmin(res,du); for(auto [v,dv]:table[b])chmin(res,du+dv+s[u]+s[v]); } return res; }; while(q--){ int a,b; cin>>a>>b; a--,b--; cout<