Submission #1206937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206937		zyadhany	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	177 ms	33272 KiB

commuter_pass

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>

#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define vi vector<ll>
#define vii vector<vi>
#define vc vector<char>
#define vcc vector<vc>
#define vp vector<pl>
#define mi map<ll,ll>
#define mc map<char,int>
#define sortx(X) sort(X.begin(),X.end());
#define all(X) X.begin(),X.end()
#define allr(X) X.rbegin(),X.rend()
#define ln '\n'
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}
#define MUN {cout << "-1\n"; return;}
using namespace std;

const ll INF = 1e16;

void dijskt(vector<vp> &adj, vi &dp, vii &P, ll src) {
	priority_queue<pl, vp, greater<>> pq;
	pq.push({0, src});
	dp[src]=0;

	while (!pq.empty())
	{
		auto [d, u] = pq.top(); pq.pop();
		if (d != dp[u]) continue;

		for (auto [neg, w] : adj[u]) {
			ll nw = w + d;
			if (nw < dp[neg]) {
				P[neg].clear();
				dp[neg] = nw;
				pq.push({nw, neg});
			}
			if (nw == dp[neg]) P[neg].push_back(u);
		} 
	}
}

void req(vii &adj, vii &radj, vi &vis, vi &dp, ll n) {
	if (vis[n]) return;
	vis[n] = 1;
	for (auto neg : adj[n]) {
		radj[neg].push_back(n);
		req(adj, radj, vis, dp, neg);
		dp[n] = min(dp[n], dp[neg]);
	}
}

void solve(int tc) {
	ll n, m;
	ll s, t, a, b;

	cin >> n >> m;
	cin >> s >> t >> a >> b;

	vector<vp> adj(n + 1);
	for (int i = 0; i < m; i++)
	{
		ll u, v, w; cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	
	vi dis(n+1, INF);
	vii dpdist(2, vi(n+1, INF)), P(n+1);
	dijskt(adj, dpdist[0], P, a);
	dijskt(adj, dpdist[1], P, b);
	P.assign(n+1, vi());
	dijskt(adj, dis, P, s);

	vi dpl(dpdist[0]), dpr(dpdist[0]);
	vii RP(n+1);
	
	vi vis(n + 1);
	req(P, RP, vis, dpl, t);		
	vis.assign(n+1, 0);
	req(RP, P, vis, dpr, s);		

	ll res = INF;
	for (int i = 1; i <= n; i++)
		res = min(res, dpdist[1][i] + min(dpl[i], dpr[i]));
	cout << res << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int size = 1;    

    // freopen("lazy.in", "r", stdin);
    // freopen("lazy.out", "w", stdout);

    // cin >> size;
    for (int i = 1; i <= size ; i++) solve(i);
    return 0;
}

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