제출 #871189

#제출 시각아이디문제언어결과실행 시간메모리
871189aaron_dcoderCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
444 ms48312 KiB
#define 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, road num} vector<vector<pll>> dag_out; //{from, road num} vector<vector<pll>> dag_in; vector<ll> Vdist,Udist; struct stat { ll cost; ll to; ll from; ll roadno; 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,-1}); while (!dijkstraq.empty()) { auto [cost, curr, _1, _2] = 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, -1}); } } } vector<bool> goodnode; void dfsgood(ll node) { goodnode[node]=true; for (auto [next, _] : dag_in[node]) { dfsgood(next); } } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cin >> N >> M >> S >> T >> U >> V; S--; T--; U--; V--; // c assert(U==S); road.assign(N,{}); dag_out.assign(N,{}); dag_in.assign(N,{}); Vdist.assign(N,-1); Udist.assign(N,-1); goodnode.assign(N,false); for (ll i = 0; i < M; ++i) { ll A,B,C; cin >> A >> B >> C; //A--; B--; //c road[A].push_back({B,C}); road[B].push_back({A,C}); } vector<ll> node_cost(N,-1); //node_cost[S] = 0; priority_queue<stat> dijkstraq; dijkstraq.push({0,S,-1,-1}); while (!dijkstraq.empty()) { auto [cost, curr, prev, roadno] = 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, roadno}); dag_in[curr].push_back({prev, roadno}); } for (ll i = 0; i < ll(road[curr].size()); ++i) { auto [next, wi] = road[curr][i]; dijkstraq.push({cost+wi, next, curr,i}); } } dbg("hmm1"); dfsgood(T); dbg("hmm2"); djiktra(V,&Vdist); djiktra(U,&Udist); ll outp=INFTY; ll o2=INFTY; dbg("hmm3"); for (ll i = 0; i < N; ++i) { dbgv(i << " " << Vdist[i] << " " << goodnode[i]); if (goodnode[i]) { outp = min(outp,Vdist[i]); o2 = min(outp,Udist[i]); } } cout << outp+o2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...