Submission #1292064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292064		heast	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	546 ms	24572 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define ii pair<int, ll>
#define ff first
#define ss second
#define pb(x) push_back(x)
#define vii vector<ll>
#define ump unordered_map
#define sz(a) (int)a.size()
#define getbit(i, j) ((i >> j) & 1)
#define addbit(i, j) (i | (1 << j))
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define fto(i, a, b, x) for (int i = a; i <= b; i += x)
#define fdto(i, a, b, x) for (int i = a; i >= b; i -= x)
#define all(x) x.begin(), x.end()

using namespace std;
const ll maxN = 1e5+5;
const ll INF = 1e18;

int n, m, s, t, u, v;
vector<ii> dothi[maxN];
ll d[maxN];

namespace sub1 {

	void dijkstra (int s) {
		fto (i, 1, n, 1) d[i] = INF;
		priority_queue<ii, vector<ii>, greater<ii>> pq;
		d[s] = 0;
		pq.push({0, s});
		while (pq.size()) {
			int u = pq.top().ss; ll du = pq.top().ff;
			pq.pop();
			if (du > d[u]) continue;
			for (ii x : dothi[u]) {
				int v = x.ff; ll w = x.ss;
				if (d[v] > d[u] + w) {
					d[v] = d[u] + w;
					pq.push({d[v], v});
				}
			}
		}
	}

	int vis[maxN];
	vector<int> tt;

	void trace (int u) {
		vis[u] = 1;
		tt.emplace_back(u);
		for (ii x : dothi[u]) {
			int v = x.ff; ll w = x.ss;
			if (vis[v]) continue;
			if (d[v] == d[u] - w) {
				trace(v);
			}
		}
	}


	void solve() {
		dijkstra(s);	
		trace(t);
		dijkstra(v);
		ll ans = INF;
		fto (i, 0, sz(tt)-1, 1) {
			ans = min(ans, d[tt[i]]);
		}
		cout << ans << '\n';
	}
}

namespace sub4 {

	struct dijkstra {

		ll d[maxN];

		void build (int s) {
			fto (i, 1, n, 1) d[i] = INF;
			priority_queue<ii, vector<ii>, greater<ii>> pq;
			d[s] = 0;
			pq.push({0, s});
			while (pq.size()) {
				int u = pq.top().ss; ll du = pq.top().ff;
				pq.pop();
				if (du > d[u]) continue;
				for (ii x : dothi[u]) {
					int v = x.ff; ll w = x.ss;
					if (d[v] > d[u] + w) {
						d[v] = d[u] + w;
						pq.push({d[v], v});
					}
				}
			}
		}
	};

	int vis[maxN];
	dijkstra d[2];
	vector<int> dag[maxN];
	ll f[maxN][2];

	void trace (int u) {
		stack<int> st;
		st.push(u);
		vis[u] = 1;
		while (st.size()) {
			u = st.top();
			st.pop();
			for (ii x : dothi[u]) {
				int v = x.ff; ll w = x.ss;
				if (d[1].d[v] == d[1].d[u] - w) {
					dag[v].emplace_back(u);
					if (!vis[v]) st.push(v);
					vis[v] = 1;
				}
			}
		}
	}

	ll ans = INF;

	void dfs (int u) {
		f[u][0] = d[0].d[u];
		f[u][1] = d[1].d[u];
		vis[u] = 1;
		for (int v : dag[u]) {
			if (vis[v]) {
				f[u][0] = min(f[u][0], f[v][0]);
				f[u][1] = min(f[u][1], f[v][1]);
				continue;
			}
			dfs(v);
			f[u][0] = min(f[u][0], f[v][0]);
			f[u][1] = min(f[u][1], f[v][1]);
		}
		ans = min({ans, f[u][0] + d[1].d[u], f[u][1] + d[0].d[u]});	
	}

	void solve() {
		d[1].build(s);
		trace(t);
		d[0].build(u);
		d[1].build(v);
		fto (i, 1, n, 1) vis[i] = 0;
		dfs(s);
		ans = min(ans, d[0].d[v]);
		cout << ans << '\n';
	}
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    fto (i, 1, m, 1) {
    	int u, v; ll w; cin >> u >> v >> w;
    	dothi[u].emplace_back(v, w);
    	dothi[v].emplace_back(u, w);
    }
    if (s == u) {
    	sub1::solve();
    	return 0;
    }
    sub4::solve();
    cerr << TIME << '\n';
    return 0;
}

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