Submission #399868

#	Time	Username	Problem	Language	Result	Execution time	Memory
399868		fvogel499	Commuter Pass (JOI18_commuter_pass)	C++14	24 / 100	1468 ms	27376 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

#define int long long
#define pii pair<ll, ll>
#define siz 100000
#define inf 1e18
#define ll long long
#define compSign >

int distFromB [siz];
int distFromA [siz];
int distFromDest [siz][4];

struct cdfb { bool operator()(int a, int b) { return (distFromB[a] compSign distFromB[b]); } };

struct cdfa { bool operator()(int a, int b) { return (distFromA[a] compSign distFromA[b]); } };

struct cdfd { bool operator()(pii a, pii b) { return (distFromDest[a.first][a.second] compSign distFromDest[b.first][b.second]); } };

int32_t main() {
	int nbNodes, nbEdges;
	cin >> nbNodes >> nbEdges;
	int passA, passB;
	cin >> passA >> passB;
	passA--;
	passB--;
	int origin, destination;
	cin >> origin >> destination;
	origin--;
	destination--;

	vector<vector<pii>> graph(nbNodes);
	for (int i = 0; i < nbEdges; i++) {
		int la, lb, lw;
		cin >> la >> lb >> lw;
		la--;
		lb--;
		graph[la].push_back(pii(lb, lw));
		graph[lb].push_back(pii(la, lw));
	}

	bool proc [nbNodes];
	for (int i = 0; i < nbNodes; i++) {
		proc[i] = false;
		distFromB[i] = inf;
	}
	priority_queue<int, vector<int>, cdfb> pq1;
	distFromB[passB] = 0;
	pq1.push(passB);
	while (!pq1.empty()) {
		int cn = pq1.top();
		pq1.pop();
		if (proc[cn]) continue;
		proc[cn] = true;
		for (pii ne : graph[cn]) {
			int nn = ne.first;
			int nd = distFromB[cn]+ne.second;
			if (nd < distFromB[nn]) {
				distFromB[nn] = nd;
				pq1.push(nn);
			}
		}
	}

	for (int i = 0; i < nbNodes; i++) {
		proc[i] = false;
		distFromA[i] = inf;
	}
	priority_queue<int, vector<int>, cdfa> pq2;
	distFromA[passA] = 0;
	pq2.push(passA);
	while (!pq2.empty()) {
		int cn = pq2.top();
		pq2.pop();
		if (proc[cn]) continue;
		proc[cn] = true;
		for (pii ne : graph[cn]) {
			int nn = ne.first;
			int nd = distFromA[cn]+ne.second;
			if (nd < distFromA[nn]) {
				distFromA[nn] = nd;
				pq2.push(nn);
			}
		}
	}

	set<pii> stbEdges;
	for (int i = 0; i < nbNodes; i++) {
		for (pii j : graph[i]) {
			if (distFromB[i] < distFromB[j.first] and distFromB[i]+distFromA[j.first]+j.second == distFromB[passA]) {
				stbEdges.insert(pii(i, j.first));
			}
		}
	}

	bool procState [nbNodes][4];
	for (int i = 0; i < nbNodes; i++) for (int j = 0; j < 4; j++) {
		procState[i][j] = false;
		distFromDest[i][j] = inf;
	}
	priority_queue<pii, vector<pii>, cdfd> q;
	distFromDest[origin][0] = 0;
	q.push(pii(origin, 0));
	while (!q.empty()) {
		int cn = q.top().first;
		int cs = q.top().second;
		q.pop();
		if (procState[cn][cs]) continue;
		proc[cn] = true;
		for (pii ne : graph[cn]) {
			int nn = ne.first;
			if (cs != 3 and cs != 2 and stbEdges.find(pii(cn, nn)) != stbEdges.end()) {
				int nd = distFromDest[cn][cs];
				int ns = 1;
				if (nd < distFromDest[nn][ns]) {
					distFromDest[nn][ns] = nd;
					q.push(pii(nn, ns));
				}
			}
			else if (cs != 3 and cs != 1 and stbEdges.find(pii(nn, cn)) != stbEdges.end()) {
				int nd = distFromDest[cn][cs];
				int ns = 2;
				if (nd < distFromDest[nn][ns]) {
					distFromDest[nn][ns] = nd;
					q.push(pii(nn, ns));
				}
			}
			int nd = distFromDest[cn][cs]+ne.second;
			int ns = 0;
			if (cs != 0) ns = 3;
			if (nd < distFromDest[nn][ns]) {
				distFromDest[nn][ns] = nd;
				q.push(pii(nn, ns));
			}
		}
	}

	int minD = inf;
	for (int i = 0; i < 4; i++) minD = min(minD, distFromDest[destination][i]);

	cout << minD;

	int d = 0;
	d++;
}

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