이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debugger.cpp"
#else
#define debug(...)
#endif
template<class T>
int len(T &a){
return a.size();
}
using ll = long long;
using pii = pair<int,int>;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
string fileio = "";
mt19937 mt(time(nullptr));
const int mod = 1e9 + 7;
const int inf = 1e9;
const ll infl = 1e18;
const int maxn = 1e5 + 1;
void solve(){
int n, m; cin >> n >> m;
int s, t, a, b; cin >> s >> t >> a >> b;
s --; t --; a --; b --;
vector<vector<pair<int,int>>> g(n);
vector<vector<int>> dag(n);
for(int i = 0; i < m; i ++){
int u, v, cost; cin >> u >> v >> cost;
u --; v --;
g[u].push_back({v, cost});
g[v].push_back({u, cost});
}
priority_queue<pair<ll,int>> q;
q.push({0, s});
vector<ll> dis(n, infl);
vector<bool> vis(n);
dis[s] = 0;
while(!q.empty()){
int i = q.top().ss;
q.pop();
if(vis[i]) continue;
vis[i] = 1;
for(auto [u, cost] : g[i]){
if(dis[u] < dis[i] + cost){
continue;
}
if(dis[u] == dis[i] + cost){
dag[u].push_back(i);
}else{
dis[u] = dis[i] + cost;
dag[u] = {i};
q.push({-dis[u], u});
}
}
}
debug(dag);
vector<ll> da(n, infl), db(n, infl);
da[a] = 0;
q.push({0, a});
vis.assign(n, false);
while(!q.empty()){
int i = q.top().ss;
q.pop();
if(vis[i]) continue;
vis[i] = 1;
for(auto [u, cost] : g[i]){
if(da[u] > da[i] + cost){
da[u] = da[i] + cost;
q.push({-da[u], u});
}
}
}
db[b] = 0;
q.push({0, b});
vis.assign(n, false);
while(!q.empty()){
int i = q.top().ss;
q.pop();
if(vis[i]) continue;
vis[i] = 1;
for(auto [u, cost] : g[i]){
if(db[u] > db[i] + cost){
db[u] = db[i] + cost;
q.push({-db[u], u});
}
}
}
vis.assign(n, 0);
vector<ll> mna(n), mnb(n);
ll ans = da[b];
auto dfs = [&](auto &dfs, int i)->void{
vis[i] = 1;
debug(i);
mna[i] = mnb[i] = infl;
for(auto u : dag[i]){
if(!vis[u]){ dfs(dfs, u); }
mna[i] = min({mna[i], mna[u], da[u]});
mnb[i] = min({mnb[i], mnb[u], db[u]});
}
ans = min({ans, da[i] + mnb[i], db[i] + mna[i]});
};
dfs(dfs, t);
debug(mna);
debug(mnb);
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
auto start = chrono::high_resolution_clock::now();
#ifndef LOCAL
if(fileio.size()){
freopen((fileio + ".in").c_str(), "r", stdin);
freopen((fileio + ".out").c_str(), "w", stdout);
}
#endif
int testcases = 1;
#ifdef Tests
cin >> testcases;
#endif
while(testcases --){
solve();
cout << '\n';
#ifdef LOCAL
cout << "_________________________" << endl;
#endif
}
#ifdef LOCAL
auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
cout << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
#endif
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:133:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
133 | auto start = chrono::high_resolution_clock::now();
| ^~~~~
commuter_pass.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
136 | freopen((fileio + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | freopen((fileio + ".out").c_str(), "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... |