Submission #156507

#	Time	Username	Problem	Language	Result	Execution time	Memory
156507		staniewzki	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	522 ms	22888 KiB

commuter_pass

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

ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.first << ", " << p.second << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
template<class T> int size(T && a) { return a.size(); }

using LL = long long;
using PII = pair<int, int>;

vector<vector<PII>> graph;
vector<LL> get_dist(int n, int s) {
	vector<LL> dist(n, 1e18);
	priority_queue<pair<LL, int>> Q;
	auto push = [&](int v, LL d) { 
		dist[v] = d;
		Q.emplace(-dist[v], v);
	};
	push(s, 0);

	while(!Q.empty()) {
		int v = Q.top().ND;
		Q.pop();
		for(PII e : graph[v]) {
			if(dist[e.ST] > dist[v] + e.ND)
				push(e.ST, dist[v] + e.ND);
		}
	}
	return dist;
}

vector<bool> vis;
vector<vector<int>> directed;
void dfs(int v, vector<LL> &d) {
	vis[v] = true;
	for(PII e : graph[v]) {
		if(d[v] == d[e.ST] + e.ND) {
			directed[v].emplace_back(e.ST);
			if(not vis[e.ST])
				dfs(e.ST, d);
		}
	}
}

vector<int> get_topologic_order(int n) {
	vector<int> ret, deg(n), Q;
	REP(i, n) for(int u : directed[i]) deg[u]++;	
	REP(i, n) if(deg[i] == 0) Q.emplace_back(i);

	while(!Q.empty()) {
		int v = Q.back();
		Q.pop_back();
		ret.emplace_back(v);
		for(int u : directed[v]) {
			if(--deg[u]	== 0)
				Q.emplace_back(u);
		}
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	
	int s, t, u, v;
	cin >> s >> t >> u >> v;
	s--, t--, u--, v--;
	graph.resize(n);
	REP(i, m) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a - 1].emplace_back(b - 1, c);
		graph[b - 1].emplace_back(a - 1, c);
	}

	auto dist_u = get_dist(n, u);
	auto dist_v = get_dist(n, v);
	auto dist_s = get_dist(n, s);
	auto dist_t = get_dist(n, t);

	debug(dist_s, dist_t);
	directed.resize(n);
	vis.resize(n);
	dfs(s, dist_t);

	vector<int> ord = get_topologic_order(n);
	vector<LL> min_u(n, 1e18), min_v(n, 1e18);
	LL ans = 1e18;

	for(int i : ord) {
		min_u[i] = min(min_u[i], dist_u[i]);
		min_v[i] = min(min_v[i], dist_v[i]);
		ans = min(ans, dist_u[i] + min_v[i]);
		ans = min(ans, min_u[i] + dist_v[i]);
		for(int j : directed[i]) {
			min_u[j] = min(min_u[j], min_u[i]);
			min_v[j] = min(min_v[j], min_v[i]);
		}
	}

	cout << ans << "\n";
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:117:23: warning: statement has no effect [-Wunused-value]
  debug(dist_s, dist_t);
                       ^

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