Submission #1195714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195714		pete555	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	313 ms	16784 KiB

commuter_pass

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

#define pi pair<int,int>
#define ll long long
#define pb push_back
#define pf push_front

void fileIO(string filename) {
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}

vector<pi> adj[100001];
ll du[100001], dv[100001], ds[100001], dp[2][100001], ans;

void dijkstra(int u, ll d[]) {
	fill(d, d + 100001, LLONG_MAX / 2);

	priority_queue<pair<ll, int>> pq;
	pq.push({d[u] = 0, u});
	while(!pq.empty()) {
		auto [cdist, u] = pq.top();
		pq.pop();
		cdist *= -1;
		if(cdist > d[u]) continue;
		for(const auto [v, w] : adj[u]) {
			ll new_len = cdist + w;
			if(new_len < d[v]) {
				d[v] = new_len;
				pq.push({-d[v], v});
			}
		}
	}
}

void dijkstra2(int start, int end) {
	fill(dp[0], dp[0] + 100001, LLONG_MAX / 2);
	fill(dp[1], dp[1] + 100001, LLONG_MAX / 2);
	fill(ds, ds + 100001, LLONG_MAX / 2);

	priority_queue<pair<ll, pair<int, int>>> pq;
	pq.push({0, {start, 0}});

	while(!pq.empty()) {
		ll cdist = pq.top().first;
		auto [u, par] = pq.top().second;
		pq.pop();
		cdist *= -1;
		if(cdist > ds[u]) continue;

		if(ds[u] == LLONG_MAX / 2) {
			ds[u] = cdist;
			dp[0][u] = min(du[u], dp[0][par]);
			dp[1][u] = min(dv[u], dp[1][par]);
			for(const auto [v, w] : adj[u]) {
				if(ds[u] + w <= ds[v]) pq.push({-(cdist + w), {v, u}});
			}
		}
		else if(cdist == ds[u]) {
			if (min(du[u], dp[0][par]) + min(dv[u], dp[1][par]) <=
			    dp[0][u] + dp[1][u]) {
				dp[0][u] = min(du[u], dp[0][par]);
				dp[1][u] = min(dv[u], dp[1][par]);
			}
		}
	}
	ans = min(ans, dp[0][end] + dp[1][end]);
}

int main()
{
	cin.tie(0)->sync_with_stdio(false);
	//fileIO("");
	int n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	for(int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		adj[a].pb({b, w});
		adj[b].pb({a, w});
	}
	dijkstra(u, du);
	dijkstra(v, dv);

	ans = du[v];

	dijkstra2(s, t);
	dijkstra2(t, s);

	cout << ans << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void fileIO(std::string)':
commuter_pass.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen((filename + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen((filename + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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