#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000;
const int maxkit=22;
int n, m, f, q;
struct El {
int to, w;
El() { }
El(int erk, int suly) {
to=erk;
w=suly;
}
const bool operator< (El masik) const {
return w>masik.w;
}
};
vector<El> graf[maxn];
int d[maxn];
bool volte[maxn];
int hol[maxn];
vector<int> fa[maxn];
int hely[maxn];
vector<int> cron;
void init() {
for(int i=0;i<n;i++) {
hol[i]=i;
}
return;
}
int holvan(int u) {
if(hol[u]!=u) {
hol[u]=holvan(hol[u]);
}
return hol[u];
}
int t=0;
void bejar(int start, int apa) {
cron.push_back(d[start]);
hely[start]=t;
t++;
for(int s:fa[start]) {
if(s!=apa) {
bejar(s,start);
cron.push_back(d[start]); t++;
}
}
return;
}
int tab[maxn][maxkit];
void set_rmq() {
for(int k=0;k<maxkit;k++) {
for(int i=0;i<cron.size();i++) {
if(k==0) {
tab[i][k]=cron[i];
}
else {
int kezd=min((int)cron.size()-1,i+(1<<(k-1)));
tab[i][k]=min(tab[i][k-1],tab[kezd][k-1]);
}
}
}
return;
}
int get_rmq(int from, int to) {
int l=to-from+1;
int kl=log2(l);
return min(tab[from][kl],tab[to+1-(1<<kl)][kl]);
}
vector<int> sol;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i=0;i<m;i++) {
int u, v, w;
cin>>u>>v>>w;
u--;
v--;
graf[u].push_back(El(v,w));
graf[v].push_back(El(u,w));
}
priority_queue<El> kovi;
cin>>f;
for(int i=0;i<f;i++) {
int s;
cin>>s;
s--;
kovi.push(El(s,0));
}
while(!kovi.empty()) {
El akt=kovi.top();
kovi.pop();
if(!volte[akt.to]) {
volte[akt.to]=true;
d[akt.to]=akt.w;
for(El s:graf[akt.to]) {
if(!volte[s.to]) {
s.w+=d[akt.to];
kovi.push(s);
}
}
}
}
vector<pair<int,int> > tavol;
for(int i=0;i<n;i++) {
tavol.push_back(make_pair(d[i],i));
}
sort(tavol.begin(),tavol.end());
reverse(tavol.begin(),tavol.end());
init();
for(auto ez:tavol) {
int akt=ez.second;
for(El s:graf[akt]) {
if(holvan(akt)!=holvan(s.to) && d[s.to]>=d[akt]) {
fa[akt].push_back(s.to);
fa[s.to].push_back(akt);
akt=holvan(akt);
s.to=holvan(s.to);
hol[s.to]=akt;
}
}
}
bejar(0,0);
set_rmq();
cin>>q;
for(int i=0;i<q;i++) {
int s, t;
cin>>s>>t;
s--; t--;
sol.push_back(get_rmq(hely[s],hely[t]));
}
for(int d:sol) {
cout<<d<<'\n';
}
return 0;
}
Compilation message
plan.cpp: In function 'void set_rmq()':
plan.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cron.size();i++) {
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
110 ms |
95724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
110 ms |
95724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
110 ms |
95716 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
446 ms |
156232 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
110 ms |
95724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
