이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define el "\n"
#define fu(i, a, b) for (int i = a; i <= b; ++i)
#define fd(i, a, b) for (int i = a; i >= b; --i)
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()
#define sz(v) (ll)(v).size()
#define mask(i) (1LL << (i))
#define bit(x, i) ((x) >> (i) & 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r) {
return uniform_int_distribution<ll>(l, r) (rng);
}
ll last(ll msk) {return msk & (-msk);}
ll pop_cnt(ll msk) {return __builtin_popcountll(msk);}
ll ctz(ll msk) {return __builtin_ctzll(msk);}
ll lg(ll msk) {return 63 - __builtin_clzll(msk);}
template<class T1, class T2> bool minimize(T1 &a, T2 b) {
return a > b ? a = b, 1 : 0;
}
template<class T1, class T2> bool maximize(T1 &a, T2 b) {
return a < b ? a = b, 1 : 0;
}
template<class T> void print(T a) {
for (auto x : a) cout << x << " ";
cout << el;
}
template<class T> void compress(T &a) {
sort(all(a));
a.resize(unique(all(a)) - a.begin());
}
const long long N = 1e5 + 27, inf = 2e18, bl = 320, base = 311, mod = 1e9 + 7, lim = 21;
struct Edge {
ll u, v, w;
Edge(){}
Edge(ll _u, ll _v, ll _w) {
u = _u, v = _v, w = _w;
}
};
ll n, m, s, t, x, y, res = inf;
ll din[N], dout[N], d[N][3];
vector<pair<ll, ll>> adj[N];
vector<ll> dag[N];
Edge edge[2 * N];
void dijkstra(ll s, ll d[]) {
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
fu(i, 1, n) d[i] = inf;
d[s] = 0;
q.push(make_pair(0, s));
while (sz(q)) {
ll u = q.top().ss, dist = q.top().ff;
q.pop();
if (dist > d[u]) continue;
for (pair<ll, ll> tmp : adj[u]) {
ll v = tmp.ff, w = tmp.ss;
if (minimize(d[v], d[u] + w)) q.push(make_pair(d[v], v));
}
}
}
struct Info {
ll u, dist, sta;
Info(){}
Info(ll _u, ll _dist, ll _sta) {
u = _u, dist = _dist, sta = _sta;
}
bool operator < (const Info &other) const {
return dist > other.dist;
}
};
void go() {
memset(d, 0x3f, sizeof(d));
priority_queue<Info> q;
q.push(Info(x, 0, 0));
d[x][0] = 0;
while (sz(q)) {
ll u = q.top().u, dist = q.top().dist, sta = q.top().sta;
q.pop();
if (u == y) return void(minimize(res, dist));
if (dist > d[u][sta]) continue;
for (pair<ll, ll> tmp : adj[u]) {
ll v = tmp.ff, w = tmp.ss;
if (!sta) {
if (minimize(d[v][0], dist + w)) q.push(Info(v, dist + w, 0));
}
else {
if (minimize(d[v][2], dist + w)) q.push(Info(v, dist + w, 2));
}
}
if (sta == 2) continue;
for (ll v : dag[u]) if (minimize(d[v][1], dist)) q.push(Info(v, dist, 1));
}
}
void back() {
memset(d, 0x3f, sizeof(d));
priority_queue<Info> q;
q.push(Info(y, 0, 0));
d[y][0] = 0;
while (sz(q)) {
ll u = q.top().u, dist = q.top().dist, sta = q.top().sta;
q.pop();
if (u == x) return void(minimize(res, dist));
// cout << u << ' ' << dist << ' ' << sta << el;
if (dist > d[u][sta]) continue;
for (pair<ll, ll> tmp : adj[u]) {
ll v = tmp.ff, w = tmp.ss;
if (!sta) {
if (minimize(d[v][0], dist + w)) q.push(Info(v, dist + w, 0));
}
else {
if (minimize(d[v][2], dist + w)) q.push(Info(v, dist + w, 2));
}
}
if (sta == 2) continue;
for (ll v : dag[u]) {
// cout << u << ' ' << v << el;
if (minimize(d[v][1], dist)) q.push(Info(v, dist, 1));
}
}
}
signed main() {
// freopen("bdbang.inp", "r", stdin);
// freopen("bdbang.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> s >> t >> x >> y;
fu(i, 1, m) {
ll u, v, w;
cin >> u >> v >> w;
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
edge[i] = Edge(u, v, w);
}
dijkstra(s, din);
dijkstra(t, dout);
fu(i, 1, m) {
ll u = edge[i].u, v = edge[i].v, w = edge[i].w;
if (din[u] + w + dout[v] == din[t]) dag[u].push_back(v);
if (din[v] + w + dout[u] == din[t]) dag[v].push_back(u);
}
go();
back();
cout << res;
}
# | 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... |