Submission #1089461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089461		Nurislam	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	209 ms	22468 KiB

commuter_pass

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

#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long


template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}

constexpr long double EPS = 1e-12;
const int N = 1e6+50, inf = 1e17;
//int mod = 998244353
//int mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)


void solve(){
	int n, m;
	cin >> n >> m;
	int s, t;
	cin >> s >> t;
	int u, v;
	cin >> u >> v;
	vector<vector<array<int, 2>>> g(n+1);
	for(int i = 1; i <= m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		g[a].pb({b, c});
		g[b].pb({a, c});
	}
	
	auto bfs = [&](int ps) -> vector<int>{
		vector<int> dp(n+1, inf);
		dp[ps] = 0;
		priority_queue<array<int, 2>> pq;
		pq.push({0, ps});
		while(pq.size()){
			auto [dis, ps] = pq.top();
			pq.pop();
			dis = -dis;
			if(dis > dp[ps])continue;
			for(auto [to, cost]:g[ps])
				if(chmin(dp[to], dp[ps] + cost))
					pq.push({-dp[to], to});
			
		}
		return dp;
	};
	
	vector<int> su, sv, ss;
	su = bfs(u);
	sv = bfs(v);
	ss = bfs(s);
	
	vector<int> umn(n+1, inf), vmn(n+1, inf);
	umn[t] = su[t];
	vmn[t] = sv[t];
	
	priority_queue<array<int,2>> q;
	q.push({ss[t], t});
	int ans = su[v];
	while(q.size()){
		auto [dis, ps] = q.top();
		q.pop();
		chmin(umn[ps], su[ps]);
		chmin(ans, umn[ps] + sv[ps]);
		//cout << ps << ' ' << umn[ps] << ' ' << sv[ps] << '\n';
		for(auto [to, cost]:g[ps]){
			if(ss[to] == ss[ps] - cost && chmin(umn[to], umn[ps]))
				q.push({ss[to], to});
		}
	}
	q.push({ss[t], t});
	while(q.size()){
		auto [dis, ps] = q.top();
		q.pop();
		chmin(vmn[ps], sv[ps]);
		chmin(ans, vmn[ps] + su[ps]);
		//cout << ps << ' ' << vmn[ps] << ' ' << su[ps] << '\n';
		for(auto [to, cost]:g[ps]){
			if(ss[to] == ss[ps] - cost && chmin(vmn[to], vmn[ps]))
				q.push({ss[to], to});
		}
	}
	cout << ans << '\n';
}

 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}
 
 
 
 
 
 
 
 
 
 
 
 
 

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