이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <queue>
#include <set>
using namespace std;
using ll = long long;
#define int ll
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define ii pair<int,int>
#define F first
#define S second
const int MAXN = 1e5+5;
vector<ii> adj[MAXN];
int n, m, s, t, u, v;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
fore(i, 0, m){
int x, y, c;
cin >> x >> y >> c;
adj[x].push_back({y, c});
adj[y].push_back({x, c});
}
auto dijkstra = [&](int r, vi &dis) -> void {
dis[r] = 0;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, r});
while(sz(pq)){
auto [cost, node] = pq.top();
pq.pop();
if(cost != dis[node]) continue;
for(auto [to, c] : adj[node]){
if(dis[node] + c < dis[to]){
dis[to] = dis[node] + c;
pq.push({dis[to], to});
}
}
}
};
vi du(n+1, 4e18), dv(n+1, 4e18), ds(n+1, 4e18);
dijkstra(u, du);
dijkstra(v, dv);
auto dijkstraDag = [&](int r, vi &dis) -> vector<vi> {
vector<vi> parent(n+1);
dis[r] = 0;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, r});
while(sz(pq)){
auto [cost, node] = pq.top(); pq.pop();
if(dis[node] != cost) continue;
for(auto [to, w] : adj[node]){
if(cost + w < dis[to]){
parent[to].clear();
parent[to].push_back(node);
dis[to] = cost + w;
pq.push({dis[to], to});
}
else if(cost + w == dis[to]){
parent[to].push_back(node);
}
}
}
return parent;
};
vector<vi> parent = dijkstraDag(s, ds);
vector<bool> sirve(n+1);
vi st;
st.push_back(t);
while(sz(st)){
int cur = st.back();
sirve[cur] = 1;
st.pop_back();
for(auto xx : parent[cur]){
if(sirve[xx]) continue;
st.push_back(xx);
}
}
vector<vi> dag(n+1);
fore(i, 1, n+1){
for(auto xx : parent[i]){
dag[xx].push_back(i);
}
}
int ans = du[v];
vector<int> dp(n+1, -1);
auto f = [&](auto self, int node, int who) -> int {
int &res = dp[node];
if(sirve[node] == 0) return res = 4e18;
if(res > -1){
return res;
}
if(who == u){
res = du[node];
} else {
res = dv[node];
}
for(int to : dag[node]){
res = min(res, self(self, to, who));
}
// cerr << "\n============\n";
// cerr << "result para nodo " << node << ": " << res << endl;
return res;
};
fore(x, 1, n+1){
int res = f(f, x, v) + du[x];
ans = min(ans, res);
}
fill(all(dp), -1);
fore(x, 1, n+1){
int res = f(f, x, u) + dv[x];
ans = min(ans, res);
}
// fore(i, 1, n+1){
// cerr << "para nodo " << i << ": ";
// for(auto xx : parent[i]){
// cerr << xx << ' ';
// }
// cerr << "\n===================\n";
// }
cout << ans;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:50:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
50 | auto [cost, node] = pq.top();
| ^
commuter_pass.cpp:55:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
55 | for(auto [to, c] : adj[node]){
| ^
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:77:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | auto [cost, node] = pq.top(); pq.pop();
| ^
commuter_pass.cpp:81:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | for(auto [to, w] : adj[node]){
| ^
# | 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... |