제출 #871267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871267		aaron_dcoder	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	860 ms	262144 KiB

commuter_pass

#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
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[node]) throw "up";
	goodnode[node]=true;
	for (ll next : dag_in[node])
	{
		if (!goodnode[next]) dfsgood(next);
	}
}

vector<ll> bestVdist;
vector<ll> seen;

ll dfsvcost(ll node) {
	if (seen[node]==2) return bestVdist[node];
	if (seen[node]==1) throw "up";
	seen[node]=1;
	bestVdist[node]=Vdist[node];
	for (ll next : dag_out[node])
	{
		if (goodnode[next]) bestVdist[node] = min(bestVdist[node], dfsvcost(next));
	}
	seen[node]=2;
	return bestVdist[node];
}


vector<ll> bestUdist;

ll dfsucost(ll node) {
	if (seen[node]==2) return bestUdist[node];
		if (seen[node]==1) throw "up";
		seen[node]=1;
	bestUdist[node]=Udist[node];
	dbgv(node);
	for (ll next : dag_out[node])
	{
		dbgv(next);
		if (goodnode[next]) bestUdist[node] = min(bestUdist[node], dfsucost(next));
	}
	seen[node]=2;
	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);
	seen.assign(N,0);

	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);
	seen.assign(N,0);
	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;




}

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