Submission #1108317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108317		mncuchiinhuttt	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	374 ms	40096 KiB

commuter_pass

/*
	Author: Vo Minh Long
	Codeforces: mncuchiinhuttt
	CBT '25
*/

#include <iostream>
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <bitset>
#include <unordered_set>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

#define long        long long

#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define yuri ios::sync_with_stdio(0);
#define is cin.tie(0);
#define dabet cout.tie(0);
#define showTime() cerr << '\n' << "Running time: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define NAME "zha"
#define len(a) (int)(a.size())
#define all(a) (a).begin(), (a).end()

const int N = 1e5 + 7;
const int BASE = 307;
const int INT_inf = 2e9;
const long LL_inf = 9e18;
const double eps = 1e-6;
const short dx[] = {1, 0, -1, 0};
const short dy[] = {0, 1, 0, -1};
const pair<long, long> MOD = {1e9 + 7, 998244353};

template<typename T1, typename T2> bool maximize(T1& a, T2 b){if(a < b) return a = b, 1; return 0;}
template<typename T1, typename T2> bool minimize(T1& a, T2 b){if(a > b) return a = b, 1; return 0;}
template<typename T1> T1 abs(T1 a){return a < 0 ? -a : a;}
template<typename T1> T1 sqr(T1 a){ return a * a; }

inline int readInt() { char c; int ans = 0; while ((c = getchar()) < '0' or c > '9'); ans = c - '0'; while ((c = getchar()) >= '0' and c <= '9') ans = ans * 10 + c - '0'; return ans; }
inline long readLong() { char c; long ans = 0; while ((c = getchar()) < '0' or c > '9'); ans = c - '0'; while ((c = getchar()) >= '0' and c <= '9') ans = ans * 10 + c - '0'; return ans; }
inline string readString() { string ans = ""; char c; while ((c = getchar()) < 33); ans.push_back(c); while ((c = getchar()) >= 33) ans.push_back(c); return ans; }

int n, m, s, t, s1, t1;
vector<pair<int, int> > adj[N];

void setData();
void solve();

int main()
{
	setData();
	solve(); 
}

void setData()
{
	yuri is dabet
	if (fopen(NAME".INP", "r"))
		freopen(NAME".INP", "r", stdin),
		freopen(NAME".OUT", "w", stdout);
	scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &s1, &t1);
	for (int i = 1; i <= m; ++i)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
}

void solve()
{
	priority_queue<array<long, 3> > q;
	vector<vector<long> > dist(n + 1, vector<long>(2, 1e18));
	q.push({dist[s1][0] = 0, s1, 0});
	q.push({dist[t1][1] = 0, t1, 1});
	while (!q.empty())
	{
		array<long, 3> u = q.top();
		q.pop();
		u[0] = -u[0];
		if (u[0] != dist[u[1]][u[2]])
			continue;
		for (const pair<int, int>& v : adj[u[1]])
			if (minimize(dist[v.first][u[2]], dist[u[1]][u[2]] + v.second))
				q.push({-dist[v.first][u[2]], v.first, u[2]});
	}
	long answer = dist[t1][0];
	vector<long> d(n + 1, 1e18);
	function<void(int, int)> find = [&] (const int& begin, const int& end) {
		vector<vector<long> > dp(n + 1, vector<long>(2, 1e18));
		vector<bool> vis(n + 1, false);
		priority_queue<array<long, 3> > q;
		q.push({0, begin, 0});
		while (!q.empty())
		{
			array<long, 3> u = q.top();
			q.pop();
			u[0] = -u[0];
			if (vis[u[1]] == false)
			{
				vis[u[1]] = true;
				d[u[1]] = u[0];
				dp[u[1]][0] = min(dist[u[1]][0], dp[u[2]][0]);
				dp[u[1]][1] = min(dist[u[1]][1], dp[u[2]][1]);
				for (const pair<int, int>& v : adj[u[1]])
					q.push({-u[0] - v.second, v.first, u[1]});
			}
			else if (u[0] == d[u[1]] and min(dist[u[1]][0], dp[u[2]][0]) + min(dist[u[1]][1], dp[u[2]][1]) <= dp[u[1]][0] + dp[u[1]][1])
			{
				dp[u[1]][0] = min(dist[u[1]][0], dp[u[2]][0]);
				dp[u[1]][1] = min(dist[u[1]][1], dp[u[2]][1]);
			}
		}
		minimize(answer, dp[end][0] + dp[end][1]);
	};
	find(s, t);
	find(t, s);
	printf("%lld\n", answer);
}

/* Some notes:

*/

Compilation message (stderr)

commuter_pass.cpp: In function 'void setData()':
commuter_pass.cpp:78:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   freopen(NAME".INP", "r", stdin),
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:79:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   freopen(NAME".OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &s1, &t1);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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