Submission #1185474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185474		badge881	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	294 ms	21892 KiB

commuter_pass

#include<bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define int long long
#define pb push_back

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), y = calc(B), z = calc(C), 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(min(ans, pz[i] + t[i]), pt[i] + z[i]);
	}
	cout << ans;
}
signed main() { 
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL); 
  solve(); 
  return 0;
}

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