이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define ft first
#define sc second
using namespace std;
const int mod=1e9+7,INF=1e17;
vector<pair<int,int>> v[100005];
int dist[100005],pr[100005],id[100005],vis[100005],ans[100005];
set<int> s[100005];
pair<int,int>p[100005];
bool cmp(int x,int y){
return dist[x]>dist[y];
}
int find(int x){
if(pr[x]==x){
return x;
}
return pr[x]=find(pr[x]);
}
void merge(int x,int y,int val){
if((x=find(x))==(y=find(y)))
return;
if(s[x].size()<s[y].size())
swap(x,y);
for(auto it : s[y]){
if(s[x].count(it))
ans[it]=val;
else
s[x].insert(it);
}
pr[y]=x;
}
main(){
int n,m,a,b,c;
cin >> n >> m;
for(int i=0;i<m;i++){
cin >> a >> b >> c;
v[a].push_back({b,c});
v[b].push_back({a,c});
}
for(int i=1;i<=n;i++){
dist[i]=INF;
}
int k,x;
cin >> k;
queue<int> q;
for(int i=0;i<k;i++){
cin >> x;
q.push(x);
dist[x]=0;
}
while(!q.empty()){
int to=q.front();
q.pop();
for(auto it : v[to]){
if(dist[it.ft]>dist[to]+it.sc){
dist[it.ft]=dist[to]+it.sc;
q.push(it.ft);
}
}
}
int t;
cin >> t;
for(int i=1;i<=t;i++){
int e,f;
cin >> e >> f;
s[e].insert(i);
s[f].insert(i);
p[i]=make_pair(e,f);
}
for(int i=1;i<=n;i++){
pr[i]=id[i]=i;
}
sort(id+1,id+n+1,cmp);
for(int i=1;i<=n;i++){
vis[id[i]]=1;
for(auto it : v[id[i]]){
if(vis[it.ft]){
merge(it.ft,id[i],dist[id[i]]);
}
}
}
for(int i=1;i<=t;i++){
cout << ans[i] << endl;
}
}
컴파일 시 표준 에러 (stderr) 메시지
plan.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
39 | main(){
| ^~~~
# | 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... |