Submission #871185

#	Time	Username	Problem	Language	Result	Execution time	Memory
871185		aaron_dcoder	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2036 ms	34012 KiB

commuter_pass

#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, 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=Udist[V];
dbg("hmm3");
	for (ll i = 0; i < N; ++i)
	{
		if (goodnode[i]) outp = min(outp,Vdist[i]);
	}

	cout << outp;




}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45