이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#define int long long
using namespace std;
const int inf = 1e18;
const int mxN = 1e5 + 10;
int n, m, s, t, U, V;
vector<vector<pair<int, int>>> adj(mxN);
vector<vector<int>> d(5, vector<int> (mxN));
void SP(int type, int x){
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for(int i = 1; i <= n; i ++){
d[type][i] = inf;
}
d[type][x] = 0;
pq.push({0, x});
while(!pq.empty()){
int du = pq.top().first;
int u = pq.top().second;
pq.pop();
if(d[type][u] != du) continue ;
for(auto [v, w] : adj[u]){
if(d[type][v] > du + w){
d[type][v] = du + w;
pq.push({d[type][v], v});
}
}
}
}
int Res;
int check[mxN], mark[mxN];
int M1[mxN], M2[mxN];
vector<vector<int>> k(mxN);
void dfs(int u){
check[u] = 1;
M1[u] = d[1][u];
M2[u] = d[2][u];
for(int v : k[u]){
if(check[v] == 0) dfs(v);
if(mark[v] == 1){
mark[u] = 1;
M1[u] = min(M1[u], M1[v]);
M2[u] = min(M2[u], M2[v]);
}
}
Res = min({Res, d[1][u] + M2[u], d[2][u] + M1[u]});
}
signed main(){
#define name "test"
if(fopen(name".inp", "r")){
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> s >> t >> U >> V;
vector<array<int, 3>> edges;
for(int i = 1; i <= m; i ++){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
edges.push_back({u, v, w});
}
SP(0, s);
SP(1, U);
SP(2, V);
for(auto [u, v, w] : edges){
if(d[0][u] + w == d[0][v]) k[u].push_back(v);
if(d[0][v] + w == d[0][u]) k[v].push_back(u);
}
mark[t] = 1;
for(int i = 1; i <= n; i ++){
M1[i] = M2[i] = inf;
}
Res = d[1][V];
dfs(s);
cout << Res << "\n";
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void SP(long long int, long long int)':
commuter_pass.cpp:29:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
29 | for(auto [v, w] : adj[u]){
| ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
88 | for(auto [u, v, w] : edges){
| ^
commuter_pass.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | freopen(name".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | freopen(name".out", "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... |