Submission #846713

#	Time	Username	Problem	Language	Result	Execution time	Memory
846713		VanIOImaster153	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	405 ms	35628 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define task "TUNNEL"
using namespace std;

template<class X, class Y>
bool minimize(X &a, Y b)
{
	if (a > b)
	{
		return a = b, true;
	}
	return false;
}

template<class X, class Y>
bool maximize(X &a, Y b)
{
	if (a < b)
	{
		return a = b, true;
	}
	return false;
}

const int SZ = 2e5 + 5;
int test = 1;
int n, m;
int a, b, c, d;
vector<pair<int, int>> adj[SZ];
int dpc[SZ], dpd[SZ], tmp[SZ], dp[2][SZ];
bool vis[SZ];
int res = 0;

void ReadData()
{
	cin >> n >> m;
	cin >> a >> b >> c >> d;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
}

void Prep1() {
	for (int i = 0; i <= 2e5; i++) {
		vis[i] = false;
	}
	priority_queue<pair<int, int>> pq;
	pq.push({0, c});
	while (!pq.empty()) {
		pair<int, int> p = pq.top();
		pq.pop();
		if (!vis[p.second]) {
			dpc[p.second] = -p.first;
			vis[p.second] = true;
			for (auto q : adj[p.second]) {
				pq.push({p.first - q.second, q.first});
			}
		}
	}
}

void Prep2() {
	for (int i = 0; i <= 2e5; i++) {
		vis[i] = false;
	}
	priority_queue<pair<int, int>> pq;
	pq.push({0, d});
	while (!pq.empty()) {
		pair<int, int> p = pq.top();
		pq.pop();
		if (!vis[p.second]) {
			dpd[p.second] = -p.first;
			vis[p.second] = true;
			for (auto q : adj[p.second]) {
				pq.push({p.first - q.second, q.first});
			}
		}
	}
}

void Dijkstra(int u, int v) {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j <= 2e5; j++) {
			dp[i][j] = 1e18;
		}
	}
	for (int i = 0; i <= 2e5; i++) {
		vis[i] = false;
	}
	priority_queue<pair<int, pair<int, int>>> pq;
	pq.push({0, {u, 0}});
	while (!pq.empty()) {
		pair<int, pair<int, int>> p = pq.top();
		pq.pop();
		if (!vis[p.second.first]) {
			vis[p.second.first] = true;
			tmp[p.second.first] = -p.first;
			dp[0][p.second.first] = min(dpc[p.second.first], dp[0][p.second.second]);
			dp[1][p.second.first] = min(dpd[p.second.first], dp[1][p.second.second]);
			for (auto q : adj[p.second.first]) {
				pq.push({p.first - q.second, {q.first, p.second.first}});
			}
		} else if (-p.first == tmp[p.second.first]) {
			if (min(dpc[p.second.first], dp[0][p.second.second]) + min(dpd[p.second.first], dp[1][p.second.second]) <= dp[0][p.second.first] + dp[1][p.second.first]) {
				dp[0][p.second.first] = min(dpc[p.second.first], dp[0][p.second.second]);
				dp[1][p.second.first] = min(dpd[p.second.first], dp[1][p.second.second]);
			}
		}
	}
	res = min(res, dp[0][v] + dp[1][v]);
}

void Solve()
{
	Prep1();
	Prep2();
	res = dpc[d];
	Dijkstra(a, b);
	Dijkstra(b, a);
	cout << res;
}

signed main()
{
	if (fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//cin >> test;
	while(test--)
	{
		ReadData();
		Solve();
		cout << "\n";
	}
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:131:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:132:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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