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;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define pii pair<int,int>
#define ret return
#define fr first
#define sc second
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define nosol puts("-1");
#define pb push_back
#define endi puts("");
#define ordered_set tree <int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N = 1e6+12,INF = 1e15+7;
int dis[N],a[N],used[N],ans[N];
vector <pii> g[N];
set <int> s[N];
struct dsu{
int n;
vector<int> p;
dsu(int N) : n(N), p(N+1) {
for (int i=0;i<=n;++i){
p[i] = i;
}
}
int find_baty(int x){
if (x == p[x])ret x;
ret p[x] = find_baty(p[x]);
}
void merge(int a,int b,int dl){
a = find_baty(a);
b = find_baty(b);
if (a == b)ret ;
if (s[a].size() > s[b].size())swap(s[a],s[b]);
for (auto x:s[a]){
if (s[b].count(x)){
ans[x] = dl;
}
else {
s[b].insert(x);
}
}
p[a] = b;
}
};
bool cmp(int a,int b){
ret dis[a]<dis[b];
}
main(){
int n,i,m;
cin>>n>>m;
dsu ds(n);
for (i=1;i<=m;++i){
int x,y,z;
cin>>x>>y>>z;
g[x].pb({y,z});
g[y].pb({x,z});
}
int qq;
cin>>qq;
set <int,decltype(cmp)*> ss(cmp);
for (i=1;i<=n;++i)dis[i] = INF;
for (i=0;i<qq;++i){
int x;
cin>>x;
ss.insert(x);
dis[x] = 0;
}
while (!ss.empty()){
int x = *ss.begin();
ss.erase(ss.begin());
for (auto [to,c]:g[x]){
if (dis[to] > dis[x] +c){
dis[to] = dis[x]+c;
ss.insert(to);
}
}
}
cin>>qq;
for (i=1;i<=qq;++i){
int x,y;
cin>>x>>y;
s[x].insert(i);
s[y].insert(i);
}
vector <pii> v;
for (i=1;i<=n;++i)
v.pb({dis[i],i});
sort(allr(v));
for (auto [dl,x]: v){
used[x] = 1;
for (auto [to,asd]: g[x]){
if (used[to]){
ds.merge(x,to,dl);
}
}
}
for (i=1;i<=qq;++i){
cout <<ans[i]<<" ";
}
}
Compilation message (stderr)
plan.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
60 | main(){
| ^~~~
plan.cpp: In function 'int main()':
plan.cpp:83:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
83 | for (auto [to,c]:g[x]){
| ^
plan.cpp:101:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
101 | for (auto [dl,x]: v){
| ^
plan.cpp:104:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
104 | for (auto [to,asd]: g[x]){
| ^
# | 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... |