Submission #924631

#	Time	Username	Problem	Language	Result	Execution time	Memory
924631		Baizho	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	469 ms	51912 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
 #pragma GCC optimize("Ofast,unroll-loops,fast-math")
 #pragma GCC target("popcnt")
 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
 
const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(5e5)+100;
const int M = ll(2e5) + 100;
const long long inf = 5e18;
const long double eps = 1e-15L;
 
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }
 
ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}
 
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
 
int n, m, s, t, U, V;
vector<long long> disu(N), disv(N);
vector<pair<long long, long long> > dist(N), diss(N);
vector<pair<int, int> > g[N];

void djik(vector<long long>& dis, int u) {
	for(int i = 1; i <= n; i ++) dis[i] = inf;
	dis[u] = 0;
	set<pair<long long, int> > st;
	st.insert({dis[u], u});
	while(!st.empty()) {
		int v = (*st.begin()).ss;
		st.erase(st.begin());
		for(auto to : g[v]) {
			if(dis[to.ff] > dis[v] + to.ss) {
				if(dis[to.ff] != inf) st.erase({dis[to.ff], to.ff});
				dis[to.ff] = dis[v] + to.ss;;
				st.insert({dis[to.ff], to.ff});
 			}
		}
	}
	
}
  
void Baizho() {
	cin>>n>>m>>s>>t>>U>>V;
	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});
	}
	djik(disu, U); djik(disv, V);
	for(int i = 1; i <= n; i ++) diss[i] = {inf, inf};
	diss[s] = {0, disu[s]};
	set<pair<long long, int> > st;
	st.insert({diss[s].ff, s});
	while(!st.empty()) {
		int v = (*st.begin()).ss;
		st.erase(st.begin());
		for(auto to : g[v]) {
			if(diss[to.ff].ff > diss[v].ff + to.ss) {
				if(diss[to.ff].ff != inf) st.erase({diss[to.ff].ff, to.ff});
				diss[to.ff] = {diss[v].ff + to.ss, min(disu[to.ff], diss[v].ss)};
				st.insert({diss[to.ff].ff, to.ff});
 			} else if(diss[to.ff].ff == diss[v].ff + to.ss) {
 				diss[to.ff].ss = min({diss[to.ff].ss, diss[v].ss, disu[to.ff]});
			 }
		}
	}
	for(int i = 1; i <= n; i ++) dist[i] = {inf, inf};
	dist[t] = {0, disv[t]};
	st.insert({dist[t].ff, t});
	while(!st.empty()) {
		int v = (*st.begin()).ss;
		st.erase(st.begin());
		for(auto to : g[v]) {
			if(dist[to.ff].ff > dist[v].ff + to.ss) {
				if(dist[to.ff].ff != inf) st.erase({dist[to.ff].ff, to.ff});
				dist[to.ff] = {dist[v].ff + to.ss, min(disv[to.ff], dist[v].ss)};
				st.insert({dist[to.ff].ff, to.ff});
 			} else if(dist[to.ff].ff == dist[v].ff + to.ss) {
 				dist[to.ff].ss = min(dist[to.ff].ss, min(disv[to.ff], dist[v].ss));
			 }
		}
	}
	long long ans = disv[U];
//	cout<<diss[t].ff<<endl;
	for(int a = 1; a <= n; a ++) {
//		cout<<diss[a].ff<<" "<<dist[a].ff<<" "<<a<<endl;
		if(diss[a].ff + dist[a].ff == diss[t].ff) {
//			cout<<a<<" "<<diss[a].ss<<" "<<dist[a].ss<<endl;
			ans = min(ans, diss[a].ss + dist[a].ss);
		}
	}
	for(int i = 1; i <= n; i ++) diss[i] = {inf, inf};
	diss[s] = {0, disv[s]};
	st.insert({diss[s].ff, s});
	while(!st.empty()) {
		int v = (*st.begin()).ss;
		st.erase(st.begin());
		for(auto to : g[v]) {
			if(diss[to.ff].ff > diss[v].ff + to.ss) {
				if(diss[to.ff].ff != inf) st.erase({diss[to.ff].ff, to.ff});
				diss[to.ff] = {diss[v].ff + to.ss, min(disv[to.ff], diss[v].ss)};
				st.insert({diss[to.ff].ff, to.ff});
 			} else if(diss[to.ff].ff == diss[v].ff + to.ss) {
 				diss[to.ff].ss = min(diss[to.ff].ss, min(disv[to.ff], diss[v].ss));
			 }
		}
	}
	for(int i = 1; i <= n; i ++) dist[i] = {inf, inf};
	dist[t] = {0, disu[t]};
	st.insert({dist[t].ff, t});
	while(!st.empty()) {
		int v = (*st.begin()).ss;
		st.erase(st.begin());
		for(auto to : g[v]) {
			if(dist[to.ff].ff > dist[v].ff + to.ss) {
				if(dist[to.ff].ff != inf) st.erase({dist[to.ff].ff, to.ff});
				dist[to.ff] = {dist[v].ff + to.ss, min(disu[to.ff], dist[v].ss)};
				st.insert({dist[to.ff].ff, to.ff});
 			} else if(dist[to.ff].ff == dist[v].ff + to.ss) {
 				dist[to.ff].ss = min(dist[to.ff].ss, min(disu[to.ff], dist[v].ss));
			 }
		}
	}
	for(int a = 1; a <= n; a ++) {
//		cout<<diss[a].ff<<" "<<dist[a].ff<<" "<<a<<endl;
		if(diss[a].ff + dist[a].ff == diss[t].ff) {
			ans = min(ans, diss[a].ss + dist[a].ss);
		}
	}
	cout<<ans;
}
 
signed main() {		
// 	Freopen("nondec");
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 
//   	precalc();
   	
    int ttt = 1;
//    cin>>ttt;
 
    for(int i=1; i<=ttt; i++) {Baizho(); }
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void Freopen(std::string)':
commuter_pass.cpp:35:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:35:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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