# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
499102 | beksultan04 | Evacuation plan (IZhO18_plan) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 = 1e18+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;
priority_queue <pii> ss;
for (i=1;i<=n;++i)dis[i] = INF;
for (i=0;i<qq;++i){
int x;
cin>>x;
ss.push({0,x});
dis[x] = 0;
}
while (!ss.empty()){
int x = ss.top().sc,intt = s.top().fr;
ss.pop();
if (dis[x] < intt)continue;
for (auto [to,c]:g[x]){
if (dis[to] > dis[x] +c){
dis[to] = dis[x]+c;
ss.push({-dis[x],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]<<" ";
}
}