Submission #208814

#	Time	Username	Problem	Language	Result	Execution time	Memory
208814		Siberian	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2097 ms	18772 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}
#define int ll
struct edge{
	int to, cost;
	edge() {}
	edge(int _to, int _cost) {
		to = _to, cost = _cost;
	}
};

const int MAXN = 1e5 + 10;
vector<edge> g[MAXN];
int n, m;
int s1, t1;
int s2, t2;

void read() {
	cin >> n >> m;
	cin >> s1 >> t1;
	s1--;
	t1--;
	cin >> s2 >> t2;
	s2--;
	t2--;
	for (int i = 0; i < m; i++) {
		int u, v;
		int c;
		cin >> u >> v >> c;
		u--;
		v--;
		g[u].push_back({v, c});
		g[v].push_back({u, c});
	}
}

const ll INF = 1e18;
ll ans;

vector<ll> djkstra(int v) {
	vector<ll> d(n, INF);
	set<pair<ll, int>> q;
	d[v] = 0;
	q.insert({0, v});
	while (!q.empty()) {
		int v = q.begin()->second;
		//cout << v << " " << d[v] << endl;
		q.erase(q.begin());
		for (auto [to, cost] : g[v]) {
			if (d[to] <= d[v] + cost) continue;
			q.erase({d[to], to});
			d[to] = d[v] + cost;
			q.insert({d[to], to});
		}
	}
	return d;
}

vector<ll> dist;

void build() {
	auto d = djkstra(s1);
	/*cout << "d = " << endl;
	for (auto i : d) {
		cout << i << " ";
	}
	cout << endl;*/
	//exit(0);
	dist.assign(n, INF);
	queue<int> q;
	q.push(t1);
	dist[t1] = d[t1];
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (auto [to, cost] : g[v]) {
			if (dist[to] != INF) continue;
			if (d[to] + cost != d[v]) continue;
			dist[to] = d[to];
			q.push(to);
		}
	}
}

vector<ll> dp;
vector<bool> used;

ll dfs(int v) {
	if (used[v]) return dp[v];
	used[v] = true;
	for (auto [to, cost] : g[v]) {
		if (dist[v] + cost != dist[to]) continue;
		chkmin(dp[v], dfs(to));
	}
	return dp[v];
}

bool check(int v, int need) {
	if (v == need) return true;
	for (auto [to, cost] : g[v]) {
		if (dist[to] != dist[v] + cost) continue;
		if (check(to, need)) return true;
	}
	return false;
}

void run() {
	build();
	/*cout << "dist = " << endl;
	for (auto i : dist) {
		cout << i << " ";
	}
	cout << endl;*/
	//dp = djkstra(t2);
	//used.assign(n, false);
	//dfs(s1);
	vector<ll> S = djkstra(s2);
	vector<ll> T = djkstra(t2);
	ans = S[t2];
	for (int i = 0; i < n; i++) {
		if (dist[i] == INF) continue;
		for (int j = 0; j < n; j++) {
			if (dist[j] == INF) continue;
			if (!check(i, j)) continue;
			chkmin(ans, S[i] + T[j]);
		}
	}
	//ans = have[t2];
	//for (int i = 0; i < n; i++) {
	//	if (dist[i] == INF) continue;
	//	chkmin(ans, dp[i] + have[i]);
	//}
}

void write() {
	cout << ans << endl;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	read();
	run();
	write();
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'std::vector<long long int> djkstra(ll)':
commuter_pass.cpp:57:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [to, cost] : g[v]) {
             ^
commuter_pass.cpp: In function 'void build()':
commuter_pass.cpp:84:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [to, cost] : g[v]) {
             ^
commuter_pass.cpp: In function 'll dfs(ll)':
commuter_pass.cpp:99:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [to, cost] : g[v]) {
            ^
commuter_pass.cpp: In function 'bool check(ll, ll)':
commuter_pass.cpp:108:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [to, cost] : g[v]) {
            ^

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