| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 871262 | aaron_dcoder | Commuter Pass (JOI18_commuter_pass) | C++17 | 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.
#undef NDEBUG
#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)
#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 2e18;
ll N,M,S,T,U,V;
//{to,wi}
vector<vector<pll>> road;
//to
vector<vector<ll>> dag_out;
//from
vector<vector<ll>> dag_in;
vector<ll> Vdist,Udist;
struct stat {
ll cost;
ll to;
ll from;
bool operator <(const stat& oth) const {
return cost > oth.cost;
}
};
void djiktra(ll start, vector<ll>* costs) {
priority_queue<stat> dijkstraq;
dijkstraq.push({0,start,-1});
while (!dijkstraq.empty()) {
auto [cost, curr, _] = dijkstraq.top();
dijkstraq.pop();
if ((*costs)[curr] != -1) {
assert((*costs)[curr]<=cost);
continue;
}
(*costs)[curr]=cost;
for (auto [next, wi] : road[curr])
{
dijkstraq.push({cost+wi, next, -1});
}
}
}
vector<bool> goodnode;
void dfsgood(ll node) {
if (goodnode[next]) throw "up";
goodnode[node]=true;
for (ll next : dag_in[node])
{
if (!goodnode[next]) dfsgood(next);
}
}
vector<ll> bestVdist;
ll dfsvcost(ll node) {
if (bestVdist[node]!=-1) return bestVdist[node];
bestVdist[node]=Vdist[node];
for (ll next : dag_out[node])
{
if (goodnode[next]) bestVdist[node] = min(bestVdist[node], dfsvcost(next));
}
return bestVdist[node];
}
vector<ll> bestUdist;
ll dfsucost(ll node) {
if (bestUdist[node]!=-1) return bestUdist[node];
bestUdist[node]=Udist[node];
dbgv(node);
for (ll next : dag_out[node])
{
dbgv(next);
if (goodnode[next]) bestUdist[node] = min(bestUdist[node], dfsucost(next));
}
return bestUdist[node];
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cin >> N >> M >> S >> T >> U >> V;
S--; T--; U--; V--; // cb
road.assign(N,{});
dag_out.assign(N,{});
dag_in.assign(N,{});
Vdist.assign(N,-1);
Udist.assign(N,-1);
goodnode.assign(N,false);
bestVdist.assign(N,-1);
bestUdist.assign(N,-1);
for (ll i = 0; i < M; ++i)
{
ll A,B,C;
cin >> A >> B >> C;
A--; B--; //c
//#warning
road[A].push_back({B,C});
road[B].push_back({A,C});
}
{
vector<ll> node_cost(N,-1);
dbg("hmm0");
priority_queue<stat> dijkstraq;
dijkstraq.push({0,S,-1});
while (!dijkstraq.empty()) {
auto [cost, curr, prev] = dijkstraq.top();
dijkstraq.pop();
//dbg(curr <<":" <<cost);
if (node_cost[curr] != -1 && cost > node_cost[curr]) {
continue;
}
//dbgv(curr <<":" <<cost);
assert(node_cost[curr]==cost || node_cost[curr]==-1);
node_cost[curr] = cost;
if (prev!=-1) {
dag_out[prev].push_back(curr);
dag_in[curr].push_back(prev);
}
for (auto [next, wi] : road[curr])
{
dijkstraq.push({cost+wi, next, curr});
}
}
dbgv(node_cost[T]);
}
//throw exception();
dbg("hmm1");
dfsgood(T);
dbg("hmm2");
djiktra(V,&Vdist);
djiktra(U,&Udist);
dfsucost(S);
dfsvcost(S);
ll outp=Vdist[U];
assert(Vdist[U]==Udist[V]);
// ll o2=INFTY;
dbg("hmm3");
/*for (ll i = 0; i < N; ++i)
{
dbg(i << ":" << Vdist[i] << " " << Udist[i] << " " << goodnode[i]);
if (goodnode[i]) {
outp = min(outp,Vdist[i]);
o2 = min(o2,Udist[i]);
}
}*/
for (ll i = 0; i < N; ++i)
{
dbg(i << ":" << Vdist[i] << " " << Udist[i] << " " << goodnode[i]);
dbg(i << ":" << bestVdist[i] << " " << bestUdist[i] << "=");
dbgv(bestUdist[i]+Vdist[i]);
if (goodnode[i]) {outp = min({outp, bestUdist[i]+Vdist[i], bestVdist[i]+Udist[i]});}
}
cout << outp;
}