이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define N 500009
#define pii pair <int, int>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
int n, m, k, ds[N], q, p[N], A[N];
bool vis[N];
vector<pii>e[N];
priority_queue<pii, vector<pii>, greater<pii>>Q;
int ata(int x){
if(p[x]==x)
return x;
return p[x]=ata(p[x]);
}
void uni(int x, int y){
p[ata(x)]=p[ata(y)];
}
void dsu(int x){
for(auto i:e[x])
if(vis[i.ff]==1)
uni(x, i.ff);
}
int main(){
cin>>n>>m;
for(int i=1; i<=m; i++){
int a, b, c;
cin>>a>>b>>c;
e[a].pb({b, c});
e[b].pb({a, c});
}
for(int i=1; i<=n; i++)
ds[i]=1e9;
cin>>k;
for(int i=1; i<=k; i++){
int a;
cin>>a, Q.push({0, a}), ds[a]=0;
}
while(Q.size()>0){
int nd=Q.top().ss;
Q.pop();
if(vis[nd])
continue;
vis[nd]=1;
for(auto i:e[nd]){
int yol=i.ss;
int to=i.ff;
if(!vis[to] and ds[nd]+yol < ds[to])
ds[to]=ds[nd]+yol, Q.push({ds[to], to});
}
}
vector<pii>v;
for(int i=1; i<=n; i++)
v.pb({ds[i], i});
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
cin>>q;
for(int i=1; i<=q; i++){
int a, b;
cin>>a>>b;
int l=0, r=v[0].ff;
while(l<=r){
int md=(l+r)/2;
for(int j=1; j<=n; j++)
p[j]=j;
memset(vis, 0, sizeof(vis));
int x=0;
while(x < v.size() and v[x].ff>=md){
dsu(v[x].ss);
vis[v[x].ss]=1;
x++;
}
if(p[ata(a)]==p[ata(b)])
l=md+1;
else
r=md-1;
}
cout<<r<<'\n';
}
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/
컴파일 시 표준 에러 (stderr) 메시지
plan.cpp: In function 'int main()':
plan.cpp:78:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(x < v.size() and v[x].ff>=md){
~~^~~~~~~~~~
# | 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... |