| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1127768 | tsengang | Commuter Pass (JOI18_commuter_pass) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define vodka void
#define ertunt return
using namespace std;
ll n, m, s, t, u, v;
vector<set<pair<ll, ll>>> adj(100004);
ll ans = 1e18;
vector<ll> beff[100004];
vector<bool> visit(100004, 0);
vodka brgdfs(ll x) {
if (visit[x] == 1) {
ertunt;
}
visit[x] = 1;
set<pair<ll, ll>> st;
vector<ll> dist(100005, 1e18);
vector<bool> vis(100005, 0);
st.insert({0, x});
dist[x] = 0;
while (!st.empty()) {
pair<ll, ll> p = *st.begin();
st.erase(p);
if (vis[p.ss]) continue;
vis[p.ss] = 1;
for (auto [y, z] : adj[p.ss]) {
if (dist[p.ss] + z < dist[y]) {
dist[y] = dist[p.ss] + z;
st.insert({dist[y], y});
}
}
}
ans = min(ans, dist[v]);
for (auto y : beff[x]) brgdfs(y);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> s >> t >> u >> v;
for (ll i = 0; i < m; i++) {
ll a, b, c;
cin >> a >> b >> c;
adj[a].insert({b, c});
adj[b].insert({a, c});
}
set<pair<ll, ll>> st;
vector<ll> dist(n + 5, 1e18);
vector<bool> vis(n + 5, 0);
vector<ll> bef(n + 5, -1);
dist[s] = 0;
st.insert({0, s});
if (u == s) {
while (!st.empty()) {
pair<ll, ll> p = *st.begin();
st.erase(p);
if (vis[p.ss]) continue;
vis[p.ss] = 1;
for (auto [x, y] : adj[p.ss]) {
if (dist[x] >= dist[p.ss] + y) {
beff[x].pb(p.ss);
dist[x] = dist[p.ss] + y;
st.insert({dist[x], x});
}
}
}
brgdfs(t);
cout << ans;
ertunt 0;
}
while (!st.empty()) {
pair<ll, ll> p = *st.begin();
st.erase(p);
if (vis[p.ss]) continue;
vis[p.ss] = 1;
for (auto [x, y] : adj[p.ss]) {
if (dist[p.ss] + y < dist[x]) {
dist[x] = dist[p.ss] + y;
st.insert({dist[x], x});
bef[x] = p.ss;
}
}
}
vector<ll> arr;
ll cur = t;
while (cur > 0) {
arr.pb(cur);
cur = bef[cur];
}
reverse(all(arr));
for (ll i = 1; i < arr.size(); i++) {
ll a = arr[i - 1], b = arr[i];
auto it = adj[a].lower_bound({b, -1});
if (it != adj[a].end() && it->ff == b) adj[a].erase(it);
it = adj[b].lower_bound({a, -1});
if (it != adj[b].end() && it->ff == a) adj[b].erase(it);
adj[a].insert({b, 0});
adj[b].insert({a, 0});
beff[b].pb(a);
}
fill(all(dist), 1e18);
st.clear();
dist[u] = 0;
fill(all(vis), 0);
st.insert({0, u});
while (!st.empty()) {
pair<ll, ll> p = *st.begin();
st.erase(p);
if (vis[p.ss]) continue;
vis[p.ss] = 1;
for (auto [x, y] : adj[p.ss]) {
if (dist[p.ss] + y < dist[x]) {
dist[x] = dist[p.ss] + y;
st.insert({dist[x], x});
}
}
}
cout << dist[v];
}