Submission #674533

#	Time	Username	Problem	Language	Result	Execution time	Memory
674533		AmirAli_H1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	487 ms	42760 KiB

commuter_pass

// In the name of Allah

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

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;

#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, m;
int s, t; int x, y;
const int maxn = 2e5 + 4;
const ll oo = 1e18;
vector<pll> adj[maxn];
vector<pair<ll, pii>> E, Ex;
ll dis[maxn]; bool mark[maxn];
ll D[maxn][2];
priority_queue<pll> qu;
ll ans[maxn][3]; bool markx[maxn][3];
priority_queue<pair<ll, pii>> qux;

void dij(int v) {
	fill(dis, dis + n, oo); fill(mark, mark + n, 0);
	dis[v] = 0; qu.push(Mp(-dis[v], v));
	while (!qu.empty()) {
		v = qu.top().S; qu.pop();
		if (mark[v]) continue;
		mark[v] = 1;
		
		for (auto f : adj[v]) {
			auto [u, w] = f;
			if (dis[v] + w < dis[u]) {
				dis[u] = dis[v] + w;
				qu.push(Mp(-dis[u], u));
			}
		}
	}
}

void dij_ans(int v) {
	for (int i = 0; i < n; i++) {
		for (int T = 0; T < 3; T++) {
			ans[i][T] = oo; markx[i][T] = 0;
		}
	}
	for (int T = 0; T < 3; T++) {
		ans[v][T] = 0; qux.push(Mp(-ans[v][T], Mp(v, T)));
	}
	
	while (!qux.empty()) {
		auto [v, t] = qux.top().S; qux.pop();
		if (markx[v][t]) continue;
		markx[v][t] = 1;
		
		for (auto f : adj[v]) {
			auto [u, w] = f;
			int tx = -1;
			if (t == 0) {
				if (w != 0) tx = 0;
				else tx = 1;
			}
			else if (t == 1) {
				if (w != 0) tx = 2;
				else tx = 1;
			}
			else {
				if (w != 0) tx = 2;
			}
			
			if (tx != -1 && ans[v][t] + w < ans[u][tx]) {
				ans[u][tx] = ans[v][t] + w;
				qux.push(Mp(-ans[u][tx], Mp(u, tx)));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	cin >> s >> t;
	s--; t--;
	cin >> x >> y;
	x--; y--;
	
	for (int i = 0; i < m; i++) {
		int u, v; ll w;
		cin >> u >> v >> w;
		u--; v--;
		adj[u].pb(Mp(v, w)); adj[v].pb(Mp(u, w));
		E.pb(Mp(w, Mp(u, v)));
	}
	
	dij(s);
	for (int i = 0; i < n; i++) D[i][0] = dis[i];
	dij(t);
	for (int i = 0; i < n; i++) D[i][1] = dis[i];
	
	for (int i = 0; i < m; i++) {
		ll w = E[i].F; auto [u, v] = E[i].S;
		if (D[u][0] + w + D[v][1] == D[t][0]) {
			Ex.pb(Mp(0, Mp(u, v)));
		}
		if (D[v][0] + w + D[u][1] == D[t][0]) {
			Ex.pb(Mp(0, Mp(v, u)));
		}
	}
	
	ll output = oo;
	for (int T = 0; T < 2; T++) {
		for (auto f : Ex) {
			ll w = f.F; auto [u, v] = f.S;
			if (T == 1) swap(u, v);
			adj[u].pb(Mp(v, w));
		}
		
		dij_ans(x);
		output = min(output, min(min(ans[y][0], ans[y][1]), ans[y][2]));
		
		for (auto f : Ex) {
			ll w = f.F; auto [u, v] = f.S;
			if (T == 1) swap(u, v);
			adj[u].pop_back();
		}
	}
	
	cout << output << endl;
	
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:136:7: warning: unused variable 'w' [-Wunused-variable]
  136 |    ll w = f.F; auto [u, v] = f.S;
      |       ^

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