| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1093449 | KindaGoodGames | Commuter Pass (JOI18_commuter_pass) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
Need to consider bidirectional path option.
Idea was right, just implementation doesn't work :(
*/
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
using namespace std;
ll INF = numeric_limits<ll>::max() / 2;
int result(int n, int m, int s, int t, int ug, int vg, vector<vector<pii>>& adj, vector<int>&dist, vector<set<int>>& pre) {
// Shortest paths from s to t
priority_queue<tiii, vector<tiii>, greater<tiii>> pq;
// run Dijkstra again
vector<int> dist2(n, INF);
pq.push({ 0,ug,ug });
while (pq.size()) {
int d, v, p;
tie(d, v, p) = pq.top();
pq.pop();
if (dist2[v] <= d) continue;
dist2[v] = d;
for (auto pa : adj[v]) {
pq.push({ pa.second + d, pa.first, v });
}
}
// run Dijkstra again
vector<int> distVG(n, INF);
pq.push({ 0,vg,vg });
while (pq.size()) {
int d, v, p;
tie(d, v, p) = pq.top();
pq.pop();
if (distVG[v] <= d) continue;
distVG[v] = d;
for (auto pa : adj[v]) {
pq.push({ pa.second + d, pa.first, v });
}
}
// SP Graph
vector<vector<int>> adjSP(n);
vector<bool> vis(n);
queue<int> qp;
set<pii> us;
qp.push(t);
while (qp.size()) {
int i = qp.front();
qp.pop();
if (vis[i]) continue;
vis[i] = true;
for (auto u : pre[i]) {
if(!us.count({i,u})){
adjSP[i].push_back(u);
us.insert({i,u});
}
//adjSP[u].push_back(i);
if (!vis[u])qp.push(u);
}
}
// remove add help vertices
queue<tiiii> q; map<pii, int> used;
int mi = dist2[vg];
// cur | pre
q.push({ t,t, INF, INF });
while (q.size())
{
int v, u, d, ds;
tie(v, u, d, ds) = q.front();
q.pop();
//adj[v].push_back({u,0});
// distance to go from any node in path to the goal
int newd = min(d, distVG[v]);
// distance to go to any node in path from start
int newds = min(ds, dist2[v]);
mi = min(mi, newds + newd);
used[{v, u}]++;
for (auto w : adjSP[v]) {
if (used[{w, v}] < 1 && w != v)q.push({ w,v,newd,newds });
//if(!used.count({v,w}) && w != v)q.push({v,w,newd});
}
}
// do the same thing but other way around
used.clear();
q.push({ t,t, INF, INF });
while (q.size())
{
int v, u, d, ds;
tie(v, u, d, ds) = q.front();
q.pop();
//adj[v].push_back({u,0});
// distance to go from any node in path to the goal
int newd = min(d, distVG[v]);
// distance to go to any node in path from start
int newds = min(ds, dist2[v]);
mi = min(mi, newds + newd);
used[{v, u}]++;
for (auto w : adjSP[v]) {
if (used[{w, v}] < 1 && w != v)q.push({ w,v,newd,newds });
//if(!used.count({v,w}) && w != v)q.push({v,w,newd});
}
}
return min(mi, dist2[vg]);
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
int s, t;
cin >> s >> t;
s--; t--;
int ug, vg;
cin >> ug >> vg;
ug--; vg--;
vector<vector<pii>> adj(n);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
a--; b--;
adj[a].push_back({ b,c });
adj[b].push_back({ a,c });
}
// Shortest paths from s to t
vector<int> dists(n, INF);
vector<set<int>> pres(n);
priority_queue<tiii, vector<tiii>, greater<tiii>> pq;
pq.push({ 0,s,s });
while (pq.size()) {
int d, v, p;
tie(d, v, p) = pq.top();
pq.pop();
if (dists[v] < d) continue;
pres[v].insert(p);
if (dists[v] == d) continue;
dists[v] = d;
for (auto pa : adj[v]) {
pq.push({ pa.second + d, pa.first, v });
}
}
// Shortest paths from t to s
vector<int> distt(n, INF);
vector<set<int>> pret(n);
priority_queue<tiii, vector<tiii>, greater<tiii>> pq;
pq.push({ 0,t,t });
while (pq.size()) {
int d, v, p;
tie(d, v, p) = pq.top();
pq.pop();
if (distt[v] < d) continue;
pret[v].insert(p);
if (distt[v] == d) continue;
distt[v] = d;
for (auto pa : adj[v]) {
pq.push({ pa.second + d, pa.first, v });
}
}
// Subcase 1
int a = result(n, m, s, t, ug, vg, adj, dists, pres); int b = result(n, m, t, s, vg, ug, adj, distt, pret);
int c = result(n, m, t,s , ug, vg, adj, distt, pret); int d = result(n, m, s, t, vg ,ug, adj, dists, pres);
cout << min({ a, b}) << endl;
}