# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1167406 | GoBananas69 | Commuter Pass (JOI18_commuter_pass) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
typedef long long ll;
using namespace std;
const ll inf = 1e18;
vector<vector<pair<ll, ll>>> adj;
vector<ll> du, dv, ds, dt;
vector<ll> p, path;
vector<bool> vis;
void dijkstra(ll s, vector<ll> &dist) {
fill(vis.begin(), vis.end(), false);
priority_queue<pair<ll, ll>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
ll u = pq.top().second;
// ll w = pq.top().first;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto &p: adj[u]) {
ll v = p.first;
ll w = p.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
}
void find(ll s, ll t) {
vector<ll> dist(adj.size(), inf);
fill(vis.begin(), vis.end(), false);
priority_queue<pair<ll, ll>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
ll u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto &e: adj[u]) {
ll v = e.first;
ll w = e.second;
if (dist[v] > dist[u] + w) {
p[v] = u;
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
for (ll v = t; v != s; v = p[v]) {
path.push_back(v);
}
path.push_back(s);
reverse(path.begin(), path.end());
}
signed main() {
//this solution assumes only one unique minimum path from s to t
cin.tie() -> sync_with_stdio(0);
ll n, m, s, t, a, b;
cin >> n >> m >> s >> t >> a >> b;
adj.resize(n + 1);
dv.resize(n + 1, inf);
du.resize(n + 1, inf);
ds.resize(n + 1, inf);
dt.resize(n + 1, inf);
p.resize(n + 1, -1);
vis.resize(n + 1);
for (ll i = 0; i<m; ++i) {
ll u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dijkstra(a, du);
dijkstra(b, dv);
dijkstra(s, ds);
dijkstra(t, dt);
find(s, t);
for (ll i = 1; i<path.size(); ++i) {
ll u = path[i - 1];
ll v = path[i];
adj[u].push_back({v, 0});
adj[v].push_back({u, 0});
}
// cout << '\n';
res = min(du[b], dv[a]);
ll res1;
if (n <= 300) {
vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, inf));
for (ll i = 1; i<=n; ++i) {
dijkstra(i, dist[i]);
}
res1 = min(du[b], dv[a]);
for(ll i = 1; i<=n; ++i) {
for(ll j = 1; j<=n; ++j) {
if(ds[i] + dt[j] + dist[i][j] == ds[t]) {
res1 = min(res1, du[i] + dv[j]);
res1 = min(res1, du[j] + dv[i]);
}
}
}
res = min(res, res1);
}
cout << res << '\n';
}