이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class A, class B>
ostream& operator<<(ostream& o, const pair<A, B>& p) {return o << '(' << p.first << ", " << p.second << ')';}
template<size_t Index = 0, typename... Types>
ostream& printTupleElements(ostream& o, const tuple<Types...>& t) {if constexpr (Index < sizeof...(Types)){if(Index > 0){o << ", ";}o << get<Index>(t);printTupleElements<Index + 1>(o, t);}return o;}
template<typename... Types>
ostream& operator<<(ostream& o, const tuple<Types...>& t){o << "(";printTupleElements(o, t);return o << ")";}
template<class T>
auto operator<<(ostream& o, const T& x) -> decltype(x.end(), o){o << '{';bool first = true;for (const auto& e : x){if (!first){o << ", ";}o << e;first = false;} return o << '}';}
//#define DEBUG
#ifdef DEBUG
#define fastio()
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#define check(x) if (!(x)) { cerr << "Check failed: " << #x << " in line " << __LINE__ << endl; exit(1); }
#else
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(...)
#define check(x)
#endif
typedef long long ll;
#define pi pair<int, int>
#define pl pair<ll, ll>
#define st first
#define nd second
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
constexpr int LIM = 1e5;
constexpr ll INF = 1e18;
struct res{
pl minsum = make_pair(INF, INF);
pl minA = make_pair(INF, INF);
pl minB = make_pair(INF, INF);
};
gp_hash_table<int, ll>dist[LIM + 10];
res ans[LIM + 10];
vector<pi>g[LIM + 10];
void dji(int s, int n) {
for(int i = 1; i <= n; i++) {
dist[s][i] = INF;
}
dist[s][s] = 0;
priority_queue<pair<ll, int> >q;
q.emplace(0, s);
while(!q.empty()) {
int v = q.top().nd;
ll d = -q.top().st;
q.pop();
if(dist[s][v] == d) {
for(auto &[u, val] : g[v]) {
if(dist[s][u] > dist[s][v] + val) {
dist[s][u] = dist[s][v] + val;
q.emplace(-dist[s][u], u);
}
}
}
}
}
int U, V;
void cntres(int s, int n) {
for(int i = 1; i <= n; i++) {
dist[s][i] = INF;
}
dist[s][s] = 0;
pl tmp = make_pair(dist[V][s], dist[U][s]);
ans[s].minsum = tmp;
ans[s].minA = tmp;
ans[s].minB = tmp;
priority_queue<pair<ll, int> >q;
q.emplace(0, s);
while(!q.empty()) {
int v = q.top().nd;
ll d = -q.top().st;
q.pop();
if(dist[s][v] == d) {
for(auto &[u, val] : g[v]) {
if(dist[s][u] > dist[s][v] + val) {
dist[s][u] = dist[s][v] + val;
q.emplace(-dist[s][u], u);
}
if(dist[s][u] == dist[s][v] + val) {
debug(v, u);
pl par1 = make_pair(min(ans[v].minsum.st, dist[V][u]), min(ans[v].minsum.nd, dist[U][u]));
pl par2 = make_pair(min(ans[v].minA.st, dist[V][u]), min(ans[v].minA.nd, dist[U][u]));
pl par3 = make_pair(min(ans[v].minB.st, dist[V][u]), min(ans[v].minB.nd, dist[U][u]));
if(ans[u].minsum.st + ans[u].minsum.nd > par1.st + par1.nd) {
ans[u].minsum = par1;
}
if(ans[u].minsum.st + ans[u].minsum.nd > par2.st + par2.nd) {
ans[u].minsum = par2;
}
if(ans[u].minsum.st + ans[u].minsum.nd > par3.st + par3.nd) {
ans[u].minsum = par3;
}
if(ans[u].minA.st > par2.st) {
ans[u].minA = par2;
}
if(ans[u].minB.nd > par3.nd) {
ans[u].minB = par3;
}
}
}
}
}
}
void solve() {
//ifstream cin("nazwa.in");
//ofstream cout("nazwa.out");
int n, m;
cin >> n >> m;
int s, t;
cin >> s >> t;
cin >> V >> U;
for(int i = 1; i <= m; i++) {
int a, b, x;
cin >> a >> b >> x;
g[a].eb(b, x);
g[b].eb(a, x);
}
dji(U, n);
dji(V, n);
for(int i = 1; i <= n; i++) {
//debug(i, dist[U][i], dist[V][i]);
}
cntres(s, n);
for(int i = 1; i <= n; i++) {
//debug(i, ans[i].minsum, ans[i].minA, ans[i].minB);
}
cout << min(dist[V][U], ans[t].minsum.st + ans[t].minsum.nd) << '\n';
}
int main() {
fastio();
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
# | 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... |