Submission #857599

#	Time	Username	Problem	Language	Result	Execution time	Memory
857599		dio_2	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	1372 ms	15760 KiB

commuter_pass

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

const long long inf = (long long)1e18;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	
	vector<vector<pair<int, int>>> adj(n + 1);
	
	while(m--){
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].emplace_back(b, c);
		adj[b].emplace_back(a, c);
	}
	
	auto Do = [&](int src, vector<long long> &d)->void{
      fill(d.begin(), d.end(), inf);
      vector<bool> in_Q(n + 1);
      d[src] = 0;
      priority_queue<pair<long long, int>> pq;
      pq.push({0, src});
      while(!pq.empty()){
			auto [_, node] = pq.top();		
			pq.pop();
			if(in_Q[node]) continue;
			in_Q[node] = 1;
			for(auto [to, cost] : adj[node]){
				if(d[node] + cost < d[to]){
					d[to] = d[node] + cost;
					pq.push({-d[to], to});
				}
			}
	   }
	};
	
	auto clear_cost = [&](int a, int b)->void{
	  for(auto &[node, _] : adj[a])
		if(node == b) _ = 0;
	  for(auto &[node, _] : adj[b])
		if(node == a) _ = 0;
	};
	
	vector<long long> Ds(n + 1);
	vector<bool> in_sp(n + 1);
	Do(s, Ds);
	
	bool unique = 1;
	
	queue<int> q;
	q.push(t);
	in_sp[t] = 1;
	vector<pair<int, int>> combs;
	
	while(!q.empty()){
		int node = q.front(); q.pop();
		int cnt = 0;
	   for(auto [from, cost] : adj[node]){
			if(Ds[from] + cost == Ds[node] && !in_sp[from]){
				in_sp[from] = 1;
				q.push(from);
				++cnt;
				unique &= (cnt == 1);
				combs.emplace_back(from, node);
			}
		}
	}
	
	if(unique){
		for(auto [a, b] : combs)
			clear_cost(a, b);
	}
	
	vector<long long> Du(n + 1), Dv(n + 1);
	Do(u, Du);
	Do(v, Dv);
	
	
	if(unique){
		
		cout << Du[v] << '\n';
		return 0;
	}
	
	
	if(s == u){
		long long ans = inf;
		for(int i = 1;i <= n;i++)
			if(in_sp[i]) ans = min(ans, Dv[i]);
		cout << ans << '\n';
		return 0;
	}
	
	long long ans = Du[v];
	
	vector<long long> Dt(n + 1);
	Do(t, Dt);
	
	auto in_path = [&](int a, int b)->bool{
		vector<long long> Da(n + 1);
		Do(a, Da);
		return (Ds[t] == Ds[a] + Da[b] + Dt[b]); 
	};
	
	if(n <= 300){
		for(int i = 1;i <= n;i++){
			for(int j = i;j <= n;j++){
				if(!in_sp[i] || !in_sp[j]) continue;
				if(in_path(i, j)){
					ans = min(ans, Du[i] + Dv[j]);
					ans = min(ans, Dv[i] + Du[j]);
				}
			}
		}
	}
	
	
	cout << ans << '\n';

	return 0;
}

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