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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl "\n"
int mod=1e9+7;
const int N=1e5+5;//2e5+5;
template<class x>
using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>;
vector<vector<pair<int,int> > > tst(N),v(N);
vector<vector<int> > grp(N);
pair<int,int> dis[N];
int npp[N],par[N],ans[N];
bool vis[N];
void con(int a,int b,int cst) {
a=par[a]; b=par[b];
if (grp[a].size()>grp[b].size()) swap(a,b);
for (int i:grp[a]) {
for (auto j=0;j<tst[i].size();j++) {
if (par[tst[i][j].first]==b) ans[tst[i][j].second]=cst;
}
}
for (int i:grp[a]) {
par[i]=b; grp[b].push_back(i);
}
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen(".in", "r", stdin); freopen(".out", "w", stdout);
int n,m; cin>>n>>m;
while (m--) {
int a,b,c; cin>>a>>b>>c;
v[a].push_back({c,b});
v[b].push_back({c,a});
}
int k; cin>>k;
for (int i=0;i<k;i++) cin>>npp[i];
for (int i=1;i<=n;i++) {
dis[i]={1e10,i};
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
for (int i=0;i<k;i++) {
dis[npp[i]]={0,npp[i]}; q.push({0,npp[i]});
}
while (!q.empty())
{
int cnt=q.top().first;
int node=q.top().second;
q.pop();
if (dis[node].first<cnt) {continue;}
for (int i=0;i<v[node].size();i++)
{
int price=v[node][i].first;
int child=v[node][i].second;
if (dis[child].first>(cnt+price))
{
dis[child].first=cnt+price;
q.push(dis[child]);
}
}
}
int t; cin>>t;
for (int i=0;i<t;i++) {
int a,b; cin>>a>>b;
tst[a].push_back({b,i});
tst[b].push_back({a,i});
}
sort(dis,dis+N); reverse(dis,dis+N);
for (int i=1;i<=n;i++) {
par[i]=i; grp[i].push_back(i);
}
for (int i=0;i<n;i++) {
int dd=dis[i].first,nm=dis[i].second;
for (int j=0;j<v[nm].size();j++) {
if (vis[v[nm][j].second] && par[v[nm][j].second]!=par[nm]) {
con(nm,v[nm][j].second,dd);
}
}
vis[nm]=true;
}
for (int i=0;i<t;i++) cout<<ans[i]<<endl;
}
Compilation message (stderr)
plan.cpp: In function 'void con(long long int, long long int, long long int)':
plan.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (auto j=0;j<tst[i].size();j++) {
| ~^~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:64:23: 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]
64 | for (int i=0;i<v[node].size();i++)
| ~^~~~~~~~~~~~~~~
plan.cpp:90:21: 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]
90 | for (int j=0;j<v[nm].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... |