이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define int long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 1e5 + 9 , mod = 1e9 + 7;
ll a[N];
ll n , m , q , k;
vector<pair<int,int>>v[N];
set<pair<int,int>>st;
void dijkstra(){
while(st.size()){
auto it = st.begin();
ll x = it->se;
ll y = it->fi;
st.erase(it);
if(a[x] != y)
continue;
for(auto to : v[x]){
if(a[x] + to.se < a[to.fi]){
a[to.fi] = a[x] + to.se;
st.insert({a[to.fi] , to.fi});
}
}
}
}
ll sz[N] , p[N] , mn[N];
int get(int n){
return (p[n] == n ? n : get(p[n]));
}
void join(int x , int y , int k){
x = get(x);
y = get(y);
if(x != y){
if(sz[x] < sz[y])
swap(x , y);
p[y] = x;
mn[y] = k;
sz[x] += sz[y];
}
}
void get1(int x , int y){
int ans = 1e9;
while(true){
if(sz[x] < sz[y]){
ans = min(ans , mn[x]);
if(p[x] == y){
cout<<min(mn[x] , ans)<<"\n";
return;
}
x = p[x];
}else{
ans = min(ans , mn[y]);
if(p[y] == x){
cout<<min(mn[y] , ans)<<"\n";
return;
}
y = p[y];
}
/*if(x == y){
cout<<0<<"\n";
return;
}*/
}
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= m; i++){
int x , y , z;
cin>>x>>y>>z;
v[x].pb({y , z});
v[y].pb({x , z});
}
cin>>k;
for(int i = 1; i <= n; i++){
a[i] = 1e9;
}
while(k--){
int x;
cin>>x;
a[x] = 0;
st.insert({0 , x});
}
dijkstra();
vector<pair<int,int>>g;
for(int i = 1; i <= n; i++){
p[i] = i;
sz[i] = 1;
g.push_back({a[i] , i});
}
sort(rall(g));
for(auto i : g){
for(auto to : v[i.se]){
if(a[to.fi] >= a[i.se]){
join(i.se , to.fi , a[i.se]);
}
}
}
cin>>q;
while(q--){
int x , y;
cin>>x>>y;
get1(x , y);
}
}
signed main(){
TL;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif*/
int t = 1;
//cin>>t;
while(t--)
{
solve();
}
}
// Author : حسن
컴파일 시 표준 에러 (stderr) 메시지
plan.cpp:136:11: warning: extra tokens at end of #endif directive [-Wendif-labels]
136 | #endif*/
| ^
plan.cpp: In function 'int main()':
plan.cpp:134:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:135:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
135 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |