Submission #1176542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176542		Tsagana	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	317 ms	21892 KiB

commuter_pass

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;


int n;
int pz[100010], pt[100010];
vector<vector<pair<int, int>>> adj;

vector<int> calc(int a) {
	set<pair<int, int>> s;
	s.insert({0, a});
	vector<int> v(n + 1, 1e18);
	v[a] = 0;
	
	while (!s.empty()) {
		auto curr = s.begin();
		int sum = (*curr).F, i = (*curr).S;
		s.erase(*curr);
	
		if (v[i] < sum) continue ;
		for (auto it: adj[i]) {
			if (v[it.F] > it.S + sum) {
				v[it.F] = it.S + sum;
				s.insert({it.S + sum, it.F});
			}
		}
	}
	return v;
}

void solve () {
	int m;
	cin >> n >> m;
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	adj.resize(n + 1);

	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].pb({b, c});
		adj[b].pb({a, c});
	}
	
	vector<int> x = calc(A);
	vector<int> y = calc(B);
	vector<int> z = calc(C);
	vector<int> t = calc(D);
	vector<pair<int, int>> vp;
	
	for (int i = 1; i <= n; i++) {
		if (x[i] + y[i] == x[B]) {
			vp.pb({x[i], i});
		}
	}
	
	sort(all(vp));
	int ans = z[D];
	
	for (auto i1 : vp) {
		int i = i1.S;
		pz[i] = z[i];
		pt[i] = t[i];
	
		for (auto it : adj[i]) {
			if (x[it.F] + it.S == x[i]) {
				pz[i] = min(pz[i], pz[it.F]);
				pt[i] = min(pt[i], pt[it.F]);
			}
		}
		ans = min(ans, pz[i] + t[i]);
		ans = min(ans, pt[i] + z[i]);
	}
	cout << ans;
}
signed main() {IOS solve(); return 0;}

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