This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
vector < pair <int, long long int> > g [100010];
long long int dist [100010]; set < pair <long long int, long long int> > s;
long long int P [100010]; long long int d [100010]; long long int bio [100010];
vector <pair <int, int> > qr [100010];
long long int ans [100010]; long long int vis [100010];
vector < pair <long long int, long long int> > kr;
long long int p ( long long int x) { return (P[x]!=x ? P [x]=p (P[x]) : P[x]); } ;
long long int W;
void spoji ( long long int x, long long int y){
x=p (x); y=p (y);
if (x==y) return ;
if (qr [x].size()<qr [y].size()) swap (x, y);
P [y]=x;
for ( long long int i=0; i<qr [y].size(); i++){
if (p (y)==p(qr[y][i].first)) ans [qr[y][i].second]=max (ans [qr[y][i].second], W);
else qr [x].push_back ({qr[y][i].first, qr[y][i].second});
}
return ;
}
int main(){
long long int n, m; cin >> n >> m;
for ( long long int i=1; i<n+1; i++){
dist [i]=(int)1e18; P [i]=i; d[i]=1;
}
//for ( long long int i=1; i<n+1; i++) s.insert ({dist [i], i});
for ( long long int i=0; i<m; i++){
long long int a, b, c; cin >> a >> b >> c;
g [a].push_back ({b, c});
g [b].push_back ({a, c});
}
long long int k; cin >> k;
for ( long long int i=0; i<k; i++){
long long int a; cin >> a;
//s.erase ({dist [a], a});
dist [a]=0;
s.insert ({dist [a], a});
}
for ( long long int j=0; j<n-k; j++){
long long int x=(*s.begin()).second;
if ((*s.begin()).first!=dist [x]) continue;
s.erase ({dist [x], x});
for ( long long int i=0; i<g [x].size(); i++){
long long int y=g [x][i].first;
if (dist [y]>dist [x]+g [x][i].second){
s.erase ({dist [y], y});
dist [y]=dist [x]+g [x][i].second;
s.insert ({dist [y], y});
}
}
}
long long int q; cin >> q;
for ( long long int i=0; i<q; i++){
long long int x, y; cin >> x >> y;
qr [x].push_back ({y, i});
qr [y].push_back ({x, i});
}
for ( long long int i=1; i<n+1; i++) {
//cout << dist [i] << " ";
kr.push_back ({dist [i], i});
}
//cout << endl;
sort (kr.begin(), kr.end(), greater < pair <long long int, long long int> > ());
for ( long long int i=0; i<kr.size(); i++){
long long int x=kr [i].second; W=kr [i].first; vis [x]=1;
for ( long long int j=0; j<g [x].size(); j++){
long long int y=g [x][j].first;
if (vis [y]){
spoji (x, y);
}
}
}
for ( long long int i=0; i<q; i++) cout << ans [i] << endl;
return 0;
}
Compilation message (stderr)
plan.cpp: In function 'void spoji(long long int, long long int)':
plan.cpp:16:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for ( long long int i=0; i<qr [y].size(); i++){
| ~^~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:44:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for ( long long int i=0; i<g [x].size(); i++){
| ~^~~~~~~~~~~~~
plan.cpp:65:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for ( long long int i=0; i<kr.size(); i++){
| ~^~~~~~~~~~
plan.cpp:67:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for ( long long int j=0; j<g [x].size(); j++){
| ~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |