이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
int n,m,k,q,curr;
vector<vector<int>> roads[100005];
int best[100005];
bool check[100005];
int ans[100005];
//
int root[100005];
set<int> vals[100005];
int findroot(int x){
if(root[x]!=x){
root[x] = findroot(root[x]);
}
return root[x];
}
void domerge(int x, int y){
x = findroot(x);
y = findroot(y);
if(x==y){
return;
}
if(vals[x].size()>vals[y].size()){
swap(x,y);
}
for(int i:vals[x]){
if(vals[y].find(i)!=vals[y].end()){
ans[i] = curr;
vals[y].erase(i);
}
else{
vals[y].insert(i);
}
}
vals[x].clear();
root[x] = y;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i=1;i<=n;i++){
best[i] = 2e9;
root[i] = i;
}
for(int i=1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
roads[a].push_back({b,c});
roads[b].push_back({a,c});
}
priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
cin >> k;
for(int i=1;i<=k;i++){
int a;
cin >> a;
best[a] = 0;
pq.push({0,a});
}
while(pq.size()>0){
while(pq.size()>0 and check[pq.top()[1]]){
pq.pop();
}
if(pq.size()==0){
break;
}
int x = pq.top()[1];
check[x] = true;
pq.pop();
for(vector<int> i:roads[x]){
if(best[i[0]]>best[x]+i[1]){
best[i[0]] = best[x]+i[1];
pq.push({best[i[0]],i[0]});
}
}
}
vector<vector<int>> ord;
for(int i=1;i<=n;i++){
ord.push_back({best[i],i});
}
sort(ord.begin(),ord.end(),greater<vector<int>>());
cin >> q;
for(int i=1;i<=q;i++){
int a,b;
cin >> a >> b;
vals[a].insert(i);
vals[b].insert(i);
}
for(vector<int> i:ord){
curr = i[0];
for(vector<int> j:roads[i[1]]){
if(best[j[0]]>=curr){
domerge(i[1],j[0]);
}
}
}
for(int i=1;i<=q;i++){
cout << ans[i] << "\n";
}
return 0;
}
# | 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... |