Submission #513825

#	Time	Username	Problem	Language	Result	Execution time	Memory
513825		Tizariox	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	453 ms	37616 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define F0R1(i, a) for (int i = 1; i <= (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define F0Rd1(i, a) for (int i = a; i > 0; i--)
#define SORT(vec) sort(vec.begin(), vec.end())
#define S0RT(arr, n) sort(arr, arr + n)

#define pA first
#define pB second
#define MOD 1000000007
#define nl "\n"
#define pb push_back

int n, m, s, t, u, v;

class cmp {
  public:
	bool operator()(vector<int> a, vector<int> b) { return a[1] > b[1]; }
};

int dist[100000];
vector<pii> adj[100000];
bool inPass[100000];
unordered_set<int> prevs[100000];

void dijkstra(int root) { // traceback
	for (int i = 0; i < n; i++) {
		dist[i] = 1e9;
	}
	dist[root] = 0;
	priority_queue<vector<int>, vector<vector<int>>, cmp> nodes;
	nodes.push({root, 0, -1});
	while (!nodes.empty()) {
		int node = nodes.top()[0];
		int minDist = nodes.top()[1];
		int parent = nodes.top()[2];
		nodes.pop();
		if (node == t) {
			return;
		}
		if (minDist != dist[node]) {
			continue;
		}
		for (pii i : adj[node]) {
			int neighbor = i.pA;
			int length = i.pB;
			if (dist[node] + length < dist[neighbor]) {
				dist[neighbor] = dist[node] + length;
				nodes.push({neighbor, dist[neighbor], node});
				prevs[neighbor].insert(node);
			} else if (dist[node] + length == dist[neighbor]) {
				prevs[neighbor].insert(node);
			}
		}
	}
}

bool vis[100000];

void dfs(int node) {
	inPass[node] = true;
	vis[node] = true;
	for (int i : prevs[node]) {
		if (!vis[i]) {
			dfs(i);
		}
	}
}

int distU[100000];

int dijkstraU(int root) { // traceback
	for (int i = 0; i < n; i++) {
		distU[i] = 1e9;
	}
	distU[root] = 0;
	priority_queue<vector<int>, vector<vector<int>>, cmp> nodes;
	nodes.push({root, 0, -1});
	while (!nodes.empty()) {
		int node = nodes.top()[0];
		int minDist = nodes.top()[1];
		int parent = nodes.top()[2];
		nodes.pop();
		if (inPass[node]) {
			return minDist;
		}
		if (minDist != distU[node]) {
			continue;
		}
		for (pii i : adj[node]) {
			int neighbor = i.pA;
			int length = i.pB;
			if (distU[node] + length < distU[neighbor]) {
				distU[neighbor] = distU[node] + length;
				nodes.push({neighbor, distU[neighbor], node});
			}
		}
	}
}

int distV[100000];

int dijkstraV(int root) { // traceback
	for (int i = 0; i < n; i++) {
		distV[i] = 1e9;
	}
	distV[root] = 0;
	priority_queue<vector<int>, vector<vector<int>>, cmp> nodes;
	nodes.push({root, 0, -1});
	while (!nodes.empty()) {
		int node = nodes.top()[0];
		int minDist = nodes.top()[1];
		int parent = nodes.top()[2];
		nodes.pop();
		if (inPass[node]) {
			return minDist;
		}
		if (minDist != distV[node]) {
			continue;
		}
		for (pii i : adj[node]) {
			int neighbor = i.pA;
			int length = i.pB;
			if (distV[node] + length < distV[neighbor]) {
				distV[neighbor] = distV[node] + length;
				nodes.push({neighbor, distV[neighbor], node});
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> s >> t >> u >> v;
	s--;
	t--;
	u--;
	v--; 
	// go through and mark every node in shortest paths from S to T as part of the shortest path, since
	// you'll never use more than 1 distinct shortest path going from U to V, as when you switch from one 
	// shortest path to another you're simply creating a new shortest path
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		adj[a].pb(pii(b, c));
		adj[b].pb(pii(a, c));
	}
	dijkstra(s);
	dfs(t);
	cout << min(dijkstraU(u) + dijkstraV(v), distU[v]) << nl;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int)':
commuter_pass.cpp:44:7: warning: unused variable 'parent' [-Wunused-variable]
   44 |   int parent = nodes.top()[2];
      |       ^~~~~~
commuter_pass.cpp: In function 'int dijkstraU(int)':
commuter_pass.cpp:90:7: warning: unused variable 'parent' [-Wunused-variable]
   90 |   int parent = nodes.top()[2];
      |       ^~~~~~
commuter_pass.cpp: In function 'int dijkstraV(int)':
commuter_pass.cpp:121:7: warning: unused variable 'parent' [-Wunused-variable]
  121 |   int parent = nodes.top()[2];
      |       ^~~~~~
commuter_pass.cpp: In function 'int dijkstraU(int)':
commuter_pass.cpp:85:56: warning: control reaches end of non-void function [-Wreturn-type]
   85 |  priority_queue<vector<int>, vector<vector<int>>, cmp> nodes;
      |                                                        ^~~~~
commuter_pass.cpp: In function 'int dijkstraV(int)':
commuter_pass.cpp:116:56: warning: control reaches end of non-void function [-Wreturn-type]
  116 |  priority_queue<vector<int>, vector<vector<int>>, cmp> nodes;
      |                                                        ^~~~~

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