이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
ll n, m, S, T, U, V, a, b, c, dist[NMAX], ans, cost[NMAX], C1[NMAX], C2[NMAX], vis[NMAX];
vector<pair<int, ll>> adj[NMAX];
void dijk(int s){
memset(dist, 0x3f, sizeof(dist));
priority_queue<pair<ll, ll>> pq;
pq.emplace(0, s); dist[s] = 0;
while(pq.size()){
auto[d, x] = pq.top(); pq.pop();
d = -d;
if(d > dist[x]) continue;
for(auto&[nx, p] : adj[x])
if(d + p < dist[nx]){
dist[nx] = d + p;
pq.emplace(-d-p, nx);
}
}
return;
}
void go(int s, int t){
dijk(s);
priority_queue<pair<ll, ll>> pq;
memset(vis, 0, sizeof(vis));
pq.emplace(dist[t], t); vis[t] = 1;
while(pq.size()){
auto[d, x] = pq.top(); pq.pop();
for(auto&[nx, p]: adj[x])
if(d - p == dist[nx]){
C1[nx] = min(C1[nx], C1[x]);
if(!vis[nx]) vis[nx] = 1, pq.emplace(d-p, nx);
}
}
return;
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> S >> T >> U >> V;
while(m--){
cin >> a >> b >> c;
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
dijk(U);
for(int i = 1; i <= n; i++) C1[i] = C2[i] = dist[i];
ans = dist[V];
go(S, T);
swap(C1, C2);
go(T, S);
for(int i = 1; i <= n; i++) cost[i] = min(C1[i], C2[i]);
dijk(V);
for(int i = 1; i <= n; i++) ans = min(ans, dist[i] + cost[i]);
cout << ans;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void dijk(int)':
commuter_pass.cpp:16:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
16 | auto[d, x] = pq.top(); pq.pop();
| ^
commuter_pass.cpp:19:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
19 | for(auto&[nx, p] : adj[x])
| ^
commuter_pass.cpp: In function 'void go(int, int)':
commuter_pass.cpp:34:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | auto[d, x] = pq.top(); pq.pop();
| ^
commuter_pass.cpp:35:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
35 | for(auto&[nx, p]: adj[x])
| ^
# | 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... |